2つのスタックを使ってキューを実装するC++プログラム

スタック（Stack）とは

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

スタックの基本操作は次のとおりです。

• push(int data) − トップに要素を挿入する
• int pop() − トップから要素を削除して返す

キュー（Queue）とは

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

キューの基本操作は次のとおりです。

• EnQueue(int data) − リア側に要素を挿入する
• int DeQueue() − フロント側から要素を削除して返す

この記事では、2つのスタックを組み合わせてキューを実装するC++プログラムを紹介します。

各関数の動作

• enQueue()関数：キューへ要素を追加します。
  • s1に値mをプッシュします。
• deQueue()関数：キューから要素を取り出します。
  • 両方のスタックが空の場合は「Queue is empty」を表示して終了します。
  • s2が空の場合は、s1の全要素をs2へ移し替えます。
  • s2から要素をポップして返します。
• push()関数：スタックに要素をプッシュします。
• pop()関数：スタックから要素をポップします。

計算量のポイント

deQueue()では、s1の要素をまとめてs2へ移動することで順序が反転し、キューとしてFIFOの振る舞いを実現しています。各要素がスタック間を移動するのは高々2回だけなので、一連の操作全体で見ると償却計算量O(1)でキュー操作が可能です。

サンプルコード

#include <stdlib.h>
#include <iostream>
using namespace std;

struct nod { // ノードの宣言
    int d;
    struct nod *n;
};

void push(struct nod** top_ref, int n_d); // 関数プロトタイプ
int pop(struct nod** top_ref);

struct queue {
    struct nod *s1;
    struct nod *s2;
};

void enQueue(struct queue *q, int m) {
    push(&q->s1, m);
}

int deQueue(struct queue *q) {
    int m;
    if (q->s1 == NULL && q->s2 == NULL) {
        cout << "Queue is empty";
        exit(0);
    }
    if (q->s2 == NULL) {
        while (q->s1 != NULL) {
            m = pop(&q->s1);
            push(&q->s2, m);
        }
    }
    m = pop(&q->s2);
    return m;
}

void push(struct nod** top_ref, int n_d) {
    struct nod* new_node = (struct nod*) malloc(sizeof(struct nod));

    if (new_node == NULL) {
        cout << "Stack underflow \n";
        exit(0);
    }
    // スタックに要素を積む
    new_node->d = n_d;
    new_node->n = (*top_ref);
    (*top_ref) = new_node;
}

int pop(struct nod** top_ref) {
    int res;
    struct nod *top;
    if (*top_ref == NULL) { // スタックが空の場合
        cout << "Stack overflow \n";
        exit(0);
    } else { // スタックから要素を取り出す
        top = *top_ref;
        res = top->d;
        *top_ref = top->n;
        free(top);
        return res;
    }
}

int main() {
    struct queue *q = (struct queue*) malloc(sizeof(struct queue));
    q->s1 = NULL;
    q->s2 = NULL;
    cout << "Enqueuing..7" << endl;
    enQueue(q, 7);
    cout << "Enqueuing..6" << endl;
    enQueue(q, 6);
    cout << "Enqueuing..2" << endl;
    enQueue(q, 2);
    cout << "Enqueuing..3" << endl;
    enQueue(q, 3);

    cout << "Dequeuing..." << deQueue(q) << " " << endl;
    cout << "Dequeuing..." << deQueue(q) << " " << endl;
    cout << "Dequeuing..." << deQueue(q) << " " << endl;
}

実行結果

Enqueuing..7
Enqueuing..6
Enqueuing..2
Enqueuing..3
Dequeuing...7
Dequeuing...6
Dequeuing...2