『Hello アルゴリズム』スタック・キュー章 総まとめ：LIFO/FIFO の核心 5 要点と配列・連結リスト実装の比較、章末 QA をソースコードで徹底解説

『Hello アルゴリズム』スタック・キュー章 総まとめ：LIFO/FIFO の核心 5 要点と配列・連結リスト実装の比較、章末 Q&A をソースコードで徹底解説

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本記事は、リポジトリの日本語版ドキュメント ja/docs/chapter_stack_and_queue/summary.md（スタックとキューの章まとめ）を骨格とし、同章の本編ドキュメント stack.md、queue.md、deque.md と、公式 Python 実装（ja/codes/python/chapter_stack_and_queue/ 配下の各種クラス）を補助資料として構成した技術解説です。「重点レビュー」の 5 要点を 1 つずつ原理・ソースコード・性能面から掘り下げたうえで、章末の「Q & A」4 問に多言語視点と実装の裏付けを加えて回答します。本記事を読むと、スタック・キュー・両端キューの本質的な違い、配列実装と連結リスト実装の時間・空間効率のトレードオフ、ブラウザの進む・戻るや undo/redo といった応用の正体を、具体コードを追いながら理解できます。

この章の全体像とまとめ記事の読み方

本章は 4 つのページで構成されています。

• stack.md：スタック（後入れ先出し）
• queue.md：キュー（先入れ先出し）
• deque.md：両端キュー（先頭・末尾の両端で挿入削除）
• summary.md：章の総まとめ（本記事のベース）

章の扉（index.md）には「スタックは猫を積み重ねるようなもの、キューは猫が列に並ぶようなもの。両者はそれぞれ後入れ先出しと先入れ先出しの論理関係を表す」という抽象が添えられており、この章で扱う 3 つのデータ構造はすべて配列か連結リストの上に「操作の制約」を掛けた線形データ構造だという視点が一貫しています。本編で学んだ内容を、まとめ記事で「要点」と「Q & A」に凝縮して復習し、さらに本記事のコード参照で最終確認する、という流れがおすすめです。

重点レビュー：理解すべき 5 つの要点

summary.md の「要点の振り返り」には 5 つの核心が示されています。それぞれを順に、ソースコードを交えて解説します。

要点 1：スタックは「後入れ先出し（LIFO）」に従うデータ構造

スタック（stack）は、最後に入れた要素が最初に取り出される**後入れ先出し（LIFO）**の論理に従う線形データ構造です。机の上に積まれた皿の山がたとえとして本編で使われており、いちばん下の皿を取り出すには上から順に皿をどかす必要があります。

• 要素の上端をスタックトップ、下端をスタックボトムと呼ぶ
• スタックトップへの追加をプッシュ、スタックトップからの削除をポップと呼ぶ

基本操作はすべて $O(1)$ です（stack.md の操作効率表）。

配列ベースの実装 array_stack.py では、Python の動的配列listをそのままスタックとして使い、append()でプッシュ、pop()でポップ、[-1]でトップへアクセスしています。連結リストベースの実装 linkedlist_stack.py では、連結リストの先頭ノードをスタックトップとみなし、push()で新しいListNodeを頭部挿入（node.next = self._peek→self._peek = node）しています。**スタックは「制限付きの配列・連結リスト」**とみなせる、という本編の説明どおりの実装です。

なお、言語によって組み込みのスタッククラスの有無が異なります。Java はStack<Integer>、C++ はstd::stack、Kotlin はStack<Int>()が利用できますが、Python・JavaScript・TypeScript・Swift・Go・Ruby などは組み込みスタックを持たないため、listやスライスなどの配列をスタックとして使うのが一般的です（いずれも stack.md のコード例で確認できます）。

要点 2：時間効率——配列実装は平均効率が高く、連結リスト実装は安定

summary.md の要点 2 は「スタックの配列実装は平均効率が高いが、拡張時に 1 回のプッシュが $O(n)$ に劣化する。連結リスト実装はより安定した効率を示す」という内容です。これは次のように整理できます（stack.md の「2つの実装の比較」）。

• 配列実装の長所：プッシュ・ポップはあらかじめ確保された連続メモリ上で行われ、キャッシュ局所性が高いため効率的。ただし、プッシュ時に配列容量を超えると**拡張処理（既存要素の全コピー）**が発生し、その 1 回の操作だけは $O(n)$ になります。拡張自体は低頻度なので、平均的（均攤）には $O(1)$を維持できます。
• 連結リスト実装の長所：容量拡張が不要で、プッシュ効率がデータ量に依存せず安定。ただし、プッシュのたびにノードオブジェクトの初期化とポインタの更新が必要になるため、基本データ型のプッシュでは相対的に効率が落ちます。

プッシュ対象がすでにノードオブジェクトである場合は初期化コストを省けるため、連結リスト実装の効率は相対的に上がる点も本編で言及されています。

