[Java] スタック・キューのメモ

目的

• Javaのコレクションフレームワークの１つである スタック・キュー について、整理してみます。
• 各クラスやメソッドの詳細な説明はしません。

関連するインタフェース・クラス

java.util.Queue

キュー専用のインタフェース。
一般的にキューといえば FIFO だと思います。
しかし Javadoc では Queue の実装として FIFO 以外のものがあっても良いとしています。

Javadoc であげられている実装例は３種類あります。

• FIFO (First In First Out) ： 一般的なキュー
• LIFO (Last In First Out) ： スタックをキューとして扱う場合
• プライオリティキュー ： 優先順位を持つキュー

java.util.Deque

両端キュー。スタックとキューの両方として扱えます。
Queue インタフェースを拡張したもの。

Javadoc によると「デック」と読むらしい。

java.util.LinkedList

双方向線形リスト。
線形リストなので、末端要素の追加・削除はお手の物。
もちろん Deque を実装しているので、スタックとしてもキューとしても扱える。

java.util.ArrayDeque

配列型の Deque の実装クラス。
先頭の要素を削除しても、配列のコピーが発生しないようにいろいろ工夫されているみたい。
ただし、途中の要素を削除するのは苦手っぽい（そんなときは LinkedList かな）。

java.util.PriorityQueue

Comparator や自然な順序付けで優先順位を求める優先キュー。

java.util.Stack

名前は一般的ですが、古いコレクションフレームワークのものなので、基本は使用しないと思います。
このクラスは Queue も Deque も実装していないことに注意してください。

java.util.Collections#asLifoQueue()

これはインタフェースでもクラスでもありませんが。
Deque のインスタンスを LIFO のキューに変換するアダプタメソッドです。
前述の LIFO のキューがほしい場合に使えます。

java.util.concurrent.BlockingDeque

空の場合に、要素が別のスレッドから追加されるまでブロックすることができる Deque のインタフェースです。
類似のものに java.util.concurrent.BlockingQueue があります。

また、その実装クラスも java.util.concurrent パッケージにあります。

主な操作メソッド

キュー用のメソッド

FIFO の場合、基本的に末尾に追加して、先頭から取り出します。
強調表示のメソッドが Queue インタフェースで定義されているものです。

操作	失敗時例外	戻り値判定
末尾に追加	addLast(), add()	offerLast(), offer()
先頭から削除	removeFirst(), remove()	pollFirst(), poll()
先頭を取得（削除しない）	getFirst(), element()	peekFirst(), peek()

スタック用のメソッド

スタックは基本的に LIFO です。
先頭に追加して、先頭から取り出します。
強調表示のメソッドは古いフレームワークの Stack でも使われていたものです。

操作	失敗時例外	戻り値判定
先頭に追加	addFirst(), push()	offerFirst()
先頭から削除	removeFirst(), pop()	pollFirst()
先頭を取得（削除しない）	getFirst()	peekFirst(), peek()

Deque のメソッド整理

Deque のメソッドは Queue と Stack のメソッドを集約しており、さらに直交性の高いメソッド名を用意しているため、異なる名前で同じ意味のメソッドがあります。

操作	失敗時例外	戻り値判定
先頭に追加	addFirst(), push()	offerFirst()
末尾に追加	addLast(), add()	offerLast(), offer()
先頭から削除	removeFirst(), remove(), pop()	pollFirst(), poll()
末尾から削除	removeLast()	pollLast()
先頭を取得（削除しない）	getFirst(), element()	peekFirst(), peek()
末尾を取得（削除しない）	getLast()	peekLast()