5.4 まとめ¶

1. 重要なポイント¶

スタックは後入れ先出し（LIFO）の原則に従うデータ構造で、配列または連結リストを使って実装できます。
時間効率の観点では、スタックの配列実装の方が平均的な効率が高いです。ただし、拡張時には単一のプッシュ操作の時間計算量が\(O(n)\)に悪化する可能性があります。対照的に、スタックの連結リスト実装はより安定した効率を提供します。
空間効率に関しては、スタックの配列実装は一定程度の空間の無駄につながる可能性があります。ただし、連結リストのノードが占有するメモリ空間は一般的に配列の要素よりも大きいことに注意することが重要です。
キューは先入れ先出し（FIFO）の原則に従うデータ構造で、同様に配列または連結リストを使って実装できます。キューの時間と空間効率に関する結論は、スタックと似ています。
両端キュー（deque）はより柔軟なキューの種類で、両端での要素の追加と削除を可能にします。

2. Q & A¶

Q: ブラウザの進む・戻る機能は双方向連結リストで実装されているのですか？

ブラウザの進む・戻るナビゲーションは本質的に「スタック」概念の現れです。ユーザーが新しいページを訪問すると、そのページがスタックの先頭に追加されます。戻るボタンをクリックすると、ページがスタックの先頭からポップされます。両端キュー（deque）は、「両端キュー」の章で述べたように、いくつかの追加操作を便利に実装できます。

Q: スタックからポップした後、ポップされたノードのメモリを解放する必要がありますか？

ポップされたノードが後で使用される場合は、そのメモリを解放する必要はありません。自動ガベージコレクションを持つJavaやPythonなどの言語では、手動のメモリ解放は必要ありません。CやC++では、手動のメモリ解放が必要です。

Q: 両端キューは2つのスタックを結合したもののように見えます。その用途は何ですか？

両端キューは、スタックとキューの組み合わせまたは2つのスタックを結合したもので、スタックとキューの両方のロジックを示します。したがって、スタックとキューのすべてのアプリケーションを実装でき、より大きな柔軟性を提供します。

Q: 元に戻すとやり直しは具体的にどのように実装されるのですか？

元に戻すとやり直しの操作は2つのスタックを使って実装されます：元に戻す用のスタックAとやり直し用のスタックBです。

ユーザーが操作を実行するたびに、それがスタックAにプッシュされ、スタックBがクリアされます。
ユーザーが「元に戻す」を実行すると、最新の操作がスタックAからポップされ、スタックBにプッシュされます。
ユーザーが「やり直し」を実行すると、最新の操作がスタックBからポップされ、スタックAに戻されます。