基本的なデータ構造の一つであるスタックについて、図を用いて解説します。
スタックと関わりのあるリストについてまず説明していきます。
リストとは
0以上の要素を、決めた順序で一列に並べて表現をしたものです。
ただ「リスト」と言われるものは連結リストを示すことが多いです。
ポインタで次の要素の格納領域を指して、データを連結して扱います。
先頭の要素は、リストヘッドと呼ばれる(topと書かれている部分)ものに格納される。
それ以降のアドレスは、変数a1の要素とは別に、次のアドレスの位置を格納する場所がある。
配列も同じくデータをまとめるものですが、リストを使うメリットは以下になります。
メモリの使用効率が良い！（配列と違って連続領域を確保する必要がないため）
スタックとは
それではメインの話のスタックとは何かについて解説します。
スタックとは、「要素の入り口と出口が一つしかないリスト」のことを指します。
他にもLIFO(Last-In First-Out)と呼ばれたりします。
つまり、簡単に説明すると、
一番最後に入れたものが一番最初に取り出すことのできる構造
ということです。
スタックの基本操作
基本操作は3つありますので、それぞれ見ていきましょう。
トップ(TOP)
スタックの先頭の位置がどこかを示します。
データが何も入ってない状態を0として、1つ入るごとに１ずつ増えていきます。
つまり、現在何個のデータが入っているのかがわかります。
この状態だとトップは１となります。
プッシュ(PUSH)
スタックにデータを格納します。
ここでは、データAがすでに入っていて、データBをプッシュしようとしています。
ポップ(POP)
スタックからデータを取り出します。
つまり、一番上に格納されているデータを取ります。
ここでは、データBが取り出されます。
データAを取り出そうとすると、データBを先に取り出してからじゃないといけないことに注意してください。
まとめ
今回はデータ構造の基本的な構造の一つであるスタックについて解説しました！
一番最後に入れたものが一番最初に取り出せる
ということさえ覚えておけば大丈夫です！
