「スタック・キュー」(2012/03/13 (火) 10:41:07) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
**スタック・キュー
(画像などを入れて解説してくれると助かります。私はうまいこと画像を用意できませんorz あと、読みづらいところ、間違ってるところあったらバッサリ書き換えちゃっていいですよ。)
***スタック
''スタック'' (stack) とはデータ構造の一つです。スタックにデータを追加することを''プッシュ'' (push) と言い、スタックからデータを取り出すことを''ポップ'' (pop) と言います。後にプッシュしたデータほど先にポップされるという特徴があります。これを Last In, First Out (LIFO) といいます。
イメージとしては、筒を思い浮かべるとわかりやすいと思います。ここでいう筒とは、有限長の円柱や多角柱の一方の端に、その角柱の断面と同形状の壁がついているもののことをいいます。筒の開いている端から物を入れていくと、先に入れた物ほど後で取り出せ、後に入れた物ほど先に取り出せるのがわかると思います。
#region(close, プログラム例)
/* stack coded by Korinku */
#include <iostream>
#include <cstdlib>
#include <string>
#define SIZEMAX 64
template <typename T>
class stack_t{
T data[SIZEMAX];
int p;
public:
stack_t(){ /* constractor で初期化 */
p = 0;
}
bool push(T inp){ /* 引数は push 入力、戻値は成功したら1失敗したら0 */
if(p < SIZEMAX){
data[p] = inp;
++p;
return true;
}
return false;
}
void pop(void){ /* ポップする。 (データは得られない。データがほしければ top()。) */
if(p > 0) {
--p;
}
}
T top(void){ /* 一番上のデータを返す。 */
if(p > 0){
return data[p - 1];
}
return 0;
}
bool empty(void){
return p <= 0;
}
void view(void){
std::cout << ((p > 0) ? "pointer\tdata\n" : "no data\n");
for(int i = p - 1; i >= 0; --i) {
std::cout << i << "\t" << data[i] << "\n";
}
}
};
int main(int argc, char *argv[]){
std::string str, usage = "数字を入力すると push\np で pop\nv で表示\nq で終了\n";
stack_t<int> sta;
std::cout << "* STACK *\n";
std::cout << usage; /* まず使い方を表示 */
while(1){
std::cout << "\nyou>";
getline(std::cin, str);
if(str[0] >= '0' && str[0] <= '9' || str[0] == '-' && str[1] >= '0' && str[1] <= '9'){
if(sta.push(atoi(str.c_str())) == 0){
std::cout << "ERROR : スタック領域が足りません。\n";
} else {
std::cout << "push " << atoi(str.c_str()) << '\n';
}
}else if(str[0] == 'p'){
if(sta.empty()) {
std::cout << "ERROR : もうスタックはないよ（´・ω・｀）\n";
} else {
std::cout << sta.top() << '\n';
sta.pop();
}
}else if(str[0] == 'v'){
sta.view();
}else if(str[0] == 'q'){
break;
}else{
std::cout << usage;
}
}
return 0;
}
#endregion
なお、スタックは C++ の STL ですでに実装されています。 STL のスタックを使うときは、
#include <stack>
でクラステンプレートを読み込み、
stack<データ型> スタック変数名
で実際にスタックを使います。
プッシュは
スタック変数名.push(データ)
一番上のデータを調べるときは
スタック変数名.top()
ポップは
スタック変数名.pop()
です。
***キュー
''キュー'' (queue) もデータ構造の一つです。キューにデータを追加することを''エンキュー'' (enqueue) と言い、キューからデータを取り出すことを''デキュー'' (dequeue) と言います。先にエンキューしたデータほど先にデキューされるという特徴があります。これを First In, First Out (FIFO) と言います。
なお、キューは C++ の STL で実装されています。 STL のキューを使うときは、
#include <queue>
でクラステンプレートを読み込み。
queue<データ型> キュー変数名
で実際にキューを使います。
STL のキューはメソッド名がスタックと同じで、 push でエンキュー、 pop でデキューとなっています。
キュー変数名.push(データ) // エンキュー
キュー変数名.pop() // デキュー
また、先頭のデータ (デキューすると取り出されるデータ) を返すメソッドは front() で、末尾のデータ (直前にエンキューされたデータ) を返すメソッドは back() です。
キュー変数名.front() // 直前にエンキューされたデータ
キュー変数名.back() // デキューすると取り出されるデータ
...
**スタック・キュー
(画像などを入れて解説してくれると助かります。私はうまいこと画像を用意できませんorz あと、読みづらいところ、間違ってるところあったらバッサリ書き換えちゃっていいですよ。)
***スタック
''スタック'' (stack) とはデータ構造の一つです。スタックにデータを追加することを''プッシュ'' (push) と言い、スタックからデータを取り出すことを''ポップ'' (pop) と言います。後にプッシュしたデータほど先にポップされるという特徴があります。これを Last In, First Out (LIFO) といいます。
イメージとしては、筒を思い浮かべるとわかりやすいと思います。ここでいう筒とは、有限長の円柱や多角柱の一方の端に、その角柱の断面と同形状の壁がついているもののことをいいます。筒の開いている端から物を入れていくと、先に入れた物ほど後で取り出せ、後に入れた物ほど先に取り出せるのがわかると思います。
#image(stack.png,width=400,height=300)
なお、スタックは C++ の STL ですでに実装されています。 STL のスタックを使うときは、
#include <stack>
でクラステンプレートを読み込み、
std::stack<データ型> スタック変数名
で実際にスタックを使います。
プッシュは
スタック変数名.push(データ)
一番上のデータを調べるときは
スタック変数名.top()
ポップは
スタック変数名.pop()
です。
***キュー
''キュー'' (queue) もデータ構造の一つです。キューにデータを追加することを''エンキュー'' (enqueue) と言い、キューからデータを取り出すことを''デキュー'' (dequeue) と言います。先にエンキューしたデータほど先にデキューされるという特徴があります。これを First In, First Out (FIFO) と言います。
イメージとしては、レジの待ち行列を思い浮かべるとわかりやすいと思います。順番に並んでいて、先に並んだ人が先にレジのサービスを受けられるのがわかると思います。(横入りなどはないものとします)
#image(queue.png,width=400,height=300)
なお、キューは C++ の STL で実装されています。STL のキューを使うときは、
#include <queue>
でクラステンプレートを読み込み。
std::queue<データ型> キュー変数名
で実際にキューを使います。
STL のキューはメソッド名がスタックと同じで、push でエンキュー、pop でデキューとなっています。
キュー変数名.push(データ) // エンキュー
キュー変数名.pop() // デキュー
また、先頭のデータ (デキューすると取り出されるデータ) を返すメソッドは front() で、末尾のデータ (直前にエンキューされたデータ) を返すメソッドは back() です。
キュー変数名.front() // 直前にエンキューされたデータ
キュー変数名.back() // デキューすると取り出されるデータ
...
表示オプション
横に並べて表示：
変化行の前後のみ表示：
