C++でキューを使用してスタックを実装する方法

キューでスタックを実装するとは

キューを使ってスタックを実装することを考えてみましょう。そのためには、スタックに対して以下のメソッドを定義する必要があります。

• push(x) – 要素xをスタックにプッシュします。
• pop() – スタックの先頭（トップ）要素を削除し、その値を返します。
• top() – スタックの先頭要素を参照して返します。
• empty() – スタックが空かどうかを判定して返します。

例えば、push(10)とpush(20)を順に呼び出した後、pop()を2回呼び出すと、出力は「20」「10」の順になります。これはスタックのLIFO（Last In First Out：後入れ先出し）という性質によるものです。

アルゴリズム（解き方の手順）

この問題を解くには、以下の手順に従います。

1. デック（deque）q を1つ定義します。
2. 関数 push(x) を定義し、x を q の先頭に挿入します。
3. 関数 pop() を定義します。k := q の先頭要素とし、q から先頭要素を削除して k を返します。
4. 関数 top() を定義します。q の先頭要素をそのまま返します。
5. 関数 empty() を定義します。q が空の場合は true を、そうでなければ false を返します。

ポイントは、push時に先頭へ挿入（push_front）することです。これにより、最後に追加した要素が常に先頭に位置するため、キュー構造でありながらスタックと同じLIFOの動作を実現できます。

実装例

理解を深めるために、以下のC++実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class MyStack {
private:
    deque<int> q;
public:
    void push(int x){
        q.push_front(x);
    }
    int pop(){
        int k = q.front();
        q.pop_front();
        return k;
    }
    int top(){
        return q.front();
    }
    bool empty(){
        if (q.empty())
            return true;
        else
            return false;
    }
};
main(){
    MyStack ob;
    ob.push(10);
    ob.push(20);
    cout << (ob.pop()) << endl;
    cout << (ob.pop()) << endl;
}

入力

push(10),push(20),pop(),pop()

出力

20
10

計算量について

std::dequeでは先頭への挿入・削除・アクセスがすべてO(1)で行えるため、push・pop・top・emptyのどの操作も定数時間で実行できます。この実装はシンプルでありながら効率的で、面接や競技プログラミングでもよく使われるテクニックです。