『Hello アルゴリズム』スタック・キュー章 総まとめLIFO/FIFO の核心 5 要点と配列・連結リスト実装の比較、章末 QA をソースコードで徹底解説【免费下载链接】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 の操作効率表。メソッド説明時間計算量push()スタックトップに要素を追加$O(1)$pop()スタックトップの要素を削除$O(1)$peek()スタックトップの要素にアクセス$O(1)$配列ベースの実装 array_stack.py では、Python の動的配列listをそのままスタックとして使い、append()でプッシュ、pop()でポップ、[-1]でトップへアクセスしています。連結リストベースの実装 linkedlist_stack.py では、連結リストの先頭ノードをスタックトップとみなし、push()で新しいListNodeを頭部挿入node.next self._peek→self._peek nodeしています。**スタックは「制限付きの配列・連結リスト」**とみなせる、という本編の説明どおりの実装です。なお、言語によって組み込みのスタッククラスの有無が異なります。Java はStackInteger、C はstd::stack、Kotlin はStackInt()が利用できますが、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。メソッド説明時間計算量push()キュー末尾に要素を追加エンキュー$O(1)$pop()キュー先頭の要素を削除デキュー$O(1)$peek()キュー先頭の要素にアクセス$O(1)$キュー実装の注意点は、単純な配列で先頭を削除すると $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)$ です。メソッド説明時間計算量push_first()先頭に要素を追加$O(1)$push_last()末尾に要素を追加$O(1)$pop_first()先頭要素を削除$O(1)$pop_last()末尾要素を削除$O(1)$peek_first()先頭要素にアクセス$O(1)$peek_last()末尾要素にアクセス$O(1)$実装方法は 2 通りありますいずれも章末付録の扱いで詳述。双方向連結リストベース先頭・末尾のどちらでも $O(1)$ の挿入削除ができるよう、ノードに前後 2 つのポインタを持たせますlinkedlist_deque.py。空のときはfrontとrearの両方を新ノードに向け、先頭挿入・末尾挿入でポインタを張り替えます。環状配列ベースキューの環状配列実装を土台に、「先頭へのエンキュー」と「末尾からのデキュー」を追加します。先頭への挿入ではself._front self.index(self._front - 1)のように先頭ポインタを左へ 1 つ回すことで実現し、index()内の剰余演算(i capacity) % capacityarray_deque.pyが配列先頭を越えたときの末尾への回帰を担います。言語別の組み込みクラスも充実しています。Python のcollections.deque、C のstd::deque、Java/Kotlin のDequeLinkedList実装、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 つ実行するたびに、その操作をスタックAにプッシュし、スタックBを空にする新しい操作をした時点で、それ以前のやり直し履歴は無効化される。ユーザーが「取り消し」を実行したときは、スタックAから直近の操作をポップし、それをスタックBにプッシュする。ユーザーが「やり直し」を実行したときは、スタックBから直近の操作をポップし、それをスタックAにプッシュする。ポイントは**「新しい操作が入るとやり直し用スタックBがクリアされる」**というルール 1 です。これを外すと、取り消しの後に別の操作をした場合でも古い「やり直し」候補が残り、履歴が不整合になります。ステップ 2・3 のポップは、スタックの基本的なpop()だけで実現できるため、時間計算量は各操作 $O(1)$ です。加えて、Q1・Q3 で述べたように取り消し履歴の上限を設ける設計では、スタックAの代わりに両端キューを使うことで、底最も古い操作からの削除も可能になります。復習の進め方コード実行と演習問題この章の内容を定着させるためのルートを紹介します。基本操作を再実行する日本語版 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 つの設計判断が対比して理解できます。両端キューの復習deque.md の図解双方向連結リスト編・環状配列編は、先頭挿入時のポインタ移動が最も分かりやすい教材です。演習問題に挑戦する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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考