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

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

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

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

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

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

質問

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

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

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

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

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

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

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

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

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

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

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

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