stackとは
スタックは末尾(または先頭)に限って要素の追加削除を行うことのできるデータ構造です。
末尾からしか要素を取り出せないので、
必然的に「後に入れたものから先に取り出さなくてなはならない」ということになります。
そのため、スタックはLIFO(last-in first-out)とも呼ばれます。
スタックに新しい要素を挿入することをpush、要素を取り出すことをpopといいます。
スタックは末尾への要素の挿入・削除ができるデータ構造なら何を使っても実装することができます。 普通は配列や単方向連結リストを用いて実装します。
STLにおけるstack
STLのstackは何を使って実装するかをvector,deque,listの中から選べます。 スタックの要素の型をTとすると、
stack<T, vector<T> > | vectorによるstack |
stack<T, deque<T> > | dequeによるstack |
stack<T, list<T> > | listによるstack |
stack<T> | stack<T, vector<T> >と同じ意味 |
他にも、push_back, pop_back, back, sizeなどのメソッドを適当に定義したクラスなら
何でもスタックの実装に使えます。
