Ｃ＋＋入門｜スタックとキュー

Ｃ＋＋入門｜スタックとキュー

積むと逆から、並ぶと順番どおり。スタックとキューを覚えれば、データの流れがぐっと見えやすくなる。

C++のSTLには、vector、list、map、setのように、たくさんの便利なデータ構造が用意されています。これらを使いこなせるようになると、複数のデータを効率よく管理できるようになります。
その中でも、処理の順番を考えるうえでとても大切なのが、stackとqueueです。

この2つは、どちらもデータをためて取り出すための仕組みですが、取り出し方のルールがまったく違います。
スタックは、あとから入れたものを先に取り出す仕組みです。
キューは、先に入れたものを先に取り出す仕組みです。

ドラゴンボール風の世界観でたとえると、スタックは修行用の巻物を上から積み重ねていく保管棚のようなものです。最後に置いた巻物がいちばん上に来るので、最初に取り出されるのは最後に置いた巻物になります。
一方でキューは、天下一武道会の受付列のようなものです。先に並んだ戦士から順番に案内されるので、最初に登録したものから先に処理されます。

この記事では、このスタックとキューの考え方、LIFOとFIFOの意味、そしてC++での使い方を、ドラゴンボール風の修行シーンになぞらえながらやさしく整理していきます。

スタックとキューとは何か

スタックとキューは、どちらもデータを一時的にためておき、必要になったときに取り出すためのデータ構造です。
ただし、同じ「ためる」という動作でも、取り出す順番のルールが異なります。

スタックは「積み重ねる」という考え方で動きます。
最後に入れたデータが、最初に取り出されます。
この取り出し方を、LIFOと呼びます。LIFOは Last In, First Out の略で、日本語では「最後に入れたものを最初に取り出す」という意味です。

キューは「行列」の考え方で動きます。
最初に入れたデータが、最初に取り出されます。
この取り出し方を、FIFOと呼びます。FIFOは First In, First Out の略で、日本語では「最初に入れたものを最初に取り出す」という意味です。

この違いを理解すると、どの場面でどちらを使うべきかが見えてきます。
たとえば、修行メニューをあとから積み上げて、最新のものから処理したいならスタックが向いています。
一方、受付順や待ち順のように、先に登録した順番を守って処理したいならキューが向いています。

図：スタックとキューの基本イメージ

この図が示していること

この図では、スタックとキューのいちばん大切な違いをひと目で確認できます。
スタックは積み重ねた上から取り出すので、最後に入れたものが最初に出てきます。
キューは列の先頭から処理するので、最初に入れたものが最初に出てきます。

ここが理解できると、stackとqueueの使い分けがぐっとしやすくなります。

スタックとLIFOの考え方

スタックは、積み重ね型のデータ構造です。
たとえば、神殿の書庫に修行巻物を置いていく場面をイメージするとわかりやすいです。

最初に巻物1を置き、その上に巻物2を置き、さらにその上に巻物3を置いたとします。
このとき、いちばん上にあるのは巻物3です。
したがって、最初に取り出せるのも巻物3になります。

つまり、入れた順番が 1 → 2 → 3 だったとしても、取り出す順番は 3 → 2 → 1 になります。
これがLIFOの動きです。

C++のstackクラスでは、この「いちばん上」を取得するために top を使います。
そして、実際に取り除くには pop を使います。
データを追加するには push を使います。

この流れは、積み重ねた道具箱や修行札の管理のような、「最後に積んだものから先に使う」処理にぴったりです。

キューとFIFOの考え方

キューは、行列型のデータ構造です。
こちらは、天下一武道会の受付列を想像すると、とてもわかりやすいです。

最初に戦士1が並び、そのあとに戦士2、最後に戦士3が並んだとします。
このとき、受付される順番は当然、1 → 2 → 3 です。
あとから来た戦士3が、先に並んでいた戦士1より先に案内されることはありません。

これがFIFOの動きです。

C++のqueueクラスでは、先頭の要素を取得するために front を使います。
そして、先頭の要素を取り除くには pop を使います。
データを追加するには、stackと同じく push を使います。

つまり、追加のしかたは同じでも、どこから取り出すかが違うわけです。
この違いが、stackとqueueを区別するいちばん大きなポイントです。

スタックとキューのサンプルプログラム

それでは、実際にC++でstackとqueueを使ったサンプルを見てみましょう。
ここでは、修行番号 1、2、3 を順番に登録し、それをstackとqueueで取り出して、違いを確認します。

プロジェクト/ファイル名： Chap6_10/main.cpp

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

