5.4 まとめ¶
1. 要点の振り返り¶
- スタックは後入れ先出しの原則に従うデータ構造であり、配列または連結リストで実装できます。
- 時間効率の面では、スタックの配列実装は平均効率が高い一方、拡張時には 1 回のプッシュ操作の時間計算量が \(O(n)\) まで悪化します。これに対して、スタックの連結リスト実装はより安定した効率を示します。
- 空間効率の面では、スタックの配列実装はある程度の領域の無駄を生む可能性があります。ただし、連結リストのノードが占有するメモリは配列要素よりも大きい点に注意が必要です。
- キューは先入れ先出しの原則に従うデータ構造であり、同様に配列または連結リストで実装できます。時間効率と空間効率の比較における結論は、前述のスタックの場合と似ています。
- 両端キューはより高い自由度を持つキューであり、両端で要素の追加と削除を行えます。
2. Q & A¶
Q：ブラウザの進む・戻るは双方向連結リストで実装されているのですか？
ブラウザの進む・戻る機能の本質は「スタック」の表れです。ユーザーが新しいページにアクセスすると、そのページはスタックの先頭に追加されます。ユーザーが戻るボタンをクリックすると、そのページはスタックの先頭から取り出されます。両端キューを使うといくつかの追加操作を簡単に実装でき、この点は「両端キュー」の章で触れています。
Q：ポップした後、そのノードのメモリを解放する必要はありますか？
後で取り出したノードを引き続き使うのであれば、メモリを解放する必要はありません。以降そのノードを使わない場合でも、Java や Python などの言語には自動ガベージコレクション機構があるため、手動でメモリを解放する必要はありません。一方、C と C++ では手動でメモリを解放する必要があります。
Q：両端キューは 2 つのスタックをつなげたように見えますが、用途は何ですか？
両端キューは、スタックとキューの組み合わせ、あるいは 2 つのスタックをつなげたもののような構造です。表しているのはスタック + キューのロジックなので、スタックとキューのすべての応用を実現でき、しかもより柔軟です。
Q：取り消し（undo）とやり直し（redo）は具体的にどのように実装されますか？
2 つのスタックを使い、スタック A を取り消し用、スタック B をやり直し用に使います。
- ユーザーが操作を 1 つ実行するたびに、その操作をスタック
Aにプッシュし、スタックBを空にします。 - ユーザーが「取り消し」を実行したときは、スタック
Aから直近の操作をポップし、それをスタックBにプッシュします。 - ユーザーが「やり直し」を実行したときは、スタック
Bから直近の操作をポップし、それをスタックAにプッシュします。