スタック

データ構造のスタックは、後入れ先出し【LIFO：Last-In, First-Out】の方式で要素を追加・削除することができるデータ構造です。

後入れ先出しとはその名の通り、後に入れたものが先に出されるデータ構造をいいます。

例えば、本棚の一番上に書籍を重ねていく場合を考えてみましょう。最初に置かれた書籍は本棚の底にあり、その上に順番に書籍が重ねられます。最後に重ねられた書籍が一番上にくるため、最後に置いた書籍から順に取り出すことができます。スタックも同様で、新しい要素は常にトップに追加され、トップから取り出されます。

スタックでは、新しい要素は常にスタックのトップに追加されます。スタックのトップにある要素は、最後に追加された要素であり、スタックから削除される要素も同じ要素です。それぞれプッシュ【push】とポップ【pop】操作で実現されます。

スタックは、再帰的なアルゴリズムなど様々なアプリケーションで使用されます。また、関数の呼び出しや式の評価など、プログラミングにおいてもよく使われます。

以下はスタックの利用例です。

• 関数呼び出し：関数を呼び出すと、関数がスタックにプッシュされます。関数が終了すると、スタックからポップされます。この方法により、プログラムがどこに戻る必要があるかを追跡できます。
• ブラウザ履歴：ブラウザの「戻る」ボタンをクリックすると、前のページに戻ります。この機能は、スタックを使用して実装されています。現在のページがスタックにプッシュされ、前のページがポップされます。
• 式の評価：数式の評価中に、演算子をスタックにプッシュします。演算子の優先順位を考慮して、スタックから演算子をポップして式を評価します。
• メモリの割り当て：プログラムがメモリを使用するとき、メモリの割り当てはスタックによって管理されます。新しいメモリが必要な場合、スタックから空いている領域が取り出されます。

スタックは、プログラミングやコンピュータサイエンスにおいて、多くの場面で使用される便利なデータ構造の1つです。

スタックを配列を使って実装する

＜サンプルプログラム＞

なお、単にスタックを利用するなら以下のjava.util.Stackを使うほうが便利です。

java.util.Stack

Javaの java.util.Stack クラスは、スタックを実装するためのクラスで、LIFO（後入れ先出し）のデータ構造を提供します。以下は、 java.util.Stack クラスで使用できる主なメソッドの一覧です。

• push(E element)：スタックに要素をプッシュします。
• pop()：スタックから要素をポップし、その要素を返します。
• peek()：スタックのトップ要素を返しますが、削除しません。
• empty()：スタックが空であるかどうかを返します。

＜サンプルプログラム＞

＜出力結果＞

ポップした要素: kiyome トップ要素: habutai スタックは空ですか？ false

練習問題

基本情報技術者試験 令和元年秋期 午前問8

練習問題

基本情報技術者試験 平成24年春期 午前問6