int main(int argc, char** argv) {
    // 修行札を積み重ねるスタック
    stack<int> trainingStack;
    // 武道会の受付順を管理するキュー
    queue<int> receptionQueue;

    // 登録する修行番号
    int data[] = { 1, 2, 3 };

    // データを順番に登録
    for (int i = 0; i < 3; i++) {
        trainingStack.push(data[i]);
        receptionQueue.push(data[i]);
    }

    // スタックの中身を取り出して表示
    cout << "stack : ";
    while (!trainingStack.empty()) {
        // いちばん上の要素を表示
        cout << trainingStack.top() << " ";
        // 表示した要素を取り除く
        trainingStack.pop();
    }
    cout << endl;

    // キューの中身を取り出して表示
    cout << "queue : ";
    while (!receptionQueue.empty()) {
        // 先頭の要素を表示
        cout << receptionQueue.front() << " ";
        // 表示した要素を取り除く
        receptionQueue.pop();
    }
    cout << endl;

    return 0;
}

実行結果

stack : 3 2 1
queue : 1 2 3

この実行結果を見ると、stackでは 3 2 1 の順で表示され、queueでは 1 2 3 の順で表示されています。
同じデータを入れているのに、出てくる順番だけが変わっていることがよくわかります。

stackクラスとqueueクラスの準備

このプログラムの最初で行っているのが、必要なヘッダーの読み込みです。

#include <stack>
#include <queue>

stackクラスを使うには stack ヘッダーが必要です。
queueクラスを使うには queue ヘッダーが必要です。
さらに、画面表示を行うために iostream も読み込んでいます。

そのあとで、stackとqueueのインスタンスを作成しています。

stack<int> trainingStack;
queue<int> receptionQueue;

ここでは、どちらも int 型のデータを扱うようにしています。
つまり、整数の修行番号を保存するためのstackとqueueを作っているわけです。

stack は「整数を積み重ねる箱」、queue は「整数を順番待ちで並べる箱」というイメージで捉えると理解しやすいです。

pushでデータを登録する

次に、for文でデータを登録しています。

for (int i = 0; i < 3; i++) {
    trainingStack.push(data[i]);
    receptionQueue.push(data[i]);
}

この部分では、配列 data に入っている 1、2、3 を順番に、stackとqueueの両方へ登録しています。
ここで面白いのは、登録方法そのものはどちらも push で同じだという点です。

つまり、stackもqueueも、データを追加するときは push を使います。
違いが出るのは、取り出すときです。

登録直後の状態をイメージすると、stackでは 1 の上に 2、その上に 3 が積み重なっています。
queueでは 1 のあとに 2、そのあとに 3 が並んでいます。

図：pushで登録したときのstackとqueueの状態

この図が示していること

この図では、stackとqueueのどちらも、pushでデータを追加することを示しています。
ただし、内部の並び方の考え方が異なります。
stackは上へ積み重なり、queueは順番に横へ並ぶようなイメージで理解すると覚えやすいです。

stackの取り出しはtopとpopを使う

stackのデータを取り出す部分は、次のwhile文です。

while (!trainingStack.empty()) {
    cout << trainingStack.top() << " ";
    trainingStack.pop();
}

ここでは、まず empty で中身が空かどうかを調べています。
empty は、コンテナが空のときに true を返し、データが残っているときに false を返します。
そのため、!trainingStack.empty() は「空ではないあいだ繰り返す」という意味になります。

次に top で、いちばん上の要素を取得しています。
この時点では、1、2、3 の順に追加されたので、いちばん上は 3 です。
そのため最初に表示されるのは 3 になります。

そのあと pop を実行すると、その 3 がstackから取り除かれます。
次に top を呼ぶと、今度はいちばん上が 2 になっているので、2 が表示されます。
さらに pop をすると 2 が消え、次は 1 が表示されます。

この流れによって、stackの出力結果は 3 2 1 になります。

ドラゴンボール風にたとえると、修行巻物を上から1枚ずつ取って読むような動きです。
最後に置いた巻物がいちばん上にあるので、真っ先に使われるのも最後に置いた巻物になります。

queueの取り出しはfrontとpopを使う

queueのデータを取り出す部分は、こちらです。

while (!receptionQueue.empty()) {
    cout << receptionQueue.front() << " ";
    receptionQueue.pop();
}

こちらも、empty で中身が空になるまでループしています。
ただし、取得に使う関数が front になっている点がstackとの違いです。

front は、queueの先頭の要素を取得する関数です。
1、2、3 の順で登録されているので、最初に取り出されるのは 1 です。
そのあと pop を実行すると、1 がqueueから取り除かれます。
次に front を呼ぶと、こんどは先頭が 2 になっているので、2 が表示されます。
さらに pop すると 2 が消え、次は 3 が表示されます。

