5.4 まとめ¶

スタックは先入れ後出しの原則に従うデータ構造であり、配列や連結リストで実装できます。
時間効率では、配列によるスタックの実装は平均的な効率が高いものの、容量拡張時には一回のプッシュの時間計算量が \(O(n)\) に悪化します。これに対し、連結リストによる実装は、より安定した効率を示します。
空間効率では、配列によるスタックの実装はある程度の領域の無駄を生じる可能性があります。ただし、連結リストのノードが占めるメモリは配列の要素より大きい点に注意が必要です。
キューは先入れ先出しの原則に従うデータ構造であり、同じく配列や連結リストで実装できます。時間効率と空間効率の比較については、前述のスタックと同様の結論になります。
両端キューは自由度の高いキューであり、両端で要素を追加したり削除したりできます。

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

ブラウザの進む・戻る機能は、本質的に「スタック」の仕組みを表しています。新しいページを開くと、そのページがスタックの先頭に追加され、戻るボタンを押すと、先頭から取り出されます。両端キューを使うと、一部の追加操作も容易に実装できます。これについては「両端キュー」の節で触れています。

Q：ポップした後は、取り出したノードのメモリを解放する必要がありますか？

その後も取り出したノードを使うなら、メモリを解放する必要はありません。使わなくなった場合、Java や Python などには自動ガベージコレクションがあるため、手動での解放は不要です。C と C++ では手動でメモリを解放する必要があります。

Q：両端キューは二つのスタックをつなげたように見えますが、どのような用途がありますか？

両端キューはスタックとキューの組み合わせ、あるいは二つのスタックをつなげたものに似ています。スタックとキューの両方の論理を持つため、それらのすべての用途を実現でき、さらに柔軟性も高いです。

Q：元に戻す（undo）とやり直す（redo）は、具体的にどう実装しますか？

二つのスタックを使い、スタック A を元に戻す操作に、スタック B をやり直す操作に用います。