さまざまなデータ構造（６）キュー１

データ構造

こんにちは。引き続きデータ構造について書いていきます。今回はキューです。

キューとは

人気のラーメン屋に並んだことはありますか？私はあります。1時間くらい待ったかな～。待ち行列がキューです。ということで、私自身もキューを構成する一員を経験していたのですね。

一番先頭と一番最後だけを見たり触ったりすることができるものと考えてください。待ち時間が長いからといって、途中で抜けるのはナシです。図にすると、次のようなものです。

結局、一方向につながっているので、前回実装した連結リストを使ってしまおうと思います。

構造を見るとわかりますが、最初に入れたものが最初に取り出せます。First In First Outの頭文字を並べて、FIFOといいます。

すでにＪａｖａにキューがありますよ

そうなんです。わざわざ自分でキューを作らなくても、すでにＪａｖａならばjava.utilというパッケージを読み込んでしまえば、キューがあるんです。リンクをはっておきます。

とはいえ、車輪の再開発です。ちゃんと手順をたどっていくことで、データ構造を学ぼうとする人のためにも、考え方が分かるようにしようと思います。

って展開をどこかで見たような・・・

キュー（サブセット版）で実装するメソッド

先ほどのオラクルのドキュメントを見ると、案外メソッドが少ないようです。それなのにすべてを実装しないで進めようと思います。キューとして実装するメソッドは先頭に関係するものだけにします。実装するメソッドは

void offer(E elemetnt)　キューの最後尾に新しいノードを追加する

E peek()　キューの先頭にあるオブジェクトを取り出す（何が先頭にあるかを見るだけ）

E poll()　キューの先頭のオブジェクトを削除し、そのオブジェクトを関数の値として返す（先頭にあるものを取り出して、除いてしまう）

にします。この他に継承されたメソッドのうち、

isEmpty()　キューが空のときTrue、空でないときFalseを返す

も実装します。

自分で選んだメソッドを実装したスタックという意味でMyQueueクラスと呼ぶことにします。

キューの実装

コンストラクタ

インスタンス変数として、連結リストを用意すれば連結リストで作ったメソッドも使うことができます。コンストラクタでは、空の連結リストを作ります。簡単なプログラムは次になります。

private MyLinkedList<E> myList;

public MyQueue() {
	myList = new MyLinkedList<E>();
}

offer(E element)

キューにelementを追加するメソッドです。連結リストのheadの先が最後尾ということにします。ここに新しいノードを追加すれば大丈夫です。

簡単なプログラムを書くとこんな感じです。

myList.add(0, element);

myList.add(0, element);

peek()

キューの先頭のものを調べるメソッドです。連結リストの一番先につながっているノードの値を戻り値にすれば大丈夫です。

簡単なプログラムはこんな感じです。マイナス１しているのは、伊藤さんが０番目、田中さんが1番目、・・・と０から数え始める（０オリジン）ためです。

return myList.get(myList.size() - 1);

poll()

peek()とほとんど同じですが、一番先につながっているノードを取り除きます。言い換えると、peek()してremove(myList.size()-1)です。マイナス１しているのは、０オリジンにしているためです。

簡単なプログラムも載せておきます。

E result = peek();
myList.remove(myList.size() - 1);
return result;

今回は、headの直後を最後尾にしましたが、逆順でも実装できます。上のように実装したのは、toString()メソッドを書き直さなくても、矢印の向きが自然に見えたからです。

isEmpty()

これはmyListの大きさが0であるかどうか調べれば求められます。簡単なプログラムは次になります。

return myList.size() == 0;

MyQueueクラス全体のプログラムは次回書きます。今回はこれでおしまい。それではまた。

Posted by 春日井 優