さまざまなデータ構造（４）スタック１
こんにちは。引き続きデータ構造について書いていきます。今回はスタックです。
スタックとは
机の上を見てください。ほ～ら、本やらプリントやら山積みになっているでしょう。まさにスタックです。え、きれいに整っていて山積みになってなんかいないですか。すみません。すべての人が私と同じと考えてはいけませんでした。私も片付けることにします。
一番上だけを見たり触ったりすることができる山積みのものと考えてください。図にすると、次のようなものです。
結局、一方向につながっているので、前回実装した連結リストを使ってしまおうと思います。
構造を見るとわかりますが、最後に入れたものが最初に取り出せます。Last In First Outの頭文字を並べて、LIFOといいます。
すでにＪａｖａにスタックがありますよ
そうなんです。わざわざ自分でスタックを作らなくても、すでにＪａｖａならばjava.utilというパッケージを読み込んでしまえば、スタックがあるんです。リンクをはっておきます。
https://docs.oracle.com/javase/jp/6/api/java/util/Stack.htmlとはいえ、車輪の再開発です。ちゃんと手順をたどっていくことで、データ構造を学ぼうとする人のためにも、考え方が分かるようにしようと思います。
って展開をどこかで見たような・・・
スタック（サブセット版）で実装するメソッド
先ほどのオラクルのドキュメントを見ると、案外メソッドが少ないようです。それなのにすべてを実装しないで進めようと思います。スタックとして実装するメソッドは先頭に関係するものだけにします。実装するメソッドは
boolean empty() スタックが空かどうかを判定する
E peek() スタックの先頭にあるオブジェクトを取り出す（何が先頭にあるかを見るだけ）
E pop() スタックの先頭のオブジェクトを削除し、そのオブジェクトを関数の値として返す（先頭にあるものを取り出して、除いてしまう）
void push(E element) スタックの先頭にオブジェクトを入れる（先頭のものの上にelementを乗せる、特に理由はありませんがvoidにしてみます）
にします。自分で選んだメソッドを実装したスタックという意味でMyStackクラスと呼ぶことにします。
スタックの実装
コンストラクタ
インスタンス変数として、連結リストを用意すれば連結リストで作ったメソッドも使うことができます。コンストラクタでは、空の連結リストを作ります。簡単なプログラムは次になります。
private MyLinkedList<E> myList;
public MyStack() {
myList = new MyLinkedList<E>();
}
empty()
スタックが空かどうかを返すメソッドです。連結リストの大きさが0かどうかを調べて返せば判定できます。
簡単なプログラムを書くとこんな感じです。
return myList.size() == 0;
peek()
スタックの一番上のものを調べるメソッドです。連結リストの０番目が得て戻り値にすれば大丈夫です。
簡単なプログラムはこんな感じです。
return myList.get(0);
pop()
peek()とほとんど同じですが、一番上のノードを取り除きます。言い換えると、peek()してremove(0)です。
簡単なプログラムも載せておきます。
E result = peek();
myList.remove(0);
return result;
push(E element)
一番上にノードを追加します。連結リストでは、add(0,element)をすれば実装できます。
簡単なプログラムは次になります。
myList.add(0, element);
stackクラス全体のプログラムは次回書きます。今回はこれでおしまい。それではまた。