左から右に格納されたリストとして表示できる抽象データ型があり、次の操作が可能です: プッシュ: リストの左端に新しいアイテムを追加する ポップ: リストの左端にあるアイテムを削除する プル: リストの右端のアイテムを削除します
プッシュ、ポップ、またはプル操作の償却時間が一定になるように、3 つのスタックと一定の追加メモリを使用してこれを実装します。スタックには、isEmpty、Push、および Pop という基本的な操作があります。
償却された時間とは、「この時間を費やすと、別のブロックを費やして、後で使用するために時間の銀行に保存できる」ことを意味します。各プッシュ操作と同様に、一定時間の 3 つのブロックを費やすため、要素がプッシュされるたびに、一定時間の 2 つの余分なブロックがあります。
いくつかの仮定を行います。
プッシュ、ポップ、またはプル操作の償却時間が一定になるように、3 つのスタックと一定の追加メモリを使用してこれを実装します。スタックには、isEmpty、Push、および Pop という基本的な操作があります。
それなら、私の最初のアドバイスは、リンクされたリストについてあなたに話している人々を無視することです. 確かに、それは合理的な人なら3 スタックの要件なしでそれを実装する方法ですが、宿題の重要な要素は、合理的な人が行う方法ではなく、インストラクターがあなたに望んでいる方法で行うことです。
2 番目のアドバイスは、ブロック、カードのデッキ、または発泡スチロールのカップの束を用意して、3 つのスタックを指定することです (たとえば、コースターなどで)。あるスタックの内容を別のスタックに転送すると何が起こるかを試してみると、アイデアが得られるはずです。
3 つのスタックのみを使用する何かを行うことができます。ハノイの塔を考えてみてください。
双方向にリンクされたリストを使用し、先頭と末尾へのポインターを保持します。残りの部分については、最初に独自のコードを作成する必要があります。その後、修正をお手伝いします。
2つのスタック（かなり標準的な問題）の観点からキューを実装することから始めて、一般化します。