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

Stack（スタック）はVectorクラスのサブクラスであり、オブジェクトを後入れ先出し（LIFO：Last-In-First-Out）で管理するデータ構造です。スタックの最上部に最後に追加された要素が、最初に取り出される要素になります。

一方、Queue（キュー）はCollectionインターフェースを継承しており、先入れ先出し（FIFO：First-In-First-Out）に基づく挿入（insert）と削除（remove）の操作をサポートします。

一見すると性質の異なるこの2つのデータ構造ですが、キューの使い方を少し工夫するだけで、キューのみを使ってスタックを実装することができます。

キューでスタックを実装する仕組み

ポイントはpush処理にあります。新しい要素をキューに追加した直後に、それまで格納されていた既存の要素をすべて一度取り出しては、もう一度末尾へ追加し直します。この「並べ替え」によって、最新の要素が常にキューの先頭に配置されるようになります。

その結果、pop処理ではキューの先頭要素を削除するだけでよく、スタックと同じLIFO（後入れ先出し）の動作が実現できます。

コード例

import java.util.*;
public class StackFromQueueTest {
    Queue queue = new LinkedList();

    public void push(int value) {
        int queueSize = queue.size();
        queue.add(value);
        // 既存の要素をすべて一度取り出して、新要素の後ろに回す
        for (int i = 0; i < queueSize; i++) {
            queue.add(queue.remove());
        }
    }

    public void pop() {
        System.out.println("スタックから取り出された要素は: " + queue.remove());
    }

    public static void main(String[] args) {
        StackFromQueueTest test = new StackFromQueueTest();
        test.push(10);
        test.push(20);
        test.push(30);
        test.push(40);
        System.out.println(test.queue);
        test.pop();
        System.out.println(test.queue);
    }
}

実行結果

[40, 30, 20, 10]
スタックから取り出された要素は: 40
[30, 20, 10]

動作のポイント

• push(10)、push(20)、push(30)、push(40) の順に追加すると、キューの内容は [40, 30, 20, 10] となり、最新の値が必ず先頭に来ます。
• pop() を呼び出すと、先頭の 40 が取り出され、残りのキューは [30, 20, 10] になります。
• pushのたびに既存要素を回転させるため、pushの計算量はO(n)、popはO(1)となる点に注意してください。