スタック(Stack)のデータ構造

2019年11月25日データ構造スタック, データ構造

スタックとは

線形なデータ構造の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の最後尾がスタックの頂上部だとみなしています。

C++

C++ではライブラリでstackが提供されています。

もしくは、vectorをstackの代わりに使用することができます。これは最後尾をスタックの頂上部とみなしています。