『Hello アルゴリズム』スタック?キュー章 総まとめLIFO/FIFO の核心 5 要點(diǎn)と配列?連結(jié)リスト実裝の比較、章末 QA をソースコードで徹底解説【免費(fèi)下載鏈接】hello-algo《Hello 算法》動(dòng)畫圖解、一鍵運(yùn)行的數(shù)據(jù)結(jié)構(gòu)與算法教程。支持簡中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代碼實(shí)現(xiàn)項(xiàng)目地址: 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/ 配下の各種クラスを補(bǔ)助資料として構(gòu)成した技術(shù)解説です?！钢攸c(diǎn)レビュー」の 5 要點(diǎn)を 1 つずつ原理?ソースコード?性能面から掘り下げたうえで、章末の「Q A」4 問に多言語視點(diǎn)と実裝の裏付けを加えて回答します。本記事を読むと、スタック?キュー?両端キューの本質(zhì)的な違い、配列実裝と連結(jié)リスト実裝の時(shí)間?空間効率のトレードオフ、ブラウザの進(jìn)む?戻るや undo/redo といった応用の正體を、具體コードを追いながら理解できます。この章の全體像とまとめ記事の読み方本章は 4 つのページで構(gòu)成されています。stack.mdスタック後入れ先出しqueue.mdキュー先入れ先出しdeque.md両端キュー先頭?末尾の両端で挿入削除summary.md章の総まとめ本記事のベース章の扉index.mdには「スタックは貓を積み重ねるようなもの、キューは貓が列に並ぶようなもの。両者はそれぞれ後入れ先出しと先入れ先出しの論理関係を表す」という抽象が添えられており、この章で扱う 3 つのデータ構(gòu)造はすべて配列か連結(jié)リストの上に「操作の制約」を掛けた線形データ構(gòu)造だという視點(diǎn)が一貫しています。本編で學(xué)んだ內(nèi)容を、まとめ記事で「要點(diǎn)」と「Q A」に凝縮して復(fù)習(xí)し、さらに本記事のコード參照で最終確認(rèn)する、という流れがおすすめです。重點(diǎn)レビュー理解すべき 5 つの要點(diǎn)summary.md の「要點(diǎn)の振り返り」には 5 つの核心が示されています。それぞれを順に、ソースコードを交えて解説します。要點(diǎn) 1スタックは「後入れ先出しLIFO」に従うデータ構(gòu)造スタックstackは、最後に入れた要素が最初に取り出される**後入れ先出しLIFO**の論理に従う線形データ構(gòu)造です。機(jī)の上に積まれた皿の山がたとえとして本編で使われており、いちばん下の皿を取り出すには上から順に皿をどかす必要があります。要素の上端をスタックトップ、下端をスタックボトムと呼ぶスタックトップへの追加をプッシュ、スタックトップからの削除をポップと呼ぶ基本操作はすべて $O(1)$ ですstack.md の操作効率表。メソッド説明時(shí)間計(jì)算量push()スタックトップに要素を追加$O(1)$pop()スタックトップの要素を削除$O(1)$peek()スタックトップの要素にアクセス$O(1)$配列ベースの実裝 array_stack.py では、Python の動(dòng)的配列l(wèi)istをそのままスタックとして使い、append()でプッシュ、pop()でポップ、[-1]でトップへアクセスしています。連結(jié)リストベースの実裝 linkedlist_stack.py では、連結(jié)リストの先頭ノードをスタックトップとみなし、push()で新しいListNodeを頭部挿入node.next self._peek→self._peek nodeしています。**スタックは「制限付きの配列?連結(jié)リスト」**とみなせる、という本編の説明どおりの実裝です。なお、言語によって組み込みのスタッククラスの有無が異なります。Java はStackInteger、C はstd::stack、Kotlin はStackInt()が利用できますが、Python?JavaScript?TypeScript?Swift?Go?Ruby などは組み込みスタックを持たないため、listやスライスなどの配列をスタックとして使うのが一般的ですいずれも stack.md のコード例で確認(rèn)できます。要點(diǎn) 2時(shí)間効率——配列実裝は平均効率が高く、連結(jié)リスト実裝は安定summary.md の要點(diǎn) 2 は「スタックの配列実裝は平均効率が高いが、拡張時(shí)に 1 回のプッシュが $O(n)$ に劣化する。連結(jié)リスト実裝はより安定した効率を示す」という內(nèi)容です。これは次のように整理できますstack.md の「2つの実裝の比較」。配列実裝の長所プッシュ?ポップはあらかじめ確保された連続メモリ上で行われ、キャッシュ局所性が高いため効率的。ただし、プッシュ時(shí)に配列容量を超えると**拡張処理既存要素の全コピー**が発生し、その 1 回の操作だけは $O(n)$ になります。拡張自體は低頻度なので、平均的均攤には $O(1)$を維持できます。連結(jié)リスト実裝の長所容量拡張が不要で、プッシュ効率がデータ量に依存せず安定。ただし、プッシュのたびにノードオブジェクトの初期化とポインタの更新が必要になるため、基本データ型のプッシュでは相対的に効率が落ちます。プッシュ対象がすでにノードオブジェクトである場合は初期化コストを省けるため、連結(jié)リスト実裝の効率は相対的に上がる點(diǎn)も本編で言及されています。要點(diǎn) 3空間効率——「無駄が出る配列」vs「1 要素あたりが大きい連結(jié)リスト」要點(diǎn) 3 は「配列実裝はある程度の領(lǐng)域の無駄を生む可能性があるが、連結(jié)リストノードが占有するメモリは配列要素より大きい」というものです。配列動(dòng)的配列は初期化時(shí)に初期容量を確保し、拡張も一定の倍率たとえば 2 倍で行われるため、実際の要素?cái)?shù)より多くの領(lǐng)域を確保しがちです。Python のlist、Java のArrayList、C のvectorなど、動(dòng)的配列全般に共通する性質(zhì)です。一方、連結(jié)リストの各ノードは値に加えて次ノードへのポインタ雙方向連結(jié)リストなら前後 2 つのポインタを持つため、1 要素あたりのメモリ消費(fèi)が大きくなります。日本語版の実裝でも、雙方向連結(jié)リストのノードはval?next?prevの 3 フィールドを持つことが linkedlist_deque.py で確認(rèn)できます。このため「どちらの実裝が省メモリか」は一概には言えず、要素の型や運(yùn)用狀況に応じた分析が必要です。要點(diǎn) 4キューは「先入れ先出しFIFO」。時(shí)間?空間の比較結(jié)論はスタックと同様キューqueueは、先に並んだ人が先に処理される先入れ先出しFIFOの線形データ構(gòu)造です。要素の追加はキュー末尾、削除はキュー先頭でのみ行われますqueue.md。メソッド説明時(shí)間計(jì)算量push()キュー末尾に要素を追加エンキュー$O(1)$pop()キュー先頭の要素を削除デキュー$O(1)$peek()キュー先頭の要素にアクセス$O(1)$キュー実裝の注意點(diǎn)は、単純な配列で先頭を削除すると $O(n)$ になってしまうことです。本編の配列実裝 array_queue.py では、これを回避するために次の 3 つの工夫をしています。変數(shù)frontで先頭要素のインデックスを指し、変數(shù)sizeで長さを記録する末尾ポインタをrear front sizeと定義末尾要素の 1 つ後ろを指す配列を環(huán)狀配列とみなし、インデックスが末尾を越えたら先頭へ戻す「剰余演算」を適用する実際のコードでは、エンキュー時(shí)にrear (self._front self._size) % self.capacity()array_queue.py、デキュー時(shí)にself._front (self._front 1) % self.capacity()と計(jì)算されており、これによりエンキュー?デキューとも 1 操作 $O(1)$ を?qū)g現(xiàn)しています。環(huán)狀配列キューの欠點(diǎn)は容量が固定で可変にできないことですが、配列を動(dòng)的配列に置き換えれば拡張機(jī)構(gòu)を?qū)毪扦蓼筿ueue.md もこの実裝課題に言及しています。連結(jié)リスト実裝では、先頭ノードをキュー先頭?末尾ノードをキュー末尾とし、末尾にのみノード追加?先頭からのみノード削除を行うため、array_queue.py のような特別なポインタ管理は不要です。時(shí)間効率?空間効率の比較結(jié)論はスタックの場合と同じです。なお、JavaScript?Swift?Ruby などで配列をキュー代わりに使う場合、先頭削除メソッドshift()/removeFirst()は配列全體のシフトを伴い $O(n)$ になる點(diǎn)が、各言語のコード例に注記されています。要點(diǎn) 5両端キューは自由度の高いキュー。両端で挿入?削除が可能**両端キューdouble-ended queue, deque**は、先頭と末尾の両方で要素の追加?削除ができる、より自由度の高いキューですdeque.md?；静僮鳏?6 つあり、すべて $O(1)$ です。メソッド説明時(shí)間計(jì)算量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 通りありますいずれも章末付録の扱いで詳述。雙方向連結(jié)リストベース先頭?末尾のどちらでも $O(1)$ の挿入削除ができるよう、ノードに前後 2 つのポインタを持たせますlinkedlist_deque.py。空のときはfrontとrearの両方を新ノードに向け、先頭挿入?末尾挿入でポインタを張り替えます。環(huán)狀配列ベースキューの環(huán)狀配列実裝を土臺に、「先頭へのエンキュー」と「末尾からのデキュー」を追加します。先頭への挿入ではself._front self.index(self._front - 1)のように先頭ポインタを左へ 1 つ回すことで実現(xiàn)し、index()內(nèi)の剰余演算(i capacity) % capacityarray_deque.pyが配列先頭を越えたときの末尾への回帰を擔(dān)います。言語別の組み込みクラスも充実しています。Python のcollections.deque、C のstd::deque、Java/Kotlin のDequeLinkedList実裝、C# のLinkedList、Dart のQueueなどです。Rust のVecDequeも両端キューで、通常のキューとしても使われます。Q A章末の疑問をソースコードと応用例で掘り下げるsummary.md には 4 つの Q A が収録されています。ここでは各回答を、本編ドキュメントや実裝コードを引きながら補(bǔ)足します。Q1ブラウザの「進(jìn)む?戻る」は雙方向連結(jié)リストで実裝されているのか回答は**「本質(zhì)は『スタック』の表れである」**です。ユーザーが新しいページを開くと、そのページはスタックの先頭に追加されます。戻るボタンを押すと、そのページはスタックの先頭から取り出されます。つまり、閲覧履歴の「戻る」はポップ操作そのものです。これに加え、両端キューを使うと、履歴の上限を超えたときの古い履歴の破棄や、進(jìn)む?戻るをまたぐ追加操作などを簡単に実裝できます。この點(diǎn)は「両端キュー」の章deque.md の応用節(jié)で言及されています。実際、本編は「ソフトウェアの『元に戻す』機(jī)能の中核はスタックだが、取り消し可能な手?jǐn)?shù)を 50 歩に制限する場合、スタックの底部先頭を削除する必要が生じるため、両端キューが必要になる」という例を挙げており、中核ロジックは LIFO、拡張ロジックは両端キューという分擔(dān)パターンがブラウザ履歴にも応用できる考え方です。Q2ポップした後、そのノードのメモリを解放する必要はあるのかポップしたノードを以後も使い続けるのであれば、解放してはいけません。たとえば、pop で取り出した値を後続の計(jì)算で使うケースが典型です。逆に、以後そのノードを使わない場合でも、Java?Pythonなどの言語は**自動(dòng)ガベージコレクションGC**を持つため、手動(dòng)で解放する必要はありません。參照が途切れた時(shí)點(diǎn)で GC が回収します。一方、CやCは手動(dòng)メモリ管理が必要です。C でmalloc()したノードは不要になった時(shí)點(diǎn)でfree()を、C でnewしたノードはdeleteを呼ぶ必要があります。この言語差は「組み込みのスタック/キューを持たない言語は配列や連結(jié)リストで自前実裝する」という本編の構(gòu)成とも関係し、たとえば C 版の章コードではfree()によるノード解放が実裝の一部として現(xiàn)れます。メモリ管理の有無は、使用言語を選ぶときの実務(wù)上の判斷材料の 1 つです。Q3両端キューは「2 つのスタックをつなげた」ように見えるが、用途は両端キューは、スタックとキューの組み合わせ、あるいは 2 つのスタックをつなげた構(gòu)造のように見えます。その正體は、スタックキューの論理を併せ持つデータ構(gòu)造です。したがって、スタックでできる応用もキューでできる応用もすべて実現(xiàn)でき、しかも両端から操作できる分だけ柔軟です。具體的なメリットは Q1 の例が分かりやすいでしょう。通常の undo はスタックで実現(xiàn)できますが、「取り消し可能な手?jǐn)?shù)を 50 歩に制限したい」という要件が加わると、最古の操作をスタックの底から削除する操作が必要になります。スタックは底にアクセスできないため、ここで両端キューを使えば、先頭底からの削除と末尾頂上への追加をどちらも $O(1)$ で行えます。**「やることの中核は LIFO だが、両端操作の自由度が必要」**という場面こそが両端キューの出番です。Q4取り消しundoとやり直しredoは具體的にどう実裝するのか2 つのスタックを使います。スタックAを取り消し用、スタックBをやり直し反取り消し用にしますstack.md の典型的応用でも「進(jìn)む?戻るを同時(shí)にサポートするには 2 つのスタックを組み合わせる」と説明されています。手順は summary.md の記述どおり、以下の 3 ルールに集約されます。ユーザーが操作を 1 つ実行するたびに、その操作をスタックAにプッシュし、スタックBを空にする新しい操作をした時(shí)點(diǎn)で、それ以前のやり直し履歴は無効化される。ユーザーが「取り消し」を?qū)g行したときは、スタックAから直近の操作をポップし、それをスタックBにプッシュする。ユーザーが「やり直し」を?qū)g行したときは、スタックBから直近の操作をポップし、それをスタックAにプッシュする。ポイントは**「新しい操作が入るとやり直し用スタックBがクリアされる」**というルール 1 です。これを外すと、取り消しの後に別の操作をした場合でも古い「やり直し」候補(bǔ)が殘り、履歴が不整合になります。ステップ 2?3 のポップは、スタックの基本的なpop()だけで実現(xiàn)できるため、時(shí)間計(jì)算量は各操作 $O(1)$ です。加えて、Q1?Q3 で述べたように取り消し履歴の上限を設(shè)ける設(shè)計(jì)では、スタックAの代わりに両端キューを使うことで、底最も古い操作からの削除も可能になります。復(fù)習(xí)の進(jìn)め方コード実行と演習(xí)問題この章の內(nèi)容を定著させるためのルートを紹介します?；静僮鳏蛟賹g行する日本語版 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 が付いているので単體実行して動(dòng)作を確認(rèn)できます。実裝の差分を読むと、スタックの「頭部挿入」、キューの「環(huán)狀配列と剰余演算」、両端キューの「雙方向リンク」という 3 つの設(shè)計(jì)判斷が対比して理解できます。両端キューの復(fù)習(xí)deque.md の図解雙方向連結(jié)リスト編?環(huán)狀配列編は、先頭挿入時(shí)のポインタ移動(dòng)が最も分かりやすい教材です。演習(xí)問題に挑戦するexercises.md に章全體の練習(xí)問題がまとまっています。言語を変えて同じ操作を書き直すことも、効率比較の感覚を摑むうえで有効です。なお、中國語版の同章まとめは docs/chapter_stack_and_queue/summary.md にあり、日本語版と內(nèi)容を?qū)潖辘扭堡普iみ比べることで、用語の理解をさらに深められます?；静僮?実裝?応用という流れを、本記事の要點(diǎn)と Q A で総復(fù)習(xí)すれば、この章の學(xué)習(xí)は完了です?！久赓M(fèi)下載鏈接】hello-algo《Hello 算法》動(dòng)畫圖解、一鍵運(yùn)行的數(shù)據(jù)結(jié)構(gòu)與算法教程。支持簡中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代碼實(shí)現(xiàn)項(xiàng)目地址: https://gitcode.com/GitHub_Trending/he/hello-algo創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考