1. 序章

このチュートリアルでは、2つのキューを使用してスタックデータ構造を実装します。

2. スタックとキューの基本

アルゴリズムに進む前に、まずこれら2つのデータ構造を見てみましょう。

2.1. スタック

スタックでは、LIFO（後入れ先出し）の順序で要素を追加します。これは、スタックに挿入された最後の要素が最初に削除されることを意味します。 スタックの基本的な操作は次のとおりです。

  • push —上部に要素を挿入します
  • pop —上部から要素を削除します

2.2. 列

キューで、FIFO（First In、First Out）の順序で要素を追加します。つまり、最初に挿入された要素が最初に削除されます。 キューの基本的な操作は次のとおりです。

  • enqueue —背面に要素を挿入します
  • dequeue —前面から要素を削除します

3. アルゴリズム

2つのキュー（ q1 、 q2 ）を使用してスタックを構築するには、キュー操作を使用してスタック操作をシミュレートする必要があります。

  • プッシュ（ E 要素）
    • q1 が空の場合、 enqueue Eからq1
    • q1 が空でない場合、enqueueからq1からq2までのすべての要素、 enqueue E からq1、およびenqueueからq2からq1までのすべての要素
  • ポップ
    • dequeue q1からの要素

ご覧のとおり、 q1 はスタックのメインソースとして機能しますが、 q2 は、スタックが期待する順序を維持するために使用する単なるヘルパーキューです。

pushおよびpop操作の擬似コードは次のとおりです。

pop操作の時間計算量はO（1）です。 push 操作の場合、 q1からn -1要素を転送する必要があるため、 O（n）の時間計算量があります。 q2 に移動し、q2からq1に戻ります。

4. 結論

このチュートリアルでは、2つのキューを使用してスタックを構築するアルゴリズムを紹介しました。

これを行うことに実際の利点がない場合でも、実際のプログラミング経験を教えてくれ、データ構造を組み合わせて再利用して目標を達成できることを示していることに注意してください。 スタックとキューについては、一般的で有用なデータ構造に関する記事で詳しく説明しています。