C++で2つのキューを使ってスタックを実装する方法（サンプルコード付き）

スタック（Stack）とは

スタックはLIFO（Last In First Out：後入れ先出し）方式で動作するデータ構造です。要素の挿入と削除がすべて同じ端（トップ）から行われ、最後に入力した要素が最初に取り出されます。

スタックの主な操作は以下のとおりです。

• push(int data) − トップに要素を挿入する
• int pop() − トップから要素を削除（取り出し）する

キュー（Queue）とは

キューはFIFO（First In First Out：先入れ先出し）方式で動作するデータ構造です。挿入は一方の端（リア／末尾）から行い、削除はもう一方の端（フロント／先頭）から行います。最初に入力した要素が最初に取り出されます。

キューの主な操作は以下のとおりです。

• EnQueue(int data) − 末尾（リア）に要素を挿入する
• int DeQueue() − 先頭（フロント）から要素を削除（取り出し）する

本記事では、この性質の異なる2つのデータ構造を組み合わせ、2つのキューを用いてスタックを実装するC++プログラムを紹介します。

2つのキューによるスタック実装の考え方

この実装では、連結リストで構成した2つのキュー（qu1・qu2）を交互に利用します。pop操作を行う際、片方のキューに要素が1つだけ残るまで、もう片方のキューへ順番に移し替えます。最後に残った要素が「最後に入力された要素」であるため、これを取り出すことでLIFO（後入れ先出し）の動作が実現します。

計算量の観点では、pushはO(1)、popはキュー間の要素移動が必要なためO(n)となります。

アルゴリズム

開始
    関数 enqueue1：キューqu1に要素aを挿入する
    np1 = 新しいノードqu1を生成
    np1->d1 = a
    np1->n1 = NULL
    もし f1 == NULL ならば
        r1 = np1
        r1->n1 = NULL
        f1 = r1
    そうでなければ
        r1->n1 = np1
        r1 = np1
        r1->n1 = NULL
終了

開始
    関数 dequeue1：キューqu1から要素を削除する
    もしキューが空ならば
        「キューに要素が存在しません」と表示する
    そうでなければ
        q1 = f1
        f1 = f1->n1
        a = q1->d1
        q1を解放（delete）する
    aを返す
終了

開始
    関数 enqueue2：キューqu2に要素aを挿入する
    np2 = 新しいノードqu2を生成
    np2->d2 = a
    np2->n2 = NULL
    もしキューが空ならば
        r2 = np2
        r2->n2 = NULL
        f2 = r2
    そうでなければ
        r2->n2 = np2
        r2 = np2
        r2->n2 = NULL
終了

開始
    関数 dequeue2：キューqu2から要素を削除する
    もしキューが空ならば
        「キューに要素が存在しません」と表示する
    そうでなければ
        q2 = f2
        f2 = f2->n2
        a = q2->d2
        q2を解放（delete）する
    aを返す
終了

サンプルコード

#include<iostream>
using namespace std;

struct qu1 { // キュー1の宣言
    qu1 *n1;
    int d1;
}*f1 = NULL, *r1 = NULL, *q1 = NULL, *p1 = NULL, *np1 = NULL;

struct qu2 { // キュー2の宣言
    qu2 *n2;
    int d2;
}*f2 = NULL, *r2 = NULL, *q2 = NULL, *p2 = NULL, *np2 = NULL;

void enqueue1(int a) {
    np1 = new qu1;
    np1->d1 = a;
    np1->n1 = NULL;
    if (f1 == NULL) {
        r1 = np1;
        r1->n1 = NULL;
        f1 = r1;
    } else {
        r1->n1 = np1;
        r1 = np1;
        r1->n1 = NULL;
    }
}

int dequeue1() {
    int a;
    if (f1 == NULL) {
        cout<<"キューに要素が存在しません\n";
    } else {
        q1 = f1;
        f1 = f1->n1;
        a = q1->d1;
        delete(q1);
        return a;
    }
}

void enqueue2(int a) {
    np2 = new qu2;
    np2->d2 = a;
    np2->n2 = NULL;
    if (f2 == NULL) {
        r2 = np2;
        r2->n2 = NULL;
        f2 = r2;
    } else {
        r2->n2 = np2;
        r2 = np2;
        r2->n2 = NULL;
    }
}

int dequeue2() {
    int a;
    if (f2 == NULL) {
        cout<<"キューに要素が存在しません\n";
    } else {
        q2 = f2;
        f2 = f2->n2;
        a = q2->d2;
        delete(q2);
        return a;
    }
}

int main() {
    int n, a, i = 0;
    cout<<"スタックに入力する要素の数を入力してください\n";
    cin>>n;
    while (i < n) {
        cout<<"挿入する要素を入力してください\n";
        cin>>a;
        enqueue1(a);
        i++;
    }
    cout<<"\n\n取り出された要素\n\n";
    while (f1 != NULL || f2 != NULL) { // 両方のキューが空でない間
        if (f2 == NULL) { // キュー2が空の場合
            while (f1->n1 != NULL) {
                enqueue2(dequeue1());
            }
            cout<<dequeue1()<<endl;
        } else if (f1 == NULL) { // キュー1が空の場合
            while (f2->n2 != NULL) {
                enqueue1(dequeue2());
            }
            cout<<dequeue2()<<endl;
        }
    }
}

実行結果

スタックに入力する要素の数を入力してください
5
挿入する要素を入力してください
1
挿入する要素を入力してください
2
挿入する要素を入力してください
3
挿入する要素を入力してください
4
挿入する要素を入力してください
5

取り出された要素
5
4
3
2
1

まとめ

入力順に1、2、3、4、5とpushした要素が、5、4、3、2、1の順に取り出されています。これはスタックのLIFO（後入れ先出し）特性どおりの動作です。2つのキューを交互に使い、popのたびに要素を移し替えることで、キューだけでもスタックを実装できることが分かります。