Javaでスタックを使ってキュー（Queue）を実装する方法を解説

キューとスタックの基本

Queue（キュー）は Collection インターフェースを継承したクラスで、FIFO（First-In-First-Out：先入れ先出し）方式による要素の挿入と削除をサポートします。一方、Stack（スタック）は Vector クラスのサブクラスであり、LIFO（Last-In-First-Out：後入れ先出し）方式でオブジェクトを管理します。つまり、スタックの一番上に追加された最後の要素が、最初に取り出される要素になります。

この2つのデータ構造の性質は正反対ですが、スタックを2つ組み合わせることで、キューを実装することが可能です。以下では、その具体的な実装方法を紹介します。

実装の考え方

ポイントは次の通りです。

• enqueue（挿入）： 要素は常に1つ目のスタック（stack1）に push します。
• dequeue（削除）： 2つ目のスタック（stack2）が空の場合、stack1 の中身をすべて pop して stack2 に push し直します。これにより順序が反転し、先に入れた要素が stack2 の先頭に来ます。その後、stack2 から pop すれば FIFO の動作が実現できます。

サンプルコード

import java.util.*;

public class QueueUsingStackTest {

    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();

    // 要素を追加する（enqueue）
    public void enqueue(int element) {
        stack1.push(element);
        System.out.println(element + " inserted");
    }

    // 要素を取り出す（dequeue）
    public void dequeue() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        System.out.println(stack2.pop() + " removed");
    }

    public static void main(String args[]) {
        QueueUsingStackTest test = new QueueUsingStackTest();
        test.enqueue(10);
        test.enqueue(50);
        test.enqueue(100);
        test.dequeue();
    }
}

実行結果

10 inserted
50 inserted
100 inserted
10 removed

コードの解説

このプログラムでは、まず 10、50、100 の順に enqueue を呼び出しています。すべての要素は stack1 に積まれていくため、stack1 の内部状態は上から「100 → 50 → 10」となります。

続いて dequeue を呼び出すと、stack2 が空であるため、stack1 の全要素が stack2 へ移されます。この時点で stack2 の内部状態は上から「10 → 50 → 100」となり、最初に入れた 10 が先頭に位置します。そのため pop の結果として 10 removed が出力され、FIFO の挙動が正しく再現されていることがわかります。

計算量について

enqueue 操作は常に O(1) です。dequeue 操作は、stack2 が空の場合に限り O(n) の要素移動が発生しますが、各要素は最大でも1回しか移動しないため、償却計算量（amortized complexity）としては O(1) となります。この手法は、JavaのコレクションAPIだけではなく、アルゴリズムの面接や試験でも頻出のトピックなので、ぜひ理解しておきましょう。