スタックを使用したキューの実装

キューとスタックは、日常のコーディングで使用する非常に単純なデータ構造です。実際、これらはデータを維持するための最も簡単な構造であると考えることができます。

この記事全体を通じて、データ構造を参照するために DS を使用します。

キューは、FIFO 原理で動作する DS です。最初に来たデータが最初に出力されることが許可されます。キューを実装するにはさまざまな方法があります。配列、リンク リスト、その他多くのものを自由に使用できます。ただし、ここでは、Stack と呼ばれる別の DS を使用した Queue の実装について説明します。

皆さんご存知のように、Stack は LIFO 原理で動作する DS です。私はいつも本を積み重ねることを考えているので、視覚化するのに役立つ場合は、その例えを自由に使ってください。

ハッカーランクでこの質問を見つけました。そこでは、2 つのスタックを使用してキューを実装する必要がありました。簡単そうに聞こえますか？どうすればこれを達成できるか少し考えてください。

これを行う方法はたくさんあるので、いくつかの解決策を思いついたかもしれません。それでは、直接試してみてはいかがでしょうか?

質問

それでは、試してみて「タイムアウト エラー」が発生した人、そしてわざわざ試してみなかった人のために、この問題に対する最も簡単で簡単な解決策を説明しましょう。

まず、スタックを実装する方法を見てみましょう。

ご覧のとおり、リストを使用してスタックを実装しました。最初に、コンストラクターは空のリストを初期化します。データをリストの最後に追加してプッシュします。ポップ中にインデックスを指定しないと、リストの最後からポップされます。したがって、最後に挿入される要素が最初にポップアウトされる要素となります。

ここで、キューと同様の方法で 2 つの異なるスタックを初期化しました。 1 つはエンキュー用、もう 1 つはデキュー用です。

リストの最後にデータをプッシュするためだけに、スタックと同様の enqueueStack を使用します。しかし、dequeueStack の場合、スタックのポップ関数が最後の要素から要素を削除することがわかっているので、私たちが行うことは次のとおりです。 enqueueStack を反転して dequeueStack に置きます。したがって、enqueueStack の最初の要素は dequeueStack の最後の要素になり、enqueueStack の 2 番目の要素は dequeueStack の最後から 2 番目になります。したがって、dequeueStack に Pop 関数を使用すると、プッシュした最初の要素が削除され、キューが模倣されます。

今はわかりにくいかもしれませんが、心配しないでください。コードを見れば、私が何を言っているのか理解できるでしょう。実際に今すぐ見てください!

これらの追加チェックは何のためにあるのか疑問に思われるかもしれません。 dequeueStack が空かどうかを確認するのと同様です。最初にそれを確認しないと。反転により enqueueStack の要素は dequeueStack に配置され、最初にあるはずだったデキュー Stacks 要素が最後になってしまいます。したがって、コードに示すように、最初に dequeueStack を空にする必要があります。

これと同様に、printFront はキューの先頭にあるはずの項目を印刷します。

この実装後、入力を STDIN から読み取り、出力を STDOUT に出力します。

私たちの入力は次のようになります:

そして完全なメイン関数は次のとおりです:

私はこれをできるだけ簡単な方法で実装しようとしました。これを実装するには他にもいくつかのより良い方法があるかもしれません。そのうちの 1 つをここで紹介します!

以上がスタックを使用したキューの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。