スタック(Stack)

データ構造スタック

スタックとは

線形なデータ構造の1つです。データを格納する操作(push)と取り出す操作(pop)について、対象になるデータの順番が決められています。

スタックは、最後に格納したデータが最初に出てくるようなデータ構造をしています。このような順序をLIFO(Last In First Out) もしくは FILO(First In Last Out)と言います。

データを積み重ねていき、取り出したいときは一番上のものから取っていくイメージなので、スタックと呼ばるのです。

スタックの例

\(8,11,4,9,22\)を1つずつスタックに入れると、取り出すときは最後に入れたものから出てくるので、\(22,9,4,11,8\)の順に出てきます。

スタック(stack)の図

プログラム例

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;
}

データ構造スタック

Posted by cs-learner