stack

stack とは特徴としてLIFO( "last-in" ,"first-out")のデータ構造をもっているAbstract Data Type (ADT) である。 このクラス（構造体）はたいてい、push ,pop ,top ,is_empty,(is_full)などの関数をもっている。 スタックには大きく分けてに種類あり、bounded stack とunbouded stack の実装がある。 一般的にunboundedの実装のほうが複雑になりがちだ。

Bounded stack

まずBounded stackについて。 これは配列の長さが固定(bounded）さてているstackという意味だ 実装はほとんどTrivialだろう

Unbounded stack

動的メモリを用いた長さが固定されていない(Unbounded)スタック*1。 ほとんどインターフェイスはBounded stackと変わりないが、動的なメモリ確保を行う.

*1:もちろんUnbounded とはいってもメモリに限りがあるので、その意味ではスタックの深さ（高さというべきか？）には上限がある。こちらは正しく実装しようと思うと結構大変