秋田大学ICPC対策室@wiki

スタック・キュー

最終更新:

loxyplst

- view
だれでも歓迎! 編集

スタック・キュー

(画像などを入れて解説してくれると助かります。私はうまいこと画像を用意できませんorz あと、読みづらいところ、間違ってるところあったらバッサリ書き換えちゃっていいですよ。)

スタック

スタック (stack) とはデータ構造の一つです。スタックにデータを追加することをプッシュ (push) と言い、スタックからデータを取り出すことをポップ (pop) と言います。後にプッシュしたデータほど先にポップされるという特徴があります。これを Last In, First Out (LIFO) といいます。

イメージとしては、筒を思い浮かべるとわかりやすいと思います。ここでいう筒とは、有限長の円柱や多角柱の一方の端に、その角柱の断面と同形状の壁がついているもののことをいいます。筒の開いている端から物を入れていくと、先に入れた物ほど後で取り出せ、後に入れた物ほど先に取り出せるのがわかると思います。


なお、スタックは C++ の STL ですでに実装されています。 STL のスタックを使うときは、
#include <stack>
でクラステンプレートを読み込み、
std::stack<データ型> スタック変数名
で実際にスタックを使います。
プッシュは
スタック変数名.push(データ)
一番上のデータを調べるときは
スタック変数名.top()
ポップは
スタック変数名.pop()
です。

キュー

キュー (queue) もデータ構造の一つです。キューにデータを追加することをエンキュー (enqueue) と言い、キューからデータを取り出すことをデキュー (dequeue) と言います。先にエンキューしたデータほど先にデキューされるという特徴があります。これを First In, First Out (FIFO) と言います。

イメージとしては、レジの待ち行列を思い浮かべるとわかりやすいと思います。順番に並んでいて、先に並んだ人が先にレジのサービスを受けられるのがわかると思います。(横入りなどはないものとします)


なお、キューは C++ の STL で実装されています。STL のキューを使うときは、
#include <queue>
でクラステンプレートを読み込み。
std::queue<データ型> キュー変数名
で実際にキューを使います。
STL のキューはメソッド名がスタックと同じで、push でエンキュー、pop でデキューとなっています。
キュー変数名.push(データ)	// エンキュー
キュー変数名.pop()	// デキュー
また、先頭のデータ (デキューすると取り出されるデータ) を返すメソッドは front() で、末尾のデータ (直前にエンキューされたデータ) を返すメソッドは back() です。
キュー変数名.front()	// 直前にエンキューされたデータ
キュー変数名.back()	// デキューすると取り出されるデータ




















...
添付ファイル