要点 3：空間効率——「無駄が出る配列」vs「1 要素あたりが大きい連結リスト」

要点 3 は「配列実装はある程度の領域の無駄を生む可能性があるが、連結リストノードが占有するメモリは配列要素より大きい」というものです。

• 配列（動的配列）は初期化時に初期容量を確保し、拡張も一定の倍率（たとえば 2 倍）で行われるため、実際の要素数より多くの領域を確保しがちです。Python のlist、Java のArrayList、C++ のvectorなど、動的配列全般に共通する性質です。
• 一方、連結リストの各ノードは値に加えて次ノードへのポインタ（双方向連結リストなら前後 2 つのポインタ）を持つため、1 要素あたりのメモリ消費が大きくなります。日本語版の実装でも、双方向連結リストのノードはval・next・prevの 3 フィールドを持つことが linkedlist_deque.py で確認できます。

このため「どちらの実装が省メモリか」は一概には言えず、要素の型や運用状況に応じた分析が必要です。

要点 4：キューは「先入れ先出し（FIFO）」。時間・空間の比較結論はスタックと同様

キュー（queue）は、先に並んだ人が先に処理される先入れ先出し（FIFO）の線形データ構造です。要素の追加はキュー末尾、削除はキュー先頭でのみ行われます（queue.md）。

キュー実装の注意点は、単純な配列で先頭を削除すると $O(n)$ になってしまうことです。本編の配列実装 array_queue.py では、これを回避するために次の 3 つの工夫をしています。

• 変数frontで先頭要素のインデックスを指し、変数sizeで長さを記録する
• 末尾ポインタをrear = front + sizeと定義（末尾要素の 1 つ後ろを指す）
• 配列を環状配列とみなし、インデックスが末尾を越えたら先頭へ戻す「剰余演算」を適用する

実際のコードでは、エンキュー時にrear = (self._front + self._size) % self.capacity()（array_queue.py）、デキュー時にself._front = (self._front + 1) % self.capacity()と計算されており、これによりエンキュー・デキューとも 1 操作 $O(1)$ を実現しています。環状配列キューの欠点は容量が固定で可変にできないことですが、配列を動的配列に置き換えれば拡張機構を導入できます（queue.md もこの実装課題に言及しています）。

連結リスト実装では、先頭ノードをキュー先頭・末尾ノードをキュー末尾とし、末尾にのみノード追加・先頭からのみノード削除を行うため、array_queue.py のような特別なポインタ管理は不要です。時間効率・空間効率の比較結論はスタックの場合と同じです。なお、JavaScript・Swift・Ruby などで配列をキュー代わりに使う場合、先頭削除メソッド（shift()/removeFirst()）は配列全体のシフトを伴い $O(n)$ になる点が、各言語のコード例に注記されています。

要点 5：両端キューは自由度の高いキュー。両端で挿入・削除が可能

**両端キュー（double-ended queue, deque）**は、先頭と末尾の両方で要素の追加・削除ができる、より自由度の高いキューです（deque.md）。

基本操作は 6 つあり、すべて $O(1)$ です。

実装方法は 2 通りあります（いずれも章末付録の扱いで詳述）。

• 双方向連結リストベース：先頭・末尾のどちらでも $O(1)$ の挿入削除ができるよう、ノードに前後 2 つのポインタを持たせます（linkedlist_deque.py）。空のときはfrontとrearの両方を新ノードに向け、先頭挿入・末尾挿入でポインタを張り替えます。
• 環状配列ベース：キューの環状配列実装を土台に、「先頭へのエンキュー」と「末尾からのデキュー」を追加します。先頭への挿入ではself._front = self.index(self._front - 1)のように先頭ポインタを左へ 1 つ回すことで実現し、index()内の剰余演算(i + capacity) % capacity（array_deque.py）が配列先頭を越えたときの末尾への回帰を担います。

言語別の組み込みクラスも充実しています。Python のcollections.deque、C++ のstd::deque、Java/Kotlin のDeque（LinkedList実装）、C# のLinkedList、Dart のQueueなどです。Rust のVecDequeも両端キューで、通常のキューとしても使われます。

Q & A：章末の疑問をソースコードと応用例で掘り下げる

summary.md には 4 つの Q & A が収録されています。ここでは各回答を、本編ドキュメントや実装コードを引きながら補足します。

Q1：ブラウザの「進む・戻る」は双方向連結リストで実装されているのか？

回答は**「本質は『スタック』の表れである」**です。ユーザーが新しいページを開くと、そのページはスタックの先頭に追加されます。戻るボタンを押すと、そのページはスタックの先頭から取り出されます。つまり、閲覧履歴の「戻る」はポップ操作そのものです。

