スタック(Stack)のデータ構造
スタックとは
線形なデータ構造の１つです。データを格納する操作(push)と取り出す操作(pop)について、対象になるデータの順番が決められています。
スタックは、最後に格納したデータが最初に出てくるようなデータ構造をしています。このような順序をLIFO(Last In First Out) もしくは FILO(First In Last Out)と言います。
データを積み重ねていき、取り出したいときは一番上のものから取っていくイメージなので、スタックと呼ばるのです。
スタックの例
\(8,11,4,9,22\)を１つずつスタックに入れると、取り出すときは最後に入れたものから出てくるので、\(22,9,4,11,8\)の順に出てきます。
プログラム例
Python
Pythonではlistをstackの代わりに使うことができます。これはlistの最後尾がスタックの頂上部だとみなしています。
stack = []
stack.append(8) # pushの代わりにappendを使用する
stack.append(11)
stack.append(4)
stack.append(9)
stack.append(22)
print(stack)
element = stack.pop() # 22が取り出される
print(element)
element = stack.pop() # 9が取り出される
print(element)
print(stack)C++
C++ではライブラリでstackが提供されています。
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
s.push(8);
s.push(11);
s.push(4);
s.push(9);
s.push(22);
cout << s.top() << "\n"; // 22が出力
s.pop(); // 22が消される
cout << s.top() << "\n"; // 9が出力
s.pop(); // 9が消される
cout << s.top() << "\n"; // 4が出力
s.pop(); // 4が消される
cout << s.top() << "\n"; // 11が出力
s.pop(); // 11が消される
cout << s.top() << "\n"; // 8が出力
s.pop(); // 8が消される
return 0;
}もしくは、vectorをstackの代わりに使用することができます。これは最後尾をスタックの頂上部とみなしています。
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> s;
s.push_back(8);
s.push_back(11);
s.push_back(4);
s.push_back(9);
s.push_back(22);
cout << s.back() << "\n"; // 22が出力
s.pop_back(); // 22が消される
cout << s.back() << "\n"; // 9が出力
s.pop_back(); // 9が消される
cout << s.back() << "\n"; // 4が出力
s.pop_back(); // 4が消される
cout << s.back() << "\n"; // 11が出力
s.pop_back(); // 11が消される
cout << s.back() << "\n"; // 8が出力
s.pop_back(); // 8が消される
return 0;
}