stackの実装

問題：以下がO(1)のstackを実装する．
・pop (LastInの要素を取り出す)
・push(要素を取り出す)
・min(最小値の要素を取り出す)

え，全部O(1)?.....
①最初に思いついた方針は，スタックに最小値のメンバーを追加すること．
然し，minが呼ばれたあとに，stack内の要素全てと比べないと行けないので，スタック内部がソートされていなければ，O(n)，ソートされていたとしても，O(logn)の計算量はかかる．
②次に考えたのは，ノードに，最小値のノードのポインタを追加すること．(popやpush時に逆引き処理出来るように，逆向きのポインタも追加)
然し，この場合はpush時に，pushした要素がスタック内で何番目に小さいのかを探索しないといけないので結局O(logn)の計算量．

んー全部O(1）無理やろー!
ということで悩んだ挙句，調べる．情けない

問題の読み違いだった．
問題：以下がO(1)のstackを実装する．
・pop (LastInの要素を取り出す)
・push(要素を取り出す)
・min(最小値の要素を取り出す返す)

minに関しては，要素は取り出さなくて値を返すだけで良いとのこと．
なるほど．ということで「ノードにその時点での最小値を持っておけばよい」で解決．