これに加え、両端キューを使うと、履歴の上限を超えたときの古い履歴の破棄や、進む・戻るをまたぐ追加操作などを簡単に実装できます。この点は「両端キュー」の章（deque.md の応用節）で言及されています。実際、本編は「ソフトウェアの『元に戻す』機能の中核はスタックだが、取り消し可能な手数を 50 歩に制限する場合、スタックの底部（先頭）を削除する必要が生じるため、両端キューが必要になる」という例を挙げており、中核ロジックは LIFO、拡張ロジックは両端キューという分担パターンがブラウザ履歴にも応用できる考え方です。

Q2：ポップした後、そのノードのメモリを解放する必要はあるのか？

ポップしたノードを以後も使い続けるのであれば、解放してはいけません。たとえば、pop で取り出した値を後続の計算で使うケースが典型です。逆に、以後そのノードを使わない場合でも、Java・Pythonなどの言語は**自動ガベージコレクション（GC）**を持つため、手動で解放する必要はありません。参照が途切れた時点で GC が回収します。

一方、CやC++は手動メモリ管理が必要です。C でmalloc()したノードは不要になった時点でfree()を、C++ でnewしたノードはdeleteを呼ぶ必要があります。この言語差は「組み込みのスタック/キューを持たない言語は配列や連結リストで自前実装する」という本編の構成とも関係し、たとえば C 版の章コードではfree()によるノード解放が実装の一部として現れます。メモリ管理の有無は、使用言語を選ぶときの実務上の判断材料の 1 つです。

Q3：両端キューは「2 つのスタックをつなげた」ように見えるが、用途は？

両端キューは、スタックとキューの組み合わせ、あるいは 2 つのスタックをつなげた構造のように見えます。その正体は、スタック＋キューの論理を併せ持つデータ構造です。したがって、スタックでできる応用もキューでできる応用もすべて実現でき、しかも両端から操作できる分だけ柔軟です。

具体的なメリットは Q1 の例が分かりやすいでしょう。通常の undo はスタックで実現できますが、「取り消し可能な手数を 50 歩に制限したい」という要件が加わると、最古の操作をスタックの底から削除する操作が必要になります。スタックは底にアクセスできないため、ここで両端キューを使えば、先頭（底）からの削除と末尾（頂上）への追加をどちらも $O(1)$ で行えます。**「やることの中核は LIFO だが、両端操作の自由度が必要」**という場面こそが両端キューの出番です。

Q4：取り消し（undo）とやり直し（redo）は具体的にどう実装するのか？

2 つのスタックを使います。スタックAを取り消し用、スタックBをやり直し（反取り消し）用にします（stack.md の典型的応用でも「進む・戻るを同時にサポートするには 2 つのスタックを組み合わせる」と説明されています）。

手順は summary.md の記述どおり、以下の 3 ルールに集約されます。

1. ユーザーが操作を 1 つ実行するたびに、その操作をスタックAにプッシュし、スタックBを空にする（＝新しい操作をした時点で、それ以前のやり直し履歴は無効化される）。
2. ユーザーが「取り消し」を実行したときは、スタックAから直近の操作をポップし、それをスタックBにプッシュする。
3. ユーザーが「やり直し」を実行したときは、スタックBから直近の操作をポップし、それをスタックAにプッシュする。

ポイントは**「新しい操作が入るとやり直し用スタックBがクリアされる」**というルール 1 です。これを外すと、取り消しの後に別の操作をした場合でも古い「やり直し」候補が残り、履歴が不整合になります。ステップ 2・3 のポップは、スタックの基本的なpop()だけで実現できるため、時間計算量は各操作 $O(1)$ です。加えて、Q1・Q3 で述べたように取り消し履歴の上限を設ける設計では、スタックAの代わりに両端キューを使うことで、底（最も古い操作）からの削除も可能になります。

復習の進め方：コード実行と演習問題

この章の内容を定着させるためのルートを紹介します。

1. 基本操作を再実行する：日本語版 Python コードは ja/codes/python/chapter_stack_and_queue/ に一通りそろっています。stack.py・queue.py・deque.pyが「言語組み込みクラスを使う基本操作」、array_stack.py・linkedlist_stack.py・array_queue.py・linkedlist_queue.py・array_deque.py・linkedlist_deque.pyが「自前実装」に対応しており、各ファイル末尾に Driver Code が付いているので単体実行して動作を確認できます。実装の差分を読むと、スタックの「頭部挿入」、キューの「環状配列と剰余演算」、両端キューの「双方向リンク」という 3 つの設計判断が対比して理解できます。
2. 両端キューの復習：deque.md の図解（双方向連結リスト編・環状配列編）は、先頭挿入時のポインタ移動が最も分かりやすい教材です。
3. 演習問題に挑戦する：exercises.md に章全体の練習問題がまとまっています。言語を変えて同じ操作を書き直すことも、効率比較の感覚を掴むうえで有効です。

なお、中国語版の同章まとめは docs/chapter_stack_and_queue/summary.md にあり、日本語版と内容を対応づけて読み比べることで、用語の理解をさらに深められます。基本操作・実装・応用という流れを、本記事の要点と Q & A で総復習すれば、この章の学習は完了です。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo