連結リストとキュー
今回は簡単な例題として「キュー (queue)」という基本的なデータ構造を取り上げます。キューは配列や連結リストを使って簡単に実装することができます。今回は連結リストを使うことにしましょう。なお、Java の標準ライブラリには Queue というインターフェースが用意されているので、私たちがキューを自作する必要はありませんが、Java とデータ構造のお勉強ということで、あえてプログラムを作ってみましょう。
●キューとは？
キューは「待ち行列」といわれるデータ構造です。たとえばチケットを買う場合、カウンタの前に並んで順番を待たなくてはいけません。キューはカウンタの前に並ぶ行列と考えてください。列の先頭にいる人から順番にチケットを買うことができますが、あとから来た人は列の後ろに並ばなくてはいけません。列の先頭まで進むと、チケットを購入することができます。これを図に表すと次のようになります。
図 : キューの動作
このように、キューはデータを取り出すときは列の先頭から行い、データを追加するときは列の後ろへ行います。このため、キューは「先入れ先出し (FIFO : first-in, first-out)」とも呼ばれます。
リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。
たとえば、データの追加に append() を使うと、データを追加するたびにリスト (キュー) がコピーされてしまいます。このため、キューに格納されているデータが多くなると実行時間がかかるようになります。そこで、append() の代わりに最後尾のセルを破壊的に修正して、新しいデータを追加することを考えてみます。この場合、リストのコピーは回避できますが、最後尾のセルは先頭から順番にセルをたどっていかないと到達できないので、データが多くなるとやっぱり時間がかかってしまいます。
そこで、最後尾のセルを格納する変数を用意することにします。こうすると、先頭からセルをたどらなくても、最後尾にデータを追加することができます。次の図を見てください。
図 : キューの構造
この変数を head と tail としましょう。キューにデータがない場合は、(1) のように head と tail は null になっています。データがある場合は、(2) のように head は先頭のセルを参照し、tail は最後尾のセルを参照しています。これで、データの追加を効率的に行うことができます。
●クラス Queue<E> の仕様
それではプログラムを作りましょう。最初にクラスの仕様を下表に示します。
| メソッド | 機能 |
|---|---|
| new Queue() | 空のキューを生成する |
| boolean add(E x) | キューに x を追加する |
| E remove() | キューから先頭要素を削除して返す |
| E element() | キューの先頭要素を参照する |
| boolean isEmpty() | キューが空ならば true を返す |
| int size() | キューの要素数を求める |
| void clear() | キューを空にする |
クラス名は Queue とします。データの追加は add() で、先頭要素の削除は remove() で、先頭要素の参照は element() で行います。これらのメソッドの名前と仕様は Java のインターフェース Queue にあわせました。なお、データの追加を enqueue, 削除を dequeue と呼ぶ場合も多いです。
●プログラムの作成
それではプログラムを作りましょう。最初にクラスを定義します。
リスト : クラス Queue の定義
class Queue<E> {
// 内部クラス
private class Cell {
E item;
Cell next;
Cell(E x, Cell xs) {
item = x;
next = xs;
}
}
// フィールド変数
Cell head, tail;
int cnt;
public Queue() {
head = tail = null;
cnt = 0;
}
// メソッドの定義
・・・省略・・・
}
クラス Queue の中でセルを表すクラス Cell を定義します。Cell のメソッドはコンストラクタだけで、フィールド変数 item と next の値を初期化します。今回はアクセスメソッドを定義せずに、キューのメソッドから直接アクセスすることにします。Queue のコンストラクタでは、要素数を表す変数 cnt とセルを参照する変数 head, tail を初期化します。
次はデータを追加するメソッド add() を作ります。
リスト : データの追加
public boolean add(E x) {
Cell xs = new Cell(x, null);
if (cnt == 0)
head = xs;
else
tail.next = xs;
tail = xs;
cnt++;
return true;
}
最初にデータ x を格納したセル xs を生成します。キューが空の場合は、head に xs をセットします。そうでなければ、最後尾のセル tail の next に xs を追加します。あとは、tail を xs に書き換えて、cnt の値を + 1 します。
次は次は先頭要素を削除するメソッド remove() を作ります。
リスト : 先頭要素の削除
public E remove() {
if (cnt == 0)
throw new NoSuchElementException("Queue.remove()");
E x = head.item;
head = head.next;
if(--cnt == 0) tail = null;
return x;
}
キューが空の場合は throw でエラーを送出します。そうでなければ、先頭のセル head の要素を変数 x にセットし、このセルをリストから削除します。この処理は head の値を次のセル (head.next) に書き換えるだけです。cnt の値を -1 してデータがなくなった場合は tail の値を null に書き換えます。最後に、return で x を返します。
あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト１ をお読みください。
●簡単なテスト
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
リスト : 簡単なテスト
public class queue1 {
public static void main(String[] args) {
var q = new Queue<Integer>();
System.out.println(q.isEmpty());
System.out.println(q.size());
for (int i = 1; i <= 8; i++) q.add(i);
System.out.println(q.isEmpty());
System.out.println(q.size());
while (!q.isEmpty()) {
System.out.print(q.element() + " ");
System.out.print(q.remove() + " ");
}
System.out.println("");
System.out.println(q.isEmpty());
System.out.println(q.size());
}
}
$ javac queue1.java $ java queue1 true 0 false 8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 true 0
正常に動作していますね。
●循環リスト
連結リストは要素を一列に並べたデータ構造ですが、最後尾のセルと先頭のセルを連結することで要素をリング状に並べることができます。これを「循環リスト (circular list)」 といいます。次の図を見てください。
上図の連結リスト (1 2 3) は null で終端されています。この連結リストで、最後尾のセルの next を先頭のセル A に書き換えると、循環リストを作ることができます。循環リストは環状に並んだデータを表すのに便利なデータ構造です。
●循環リストによるキューの実装
循環リストの場合、最後尾のセルを参照する変数 tail を用意するだけでキューを実現することができます。下図を見てください。
図 : 循環リストによるキューの構造
循環リストの場合、最後尾のセルの次のセルが先頭になります。(3) を見てください。循環リストの場合、tail が参照する最後尾のセルの next は null ではありません。next が参照するセルがキューの先頭になるのです。データが一つしかない場合、(2) のように tail が参照するセルの next は自分自身を参照しています。つまり、このセルが先頭であり最後尾でもあるわけです。キューにデータがない場合、tail の値は (1) のように null になります。
●プログラムの作成
それでは、プログラムを作りましょう。最初にクラスを定義します。
リスト : 循環リストによるキューの実装
class Queue<E> {
// 内部クラス
private class Cell {
E item;
Cell next;
Cell(E x, Cell xs) {
item = x;
next = xs;
}
}
// フィールド変数
Cell tail;
int cnt;
public Queue() {
tail = null;
cnt = 0;
}
// メソッドの定義
・・・省略・・・
}
Queue の中でセルを表すクラス Cell を定義するのは前と同じです。Queue のコンストラクタでは、要素数を表す変数 cnt と最後尾のセルを参照する変数 tail を初期化します。
次はデータを追加するメソッド add() を作ります。
リスト : データの追加
public boolean add(E x) {
if (cnt == 0) {
tail = new Cell(x, null);
tail.next = tail;
} else {
Cell xs = new Cell(x, tail.next);
tail.next = xs;
tail = xs;
}
cnt++;
return true;
}
キューが空の場合は、コンストラクタでセルを生成して tail にセットします。そして、tail.next の値を自分自身の値 tail に書き換えます。これで循環リストになります。データがある場合は、セル tail の後ろに新しいセル xs を挿入します。そして、tail の値を xs に書き換えれば、xs が最後尾のセルになります。
次は先頭要素を削除するメソッド remove() を作ります。
リスト : 先頭要素の削除
public E remove() {
if (cnt == 0)
throw new NoSuchElementException("Queue.remove()");
Cell xs = tail.next;
tail.next = xs.next;
cnt--;
if (cnt == 0) tail = null;
return xs.item;
}
キューが空の場合は throw でエラーを送出します。そうでなければ、先頭のセル tail.next を変数 xs にセットし、このセルを循環リストから削除します。この処理は tail.next の値を xs の次のセル (xs.next) に書き換えるだけです。cnt の値を -1 してデータがなくなった場合は tail の値を null にします。最後に、return で xs.item の値を返します。
あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト２ をお読みください。
●immutable なキュー
次は immutable な連結リスト (ImList) を使って immutable なキューを作ってみましょう。今回は関数型言語 (SML/NJ など) でよく使われている方法を紹介します。次の図を見てください。
上図は 2 つのリストでキューを表しています。データを取り出すときは head のリストを、データを追加するときは tail のリストを使います。head と tail で一つのキューを構成し、head のリストはデータを逆順で格納することになります。ようするに、head が先頭で tail が最後尾になるわけです。上図のキューを一つのリストで表すと (0, 1, 2, 3, 4, 5) になります。
したがって、head が空リストでも tail にデータがあれば、キューは空ではありません。tail のリストを逆順にして head にセットし、tail を空リストにします。これで head からデータを取り出すことができます。キューが空の状態は head と tail が両方とも空リストの場合です。
●immtable なキューの仕様
下表に immutable な Queue の仕様を示します。
| メソッド | 機能 |
|---|---|
| Queue<E> Queue.queue() | 空のキューを生成する |
| Queue<E> Queue.queue(ImList<E> xs) | 連結リスト xs の要素でキューを初期化する |
| Queue<E> add(E x) | キューにデータを追加する |
| E first() | キューの先頭要素を参照する |
| Queue<E> rest() | キューの先頭要素を削除する |
| Pair<E, Queue<E>> pop() | 先頭要素とそれを削除したキューを返す |
| boolean isEmpty() | キューが空ならば True を返す |
| int length() | キューの要素の個数を求める |
メソッド名は immutable な連結リスト ImList にあわせました。データの追加は add() で、先頭データの参照は first() で、先頭データの削除は rest() で行います。first() と rest() を同時に行うのが pop() です。
●プログラムの作成
それではプログラムを作りましょう。最初にクラスを定義します。次のリストを見てください。
リスト : immutable なキューの定義
package immutable;
import immutable.*;
// immutable なキュー
public final class Queue<E> {
private final ImList<E> head;
private final ImList<E> tail;
private Queue(ImList<E> xs, ImList<E> ys) {
head = xs;
tail = ys;
}
// メソッドの定義
・・・省略・・・
}
クラス Queue はパッケージ immutable に定義します。フィールド変数は head と tail の 2 つです。クラスとそのフィールド変数は final であることに注意してください。
次はデータを追加するメソッド add() を作りましょう。
リスト : データの追加
public Queue<E> add(E x) {
return new Queue<E>(head, ImList.cons(x, tail));
}
add() は簡単です。tail の先頭にデータ x を追加した Queue を生成して返すだけです。
次は先頭データを参照するメソッド first() と取り除くメソッド rest() を作ります。
リスト : 先頭データの参照と削除
// 先頭データの参照
public E first() {
if (!head.isEmpty())
return head.first();
else if (!tail.isEmpty())
return tail.last();
else
throw new NoSuchElementException("Queue.first()");
}
// 先頭データの削除
public Queue<E> rest() {
if (!head.isEmpty())
return new Queue<E>(head.rest(), tail);
else if (!tail.isEmpty())
return new Queue<E>(tail.reverse().rest(), ImList.nil());
else
throw new NoSuchElementException("Queue.rest()");
}
キューが空の場合、first() と rest() はエラーを送出します。head が空リストでない場合、first() は head.item を返します。rest() は head.rest() と tail を格納したキューを生成して返します。head が空リストの場合、first() は tail の最後の要素を last() で求めて返します。rest() は tail.reverse() で tail のリストを反転し、先頭要素を rest() で削除します。あとは、そのリストと空リストを格納したキューを生成して返します。
あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト３ をお読みください。
●実行例
それでは簡単な実行例を示します。
リスト : 簡単なテスト
import immutable.ImList;
import immutable.Queue;
public class queue3 {
public static void main(String[] args) {
var q = Queue.queue(ImList.iota(1, 5));
System.out.println(q.isEmpty());
System.out.println(q.length());
q = ImList.iota(6, 10).foldLeft((a, x) -> a.add(x), q);
System.out.println(q.length());
while (!q.isEmpty()) {
System.out.print(q.first() + " ");
q = q.rest();
}
System.out.println("");
System.out.println(q.isEmpty());
System.out.println(q.length());
}
}
immutable なキューなので、キューを格納している変数の値を書き換えていることに注意してください。実行結果を示します。
false 5 10 1 2 3 4 5 6 7 8 9 10 true 0
正常に動作していますね。
●プログラムリスト１
//
// queue1.java : 連結リストによるキューの実装
//
// Copyright (C) 2016-2021 Makoto Hiroi
//
import java.util.NoSuchElementException;
class Queue<E> {
// 内部クラス
private class Cell {
E item;
Cell next;
Cell(E x, Cell xs) {
item = x;
next = xs;
}
}
// フィールド変数
Cell head, tail;
int cnt;
public Queue() {
head = tail = null;
cnt = 0;
}
// 追加
public boolean add(E x) {
Cell xs = new Cell(x, null);
if (cnt == 0)
head = xs;
else
tail.next = xs;
tail = xs;
cnt++;
return true;
}
// 削除
public E remove() {
if (cnt == 0)
throw new NoSuchElementException("Queue.remove()");
E x = head.item;
head = head.next;
if(--cnt == 0) tail = null;
return x;
}
// 参照
public E element() {
if (cnt == 0)
throw new NoSuchElementException("Queue.element()");
return head.item;
}
// 空にする
public void clear() {
head = tail = null;
cnt = 0;
}
// 空か？
public boolean isEmpty() { return cnt == 0; }
// 要素数
public int size() { return cnt; }
}
public class queue1 {
public static void main(String[] args) {
var q = new Queue<Integer>();
System.out.println(q.isEmpty());
System.out.println(q.size());
for (int i = 1; i <= 8; i++) q.add(i);
System.out.println(q.isEmpty());
System.out.println(q.size());
while (!q.isEmpty()) {
System.out.print(q.element() + " ");
System.out.print(q.remove() + " ");
}
System.out.println("");
System.out.println(q.isEmpty());
System.out.println(q.size());
}
}
●プログラムリスト２
//
// queue2.java : 循環リストによるキューの実装
//
// Copyright (C) 2016-2021 Makoto Hiroi
//
import java.util.NoSuchElementException;
class Queue<E> {
// 内部クラス
private class Cell {
E item;
Cell next;
Cell(E x, Cell xs) {
item = x;
next = xs;
}
}
// フィールド変数
Cell tail;
int cnt;
public Queue() {
tail = null;
cnt = 0;
}
// 追加
public boolean add(E x) {
if (cnt == 0) {
tail = new Cell(x, null);
tail.next = tail;
} else {
Cell xs = new Cell(x, tail.next);
tail.next = xs;
tail = xs;
}
cnt++;
return true;
}
// 削除
public E remove() {
if (cnt == 0)
throw new NoSuchElementException("Queue.remove()");
Cell xs = tail.next;
tail.next = xs.next;
cnt--;
if (cnt == 0) tail = null;
return xs.item;
}
// 参照
public E element() {
if (cnt == 0)
throw new NoSuchElementException("Queue.element()");
return tail.next.item;
}
// 要素の個数
public int size() { return cnt; }
// 空か？
public boolean isEmpty() {
return cnt == 0;
}
// 空にする
public void clear() {
tail = null;
cnt = 0;
}
}
public class queue2 {
public static void main(String[] args) {
var q = new Queue<Integer>();
System.out.println(q.isEmpty());
System.out.println(q.size());
for (int i = 1; i <= 8; i++) q.add(i);
System.out.println(q.isEmpty());
System.out.println(q.size());
while (!q.isEmpty()) {
System.out.print(q.element() + " ");
System.out.print(q.remove() + " ");
}
System.out.println("");
System.out.println(q.isEmpty());
System.out.println(q.size());
}
}
●プログラムリスト３
//
// Queue.java : immutable なキュー
//
// Copyright (C) 2016-2021 Makoto Hiroi
//
package immutable;
import java.util.NoSuchElementException;
import immutable.ImList;
// immutable なキュー
public final class Queue<E> {
private final ImList<E> head;
private final ImList<E> tail;
private Queue(ImList<E> xs, ImList<E> ys) {
head = xs;
tail = ys;
}
// 生成
public static <E> Queue<E> queue() {
return new Queue<E>(ImList.nil(), ImList.nil());
}
public static <E> Queue<E> queue(ImList<E> xs) {
return new Queue<E>(xs, ImList.nil());
}
// キューは空か？
public boolean isEmpty() {
return head.isEmpty() && tail.isEmpty();
}
// 挿入
public Queue<E> add(E x) {
return new Queue<E>(head, ImList.cons(x, tail));
}
// 参照
public E first() {
if (!head.isEmpty())
return head.first();
else if (!tail.isEmpty())
return tail.last();
else
throw new NoSuchElementException("Queue.first()");
}
// 削除
public Queue<E> rest() {
if (!head.isEmpty())
return new Queue<E>(head.rest(), tail);
else if (!tail.isEmpty())
return new Queue<E>(tail.reverse().rest(), ImList.nil());
else
throw new NoSuchElementException("Queue.rest()");
}
// first() + rest()
public Pair<E, Queue<E>> pop() {
if (!head.isEmpty()) {
return Pair.pair(head.first(), new Queue<E>(head.rest(), tail));
} else if (!tail.isEmpty()) {
ImList<E> xs = tail.reverse();
return Pair.pair(xs.first(), new Queue<E>(xs.rest(), ImList.nil()));
} else {
throw new NoSuchElementException("Queue.pop()");
}
}
// 要素の個数
public int length(){
return head.length() + tail.length();
}
}
改訂 2021 年 2 月 28 日