C++を学び始めると、早い段階で出てくるのがスタックとキューです。
どちらもデータを一時的に保存して取り出すための基本的なデータ構造ですが、取り出す順番のルールが異なります。
最初は名前だけ見ても違いがわかりにくいかもしれません。
しかし、この2つはアルゴリズムや探索処理、状態管理などで頻繁に使われるため、しっかり理解しておくことが大切です。
この記事では、C++におけるスタックとキューの基本、違い、使い分け、そして理解しておきたい注意点まで、初心者向けにわかりやすく整理していきます。
スタックとは？
スタックは、最後に入れたものを最初に取り出すデータ構造です。
このルールは「後入れ先出し」と呼ばれ、英語では LIFO（Last In, First Out） と表現されます。
たとえば、本を机の上に積み重ねる場面をイメージするとわかりやすいです。
新しい本は一番上に置かれ、取り出すときも一番上から取ります。
つまり、最後に置いた本が最初に取り出されます。
このように、スタックは「一番最後に追加したものを優先して扱う」構造です。
キューとは？
キューは、最初に入れたものを最初に取り出すデータ構造です。
こちらは「先入れ先出し」と呼ばれ、英語では FIFO（First In, First Out） といいます。
イメージしやすいのは、レジ待ちや受付の順番待ちです。
先に並んだ人から順番に案内され、後から来た人は列の後ろに並びます。
つまり、最初に入ったものが最初に出ていく仕組みです。
このように、キューは「順番通りに処理したい」場面に向いています。
スタックとキューの違い
スタックとキューの違いは、とてもシンプルです。
最大の違いは、どの順番で取り出すかにあります。
スタックは、最後に追加したものから取り出します。
一方、キューは最初に追加したものから順番に取り出します。
この違いだけを見ると小さな差に感じるかもしれませんが、実際には使いどころがかなり変わってきます。
「直前の状態から戻したい」のか、「先に来たものから順に処理したい」のかによって、選ぶべきデータ構造が決まります。
C++ではどう扱うのか
C++では、標準ライブラリの中にスタックとキューを扱う仕組みが用意されています。
それが std::stack と std::queue です。
これらは通常の配列やベクタのように自由に中身へアクセスするためのものではなく、決められたルールでのみ操作できるようにした構造です。
つまり、スタックなら上に積む・上から取る、キューなら後ろに追加して前から取り出す、という使い方に特化しています。
この制限があるからこそ、「順番のルール」が崩れにくくなっています。
スタックでできること
C++のスタックでは、主に次のような操作を行います。
- 要素を追加する
- 一番上の要素を確認する
- 一番上の要素を削除する
- 空かどうかを確認する
- 要素数を確認する
ここで大事なのは、途中の要素を自由に取り出したり確認したりするものではないという点です。
スタックで触れられるのは、基本的に一番上だけです。
そのため、スタックは「積み重ね」として考えると理解しやすくなります。
キューでできること
キューでは、主に次のような操作ができます。
- 要素を末尾に追加する
- 先頭の要素を確認する
- 末尾の要素を確認する
- 先頭の要素を削除する
- 空かどうかを確認する
- 要素数を確認する
キューでは、処理の入口と出口が分かれています。
追加は後ろ、取り出しは前です。
そのため、順番待ちやタスク処理のような流れのある処理に向いています。
まず覚えたい重要ポイント
スタックとキューを学ぶうえで、最初に押さえておきたい注意点がいくつかあります。
削除の操作は値を返さない
C++のスタックやキューでは、要素を削除する操作は削除するだけです。
削除しながら、その値を同時に受け取ることはできません。
そのため、値を使いたい場合は、まず現在の要素を確認してから削除する、という順番になります。
この点は初心者がつまずきやすいところです。
「取り出す」と「削除する」が一体ではなく、C++では分かれていると覚えておくと混乱しにくくなります。
空の状態で要素を見ない
スタックが空なのに一番上の要素を見ようとしたり、キューが空なのに先頭や末尾を見ようとしたりするのは危険です。
こうした使い方は正しくありません。
そのため、要素を確認する前に「空ではないか」をチェックする習慣が大切です。
小さな確認に見えても、実際には非常に重要なポイントです。
スタックが使われる場面
スタックは、「最後に行ったものから戻る」「奥に入ったものから順に処理を終える」といったケースに向いています。
元に戻す機能
アプリやエディタの「Undo（元に戻す）」機能は、最後に行った操作から順番に取り消します。
この仕組みはスタックと非常に相性がよいです。
括弧の対応チェック
数式や文字列の中で、開き括弧と閉じ括弧が正しく対応しているかを確認する処理でもスタックが使われます。
直前の開き括弧と今見ている閉じ括弧を対応させる必要があるためです。
関数呼び出しの考え方
プログラムの関数呼び出しも、考え方としてはスタックに近い動きをします。
後から呼ばれた処理が先に終わり、終わったら元の場所に戻っていきます。
深さ優先探索
グラフや木構造を「まず深く進む」探索では、スタック的な考え方が使われます。
再帰で書く場合も、本質的にはこの考え方に近いです。
キューが使われる場面
キューは、「先に来たものから順番に処理する」「近いところから広げていく」といった場面に向いています。
順番待ちの処理
印刷待ち、受付待ち、ジョブの順次処理などでは、先に入ったものから順番に処理する必要があります。
このような処理にはキューが自然です。
幅優先探索
グラフや木構造を近い順にたどる探索では、キューがよく使われます。
まず近くをすべて見てから、その次の層へ進むという流れになるためです。
最短手数の探索
重みのないグラフで最短の移動回数や手数を求める場合にも、キューを使う幅優先探索が定番です。
ただし、これは「すべての移動コストが同じ」という条件のもとで有効です。
DFSとBFSの違いと覚え方
スタックとキューは、探索アルゴリズムの理解にも直結します。
- DFS（深さ優先探索） はスタック的
- BFS（幅優先探索） はキュー的
この対応はとても重要です。
DFSは、まず奥へ奥へと進んでいく探索です。
一方のBFSは、近いところから順番に広げていく探索です。
この違いを理解しておくと、問題に応じてどちらの考え方を使えばよいか判断しやすくなります。
C++のスタックとキューは「コンテナアダプタ」
少しだけC++らしい話をすると、std::stack と std::queue は単独のコンテナというより、別のコンテナの上に操作制限をかけた仕組みです。
これをコンテナアダプタと呼びます。
内部では deque などのコンテナが使われることが多く、そのうえでスタックやキューとして必要な操作だけを表に出しています。
そのため、ベクタのように中身を自由に走査したり、任意の位置へ直接アクセスしたりする用途には向いていません。
あくまで「ルールに従って順番を守る」ための構造です。
なぜ中身を自由に見られないのか
スタックやキューは、全体を自由に見渡すための構造ではありません。
公開されている操作が意図的に限定されているためです。
これは不便に見えることもありますが、逆にいえば役割が明確で、誤った使い方をしにくいという利点でもあります。
順番のルールを守ることが、このデータ構造の価値そのものだからです。
計算量はどう考えればよい？
スタックとキューの基本操作は、一般的にとても高速です。
追加、削除、先頭や上端の確認などは、通常は一定時間で処理できると考えて問題ありません。
もちろん、厳密には内部構造による違いがあります。
ただ、学習や通常の開発の範囲では「スタックとキューの基本操作は軽い」と理解しておけば十分です。
自作する場合の注意点
学習のためにスタックやキューを自作してみるのは、とても良い練習になります。
特にスタックは比較的シンプルなので、概念理解にも向いています。
一方で、キューは見た目より少し注意が必要です。
単純な配列だけで作ると、前から取り出したあとの空き領域をうまく再利用できないことがあります。
そのため、実用的なキューを作るには循環キューの考え方が必要になります。
学習用として簡単な実装を見るのは有益ですが、実際の開発では標準ライブラリを使うほうが安全です。
スタックとキューの使い分け方
最後に、使い分けの感覚をシンプルにまとめます。
スタックが向いているケース
- 直前の状態から順に戻したい
- 最後に追加したものを優先したい
- 深く潜るような処理をしたい
- 括弧やネスト構造を扱いたい
キューが向いているケース
- 先に来たものから順に処理したい
- 順番待ちを表現したい
- 近い順に探索したい
- タスクを整列して処理したい
この違いを感覚的に理解できるようになると、問題を見た瞬間に「これはスタック向きか、キュー向きか」が判断しやすくなります。
まとめ
C++のスタックとキューは、どちらも非常に基本的でありながら、実践で頻繁に使われる重要なデータ構造です。
スタックは後入れ先出し、キューは先入れ先出し。
この違いが、それぞれの役割を決めています。
スタックは戻る処理や深さ優先探索に向いており、キューは順番待ち処理や幅優先探索に向いています。
また、C++ではこれらが標準ライブラリとして用意されているため、基本を押さえればすぐに実践に活かせます。
まずは「どういう順番で取り出したいのか」を意識して、スタックとキューを使い分けられるようになることが大切です。
この感覚が身につくと、アルゴリズムの理解もかなり進みやすくなります。
以上、C++のスタックとキューについてでした。
最後までお読みいただき、ありがとうございました。