こうして、queueでは 1 2 3 の順に出力されます。

これは、武道会の受付列そのものです。
先に並んだ戦士から案内されていくので、あとから来た戦士が先に処理されることはありません。

topとfrontの違い

stackとqueueは、どちらも pop でデータを取り除きます。
ですが、取り除く対象を確認する関数が異なります。

stackでは top を使います。
これは、いちばん最後に登録された要素、つまりいちばん上の要素を見るための関数です。

queueでは front を使います。
これは、いちばん最初に登録された要素、つまり先頭の要素を見るための関数です。

この違いが、そのままLIFOとFIFOの違いにつながっています。

この表を見ると、stackとqueueは似ている部分も多いですが、top と front の違いがとても重要だとわかります。

emptyの役割

サンプルでは、stackとqueueの両方で empty を使っています。

while (!trainingStack.empty())
while (!receptionQueue.empty())

empty は、「中身が空かどうか」を調べる関数です。
空なら true、空でなければ false を返します。

たとえば、stackの中にまだ 3、2、1 が残っているなら empty は false です。
したがって !trainingStack.empty() は true になり、ループが続きます。
すべて pop して中身がなくなると empty は true になるので、!trainingStack.empty() は false になり、ループが終わります。

queueでも同じです。
先頭から順に pop していき、中身が空になったらループを終了します。

このように、empty は「取り出せるデータがまだあるかどうか」を確認する、とても大切な関数です。

スタックの流れを順番に追ってみる

stackに 1、2、3 を登録したあと、中身は下から 1、2、3 の順に積まれています。
いちばん上は 3 です。

最初の top では 3 が見えます。
そのあと pop をすると 3 が消えます。

次の top では 2 が見えます。
そのあと pop をすると 2 が消えます。

最後の top では 1 が見えます。
そのあと pop をすると 1 が消えます。

この流れによって、表示順は 3 2 1 になります。

図：stackとqueueの取り出しの流れ

この図が示していること

この図では、stackでは上から、queueでは先頭から取り出していくことを示しています。
stackは top でいちばん新しい要素を見て、pop でそれを取り除きます。
queueは front でいちばん古い要素を見て、pop でそれを取り除きます。

同じ 1、2、3 というデータでも、どちらの構造を使うかによって出力順が変わる理由が、この図からよくわかります。

queueの流れを順番に追ってみる

queueに 1、2、3 を登録したあと、中身は先頭から 1、2、3 の順に並んでいます。
先頭は 1 です。

最初の front では 1 が見えます。
そのあと pop をすると 1 が消えます。

次の front では 2 が見えます。
そのあと pop をすると 2 が消えます。

最後の front では 3 が見えます。
そのあと pop をすると 3 が消えます。

この流れによって、表示順は 1 2 3 になります。

スタックと比べると、まさに逆の考え方になっていることがわかります。
そのため、処理順が重要なプログラムでは、stackを使うべきかqueueを使うべきかをしっかり見極めることが大切です。

どんな場面で使い分けるのか

stackは、最新のものから処理したい場面に向いています。
たとえば、あとから追加した修行メニューを優先して処理したい場合や、途中までの操作を逆順にたどるような処理に向いています。

queueは、登録した順番どおりに処理したい場面に向いています。
たとえば、受付順、待ち行列、順番どおりに処理するイベント管理などで活躍します。

ドラゴンボール風にいえば、stackは修行巻物の山、queueは武道会の受付列です。
このイメージが頭の中にあると、問題を見たときに、どちらを使うべきか直感的に判断しやすくなります。

stackとqueueで覚えておきたい関数

stackとqueueを使うときは、まず push、pop、empty をしっかり覚えるとよいです。
そのうえで、stackなら top、queueなら front を使い分けられるようになれば、基本操作はほぼ押さえられます。

この表を見ながら、stackでは top、queueでは front という違いを意識しておくと、コードを書くときに混乱しにくくなります。

スタックとキューを理解すると何がよいのか

スタックとキューは、ただのSTLクラスというだけではありません。
「データをどういう順番で処理したいのか」という考え方そのものを学ぶための、とても大切なテーマです。

同じデータでも、stackに入れるかqueueに入れるかで、結果が変わります。
つまり、プログラムを書くときには、何を保存するかだけでなく、どの順番で取り出したいかまで考える必要があるわけです。

stackとqueueが理解できると、STLの知識が広がるだけでなく、アルゴリズムやデータ構造全体の見方も深くなっていきます。
C++の学習を進めていくうえでも、とても重要な一歩になります。