『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/ 配下の各種クラスを補助資料として構成した技術解説です?！钢攸cレビュー」の 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 の動的配列l(wèi)istをそのままスタックとして使い、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 つ後ろを指す配列を環(huán)狀配列とみなし、インデックスが末尾を越えたら先頭へ戻す「剰余演算」を適用する実際のコードでは、エンキュー時にrear (self._front self._size) % self.capacity()array_queue.py、デキュー時にself._front (self._front 1) % self.capacity()と計算されており、これによりエンキュー?デキューとも 1 操作 $O(1)$ を実現しています。環(huán)狀配列キューの欠點は容量が固定で可変にできないことですが、配列を動的配列に置き換えれば拡張機構を導入できます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の両方を新ノードに向け、先頭挿入?末尾挿入でポインタを張り替えます。環(huán)狀配列ベースキューの環(huán)狀配列実裝を土臺に、「先頭へのエンキュー」と「末尾からのデキュー」を追加します。先頭への挿入では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 の応用節(jié)で言及されています。実際、本編は「ソフトウェアの『元に戻す』機能の中核はスタックだが、取り消し可能な手數を 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 が付いているので単體実行して動作を確認できます。実裝の差分を読むと、スタックの「頭部挿入」、キューの「環(huán)狀配列と剰余演算」、両端キューの「雙方向リンク」という 3 つの設計判斷が対比して理解できます。両端キューの復習deque.md の図解雙方向連結リスト編?環(huán)狀配列編は、先頭挿入時のポインタ移動が最も分かりやすい教材です。演習問題に挑戦する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創(chuàng)作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考 『Hello アルゴリズム』スタック?キュー章 総まとめ：LIFO/FIFO の核心 5 要點と配列?連結リスト実裝の比較、章末 QA をソースコードで徹底解説
『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/ 配下の各種クラスを補助資料として構成した技術解説です?！钢攸cレビュー」の 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 の動的配列l(wèi)istをそのままスタックとして使い、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 つ後ろを指す配列を環(huán)狀配列とみなし、インデックスが末尾を越えたら先頭へ戻す「剰余演算」を適用する実際のコードでは、エンキュー時にrear (self._front self._size) % self.capacity()array_queue.py、デキュー時にself._front (self._front 1) % self.capacity()と計算されており、これによりエンキュー?デキューとも 1 操作 $O(1)$ を実現しています。環(huán)狀配列キューの欠點は容量が固定で可変にできないことですが、配列を動的配列に置き換えれば拡張機構を導入できます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の両方を新ノードに向け、先頭挿入?末尾挿入でポインタを張り替えます。環(huán)狀配列ベースキューの環(huán)狀配列実裝を土臺に、「先頭へのエンキュー」と「末尾からのデキュー」を追加します。先頭への挿入では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 の応用節(jié)で言及されています。実際、本編は「ソフトウェアの『元に戻す』機能の中核はスタックだが、取り消し可能な手數を 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 が付いているので単體実行して動作を確認できます。実裝の差分を読むと、スタックの「頭部挿入」、キューの「環(huán)狀配列と剰余演算」、両端キューの「雙方向リンク」という 3 つの設計判斷が対比して理解できます。両端キューの復習deque.md の図解雙方向連結リスト編?環(huán)狀配列編は、先頭挿入時のポインタ移動が最も分かりやすい教材です。演習問題に挑戦する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創(chuàng)作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考