連結リスト (linked list) はデータを一方向につなげたデータ構造です。リストを操作するプログラミング言語では Lisp が有名ですが、Lisp で扱うリストが連結リストです。Python のリストは 1 次元の可変長配列のことで、連結リストではありません。ご注意ください。
下図に連結リストの構造を示します。
(1)
変数
┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(None)
└─┘ └─┴─┘ └─┴─┘ └─┴─┘
(2)
ヘッダセル
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ │・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(None)
└─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘
図 : 連結リストの構造
連結リストはセル (cell) というデータを繋げて作ります。セルにはデータを格納する場所と、次のセルを指し示す場所から構成されます。図でいうと、箱がひとつのセルを表していて、左側にデータを格納し、右側に次のセルへの参照を格納します。リストの終わりを示すため、最後のセルの右側には特別な値（たとえば None）を格納します。そして、図 (1) のように先頭セルへの参照を変数に格納しておけば、この変数を使って連結リストにアクセスすることができます。また、図 (2) のようにヘッダセルを用意する方法もあります。
連結リストの長所は、データの挿入や削除が簡単にできることです。配列でデータの削除や挿入を行う場合、要素を移動しなければいけませんが、連結リストはセルを付け替えるだけで実現できます。逆に、配列はどの要素にも一定の時間でアクセスすることができますが、連結リストはセルを順番にたどっていくため、後ろのデータほどアクセスに時間がかかります。これが連結リストの短所です。
Python のリストは 1 次元配列ですが、大きさを変更できる可変長配列として実装されているため、Ｃ言語の配列と違って柔軟で扱いやすいデータ構造になっています。Python で連結リストを使う機会はあまりないと思いますが、連結リストは基本的で重要なデータ構造なので、理解しておくと役に立つ場合があると思います。連結リストは お気楽 Python プログラミング入門第 5 回 で詳しく説明しています。興味のある方はお読みください。このページでは入門講座で取り上げることのできなかった「循環リスト」や「双方向リスト」について説明します。
連結リストは要素を一列に並べたデータ構造ですが、最後尾のセルと先頭のセルを連結することで要素をリング状に並べることができます。これを「循環リスト (circular list) 」 といいます。次の図を見てください。
Cell の next を直接 CELL A に書き換える
└─────┐
Cell A ↓
data next data next data next
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
１ ２ ３
┌───────────────┐
↓ │
┌─┬─┐ ┌─┬─┐ ┌─┬┼┐
変数─→│・│・┼─→│・│・┼─→│・│・│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
１ ２ ３
図 : 循環リスト
上図の連結リスト LList(1, 2, 3) は None で終端されています。この連結リストで、最後尾のセルの next を先頭のセル A に書き換えると、循環リストを作ることができます。循環リストは環状に並んだデータを表すのに便利なデータ構造です。
それでは簡単な例題として、循環リストを使って「キュー (queue) 」を実装してみましょう。キューは お気楽 Python プログラミング入門第 6 回 で詳しく説明しています。よろしければ参考にしてください。連結リストを使ったキューの構造を下図に再掲します。
rear ─→ None
front ─→ None
(1) キューが空の状態
rear ─────────────────────┐
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
front ─→│・│・┼→│・│・┼→│・│・┼→│・│・┼→ None
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
data1 data2 data3 data4
(2) キューにデータがある場合
図 : 連結リストによるキューの構造
先頭のセルを参照する変数 front のほかに、最後尾のセルを参照する変数 rear を用意します。キューにデータがない場合は、(1) のように front と rear は None になっています。データがある場合は、(2) のように front は先頭のセルを参照し、rear は最後尾のセルを参照しています。これで、データの追加を効率的に行うことができます。
循環リストの場合、最後尾のセルを参照する変数 rear を用意するだけでキューを実現することができます。下図を見てください。
rear ─→ None
(1) キューが空の状態
rear ───┐
↓
┌─┬─┐
┌─→│・│・┼─┐
│ └┼┴─┘ │
│ ↓ │
│ data1 │
│ │
└────────┘
(2) キューにデータが一つある場合
rear ─────────────────────┐
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
┌─→│・│・┼→│・│・┼→│・│・┼→│・│・┼─┐
│ └┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘ │
│ ↓ ↓ ↓ ↓ │
│ data1 data2 data3 data4 │
│ │
└──────────────────────────┘
(3) キューに複数のデータがある場合
図 : 循環リストによるキューの構造
循環リストの場合、最後尾のセルの次のセルが先頭になります。(3) を見てください。循環リストの場合、rear が参照する最後尾のセルの next は None ではありません。next が参照するセルがキューの先頭になるのです。データが一つしかない場合、(2) のように rear が参照するセルの next は自分自身を参照しています。つまり、このセルが先頭であり最後尾でもあるわけです。キューにデータがない場合、rear の値は (1) のように None になります。
それでは、プログラムを作りましょう。最初に作成するメソッドを表に示します。
| メソッド | 機能 |
|---|---|
| enqueue(x) | キューにデータを追加する |
| dequeue() | キューからデータを取り出す |
| isEmpty() | キューが空ならば True を返す |
| peek() | キューの先頭にあるデータを求める |
| rotate(n = 1) | キューを回転する |
enqueue, dequeue, isEmpty は連結リストで作成したキューのメソッドと同じ機能です。peek はキューの先頭のデータを求めるだけで、キューから取り出すことはしません。rotate はキューを回転する操作で、先頭のデータを最後尾へ移動します。これを n 回繰り返します。この操作は dequeue でデータを取り出し、それを enqueue で追加することと同じですが、循環リストの場合は rear の値を次のセルに書き換えるだけで実現できます。
次はクラスを定義します。
リスト : 循環リストによるキューの実装
class Queue:
# セルの定義
class Cell:
def __init__(self, x, y = None):
self.data = x
self.next = y
# 初期化
def __init__(self):
self.size = 0
self.rear = None
キューのクラス名は Queue とし、その中でセルを表すクラス Cell を定義します。Cell のメソッドは __init__ だけで、インスタンス変数 data と next の値を初期化します。今回はアクセスメソッドを定義せずに、キューのメソッドから直接アクセスすることにします。Queue のメソッド __init__ では、データ数を表すインスタンス変数 size と最後尾のセルを参照するインスタンス変数 rear を初期化します。
次はデータを追加するメソッド enqueue を作ります。
リスト : データの追加
def enqueue(self, x):
if self.size == 0:
self.rear = Queue.Cell(x)
self.rear.next = self.rear # 循環リスト
else:
new_cell = Queue.Cell(x, self.rear.next)
self.rear.next = new_cell
self.rear = new_cell
self.size += 1
キューが空の場合は、Cell(x) でセルを生成して self.rear にセットします。次に、self.rear.next の値を自分自身の値 self.rear に書き換えます。これで循環リストになります。データがある場合は、セル self.rear の後ろに新しいセル new_cell を挿入します。そして、self.rear の値を new_cell に書き換えれば、new_cell が最後尾のセルになります。
次はデータを取り出すメソッド dequeue を作ります。
リスト : データの取り出し
def dequeue(self):
if self.size == 0: raise IndexError
front = self.rear.next
self.rear.next = front.next
self.size -= 1
if self.size == 0: self.rear = None
return front.data
キューが空の場合は raise でエラー IndexError を送出します。そうでなければ、先頭のセル self.rear.next を変数 front にセットし、このセルを循環リストから削除します。この処理は self.rear.next の値を front の次のセル (front.next) に書き換えるだけです。self.size の値を -1 してデータがなくなった場合は self.rear の値を None にします。最後に、return で fornt.data の値を返します。
次はメソッド rotate を作ります。
リスト : キューを回転する
def rotate(self, n = 1):
if self.size == 0 or n < 1: raise IndexError
while n > 0:
self.rear = self.rear.next
n -= 1
キューにデータがない場合や引数 n が 1 未満であれば raise でエラーを送出します。あとは、n 回だけ循環リストをたどる、つまり self.rear の値を self.rear.next に書き換えるだけです。循環リストには終端がないので、n の値が self.size より大きくても、ぐるぐる回るだけで正常に動作します。
メソッド isEmpty と peek, Queue を表示するメソッド__str__ は簡単なので説明は省略します。詳細は プログラムリスト１ をお読みください。
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
# 簡単なテスト
if __name__ == '__main__':
q = Queue()
print q.isEmpty()
for x in range(5): q.enqueue(x)
print q
q.rotate()
print q.peek()
q.rotate()
print q.peek()
q.rotate()
print q.peek()
q.rotate()
print q.peek()
q.rotate()
print q.peek()
while not q.isEmpty():
print q.dequeue(),
print q
print q
実行結果は次のようになります。
True Queue(0, 1, 2, 3, 4) 1 2 3 4 0 0 Queue(1, 2, 3, 4) 1 Queue(2, 3, 4) 2 Queue(3, 4) 3 Queue(4) 4 Queue() Queue()
連結リストのセル (Cell) は、データを格納する data と、直後のセルへの参照を格納する next から構成されています。双方向リストは名前が示すように、直後のセルだけでなく、直前のセルへの参照を持たせたデータ構造です。双方向リストは「重連結リスト (doubly linked list) 」と呼ばれることもあります。
prev next prev next prev next
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
←─┼・│ │・│←─┼・│ │・│←─┼・│ │・│←─
─→│・│ │・┼─→│・│ │・┼─→│・│ │・┼─→
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
data data data
図 : 双方向リスト
連結リストは後ろ方向にしかセルをたどることができませんが、双方向リストでは前後どちらの方向へもセルをたどることができます。セルを削除する場合も、前後のセルがわかるので簡単に削除することができるのです。双方向リストはメモリ管理などによく使われるデータ構造です。
それでは簡単な例題として deque (double ended queue) というデータ構造を Python で実装してみましょう。deque は「両端キュー」のことで、「デック」とか「ディーキュー」と呼ばれています。キューの場合、データの追加は最後尾に、データの取り出しは先頭に対してのみ行えます。これに対しディーキューは、先頭および最後尾のどちらでもデータの追加と取り出しが行えるデータ構造です。
ディーキューは双方向リストを使うと簡単に実現できます。次の図を見てください。
head ──┐
↓
ヘッダセル
┌─┬─┬─┐
┌←─┼ │ │ │←───────────────────┐
│┌→│ │ │ ┼─→─────────────────┐│
││ └─┴─┴─┘ ││
││ next prev ││
││ ││
││ Cell A Cell B Cell C ││
││ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ││
│└←┼ │Ａ│ │←─┼ │Ｂ│ │←─┼ │Ｃ│ │←┘│
└─→│ │ │ ┼─→│ │ │ ┼─→│ │ │ ┼─→┘
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
prev next prev next prev next
図：ディーキュー (1)
双方向リストを使う場合、ヘッダセルを用意してリストを環状に構成する方法が一般的です。ヘッダセルにはデータを格納しません。ヘッダセルの next が参照するセルが先頭で、prev が参照するセルが最後尾になります。ヘッダセルが先頭と最後尾のセルを参照しているので、両端でのデータ操作が簡単にできるのです。
データがない空リストの場合は、次の図に示すようにセルを参照する変数 next と prev の値はヘッダセル自身になります。
┌───────────┐
│ ┌─┬─┬─┐ │
└←─┼ │ │ │←─┘
┌─→│ │ │ ┼─→┐
│ └─┴─┴─┘ │
└───────────┘
データがない場合はヘッダセル自身を格納
図：ディーキュー (2)
このようにすると、空リストへデータを挿入する場合や、データを削除して空リストになる場合で、プログラムが簡単になるという利点があります。これは、実際にプログラムを作ってみるとわかります。
それでは、プログラムを作りましょう。最初に作成するメソッドを表に示します。データを追加するメソッドには push を、取り出すメソッドには pop を付けました。
| メソッド | 機能 |
|---|---|
| push_front(x) | 先頭にデータを追加する |
| push_back(x) | 末尾にデータを追加する |
| pop_front() | 先頭からデータを取り出す |
| pop_back() | 末尾からデータを取り出す |
| peek_front() | 末尾にあるデータを求める |
| peek_back() | 先頭にあるデータを求める |
| isEmpty() | ディーキューが空ならば True を返す |
次はクラスを定義します。
リスト : 双方向リストによるディーキューの実装
class Deque:
# セルの定義
class Cell2:
def __init__(self, x, y = None, z = None):
self.data = x
self.next = y
self.prev = z
# 初期化
def __init__(self):
head = Deque.Cell2(None) # ヘッダ
head.next = head # 循環リスト
head.prev = head
self.size = 0
self.head = head
クラス名は Deque とします。セルを表すクラスは Cell2 とし、Deque の中で定義します。インスタンス変数 data にデータを格納し、prev が前のセル、スロット next が次のセルを参照します。アクセスメソッドは定義しないで、Deque のメソッドから直接アクセスすることにします。
Deque のメソッド __init__ では、Cell2 でセルを生成してインスタンス変数 head に格納します。次に、head.next と head.prev を head に書き換えて循環リストにします。これで、空の双方向リストになります。最後に、Deque のインスタンス変数 size を 0 に、head を双方向リストに初期化します。
それでは、ディーキューの先頭にデータを追加するメソッド push_front から作りましょう。次の図を見てください。
H Q
<--> [ | |Q] <--> [H| | ] <-->
H の next に P を挿入
H P Q
<--> [ | |P] <--> [H| |Q] <--> [P| | ] <-->
【注意】[prev | data | next] はセルを表す。
図：データの追加 (1)
この場合はヘッダ H の next と Q の prev を挿入するセル P に書き換え、P の prev と next には H と Q をセットします。これをプログラムすると、次のようになります。
リスト：データの追加 (1)
# 先頭に追加
def push_front(self, x):
h = self.head
q = h.next
p = Deque.Cell2(x, q, h)
h.next = p
q.prev = p
self.size += 1
ヘッダセルを変数 h にセットし、その次のセル h.next を変数 q にセットします。次に、新しいセル p を Cell2(x, q, h) で生成します。このとき、p の next に q がセットされ、prev に h がセットされます。そして、h.next と q.prev の値を p に書き換えれば、データを追加することができます。また、このままの処理で空リストにデータを挿入することもできます。次の図を見てください。
H(header) P [H| |H] [?| |?] H P [P| |P] <--> [H| |H] 図：空リストへデータを挿入
上図に示すように、ヘッダセルの prev と next は自分自身を格納しているので、h.next は H 自身となります。したがって、P の prev と next には H がセットされ、H の prev と next には P がセットされるのです。これで、空リストにデータを挿入することができます。
末尾にデータを追加するメソッド push_back も同様にプログラムすることができます。次のリストを見てください。
リスト：データの挿入 (2)
# 後ろに追加
def push_back(self, x):
h = self.head
p = h.prev
q = Deque.Cell2(x, h, p)
h.prev = q
p.next = q
self.size += 1
今度は新しいセルをヘッダセルの prev に挿入します。セル h.prev を p にセットします。新しいセルを Cell2(x, h, p) で生成し、変数 q にセットします。これで、セル q の next に h が、prev に p がセットされます。あとは、h.prev と p.next の値を q に書き換えるだけです。これで末尾にデータを追加することができます。
次は、先頭のデータを削除するメソッド pop_front を作りましょう。次の図を見てください。
H Q P
<--> [ | |Q] <--> [H| |P] <--> [P| | ] <-->
H の next のセル Q を削除
H Q P
<--> [ | |P] [H| |P] [H| | ] <-->
↑ ↑
└─────────┘
図：データの削除
データの削除はとても簡単です。H の next と P の prev を書き換えればいいのです。プログラムは次のようになります。
リスト：データの削除 (1)
# 先頭のデータを取り出す
def pop_front(self):
if self.size == 0: raise IndexError
h = self.head
q = h.next
p = q.next
p.prev = h
h.next = p
self.size -= 1
return q.data
メソッド pop_front は削除したデータを返します。空リストの場合はエラー IndexError を送出します。最初に、削除するセルを h.next から求めて変数 q にセットします。そして、その次のセルを q.next から求めて変数 p にセットします。あとは、p.prev の値を h に、h.next の値を p に書き換えるだけでセル q を削除することができます。最後に、格納されているデータ q.data を返します。
ところで、最後のデータを削除する場合もこのままの処理で大丈夫です。次の図を見てください。
H(header) Q H
[Q| |Q] <--> [H| |H] ===> [H| |H]
図：最後のデータを削除
セル Q の next と prev はヘッダセル H を格納しています。Q の次のセルを P とすると、それはヘッダセル H になります。したがって、P の prev を H に書き換える処理は、ヘッダの prev をヘッダ自身に、H の next を P に書き換える処理はヘッダの next をヘッダ自身に書き換える処理になります。これで双方向リストは空リストになります。
末尾のデータを削除するメソッド pop_back も簡単にプログラムすることができます。次のリストを見てください。
リスト：データの削除 (2)
# 最後尾のデータを取り出す
def pop_back(self):
if self.size == 0: raise IndexError
h = self.head
q = h.prev
p = q.prev
p.next = h
h.prev = p
self.size -= 1
return q.data
今度はヘッダセルの prev のセルを削除します。最初に、削除するセルを h.prev から求めて変数 q にセットします。そして、その次のセルを q.prev から求めて変数 p にセットします。あとは、p.next の値を h に、h.prev の値を p に書き換えるだけでセル q を削除することができます。最後に、格納されているデータ q.data を返します。
メソッド isEmpty, peek_front, peek_back, Deque を表示するメソッド__str__ は簡単なので説明は省略します。詳細は プログラムリスト２ をお読みください。
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
リスト：テストプログラム
if __name__ == '__main__':
q = Deque()
print q.isEmpty()
for x in range(5):
q.push_front(x)
q.push_back(x * 10)
print q
print q.peek_front()
print q.peek_back()
print q.isEmpty()
for x in range(5):
print q.pop_front()
print q.pop_back()
print q
実行結果を示します。
True Deque(0, 0) Deque(1, 0, 0, 10) Deque(2, 1, 0, 0, 10, 20) Deque(3, 2, 1, 0, 0, 10, 20, 30) Deque(4, 3, 2, 1, 0, 0, 10, 20, 30, 40) 4 40 False 4 40 Deque(3, 2, 1, 0, 0, 10, 20, 30) 3 30 Deque(2, 1, 0, 0, 10, 20) 2 20 Deque(1, 0, 0, 10) 1 10 Deque(0, 0) 0 0 Deque()
ところで、キューは配列を使っても簡単に実現できます。先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータをキューに格納されているデータとするのがポイントです。次の図を見てください。
0 1 2 3 4 5 6 7 8 9
rear = 0 ↓
QUEUE [ ] : QUEUE は空
front= 0 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : データの追加
front= 0 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : 10を取り出す
front= 1 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : 20,30を取り出す
front= 3 ↑
図 : キューの動作
まずキューは空の状態で、rear, front ともに 0 です。データの追加は、rear が示す位置にデータを書き込み、rear の値を +1 します。データ 10, 20, 30 を追加すると、図のようにデータが追加され rear は 3 になります。このとき front は 0 のままなので、先頭のデータは 10 ということになります。
次に、データを取り出す場合、front の示すデータを取り出しから front の値を +1 します。この場合、front が 0 なので 10 を取り出して front の値は 1 となり、次のデータ 20 が先頭になります。データを順番に 20, 30 と取り出していくと、3 つしかデータを書き込んでいないので当然キューは空になります。このとき front は 3 になり rear と同じ値になります。このように、front と rear の値が 0 の場合だけが空の状態ではなく、front と rear の値が等しくなると、キューは空になることに注意してください。
rear, fornt ともに値は増加していく方向なので、いつかは配列の範囲をオーバーします。このため、配列を先頭と末尾がつがっているリング状と考え、rear, front が配列の範囲を超えたら 0 に戻すことにします。これを「循環配列」とか「リングバッファ」と呼びます。一般に、配列を使ってキューを実装する場合は、リングバッファとするのがふつうです。
それでは、プログラムを作りましょう。最初に作成するメソッドを表に示します。
| メソッド | 機能 |
|---|---|
| enqueue(x) | キューにデータを追加する |
| dequeue() | キューからデータを取り出す |
| peek() | キューの先頭にあるデータを求める |
| isEmpty() | キューが空ならば True を返す |
| isFull() | キューが満杯ならば True を返す |
今回はリングバッファの大きさを固定するので、キューが満杯になる場合があります。そこで、メソッド isFull を用意して、キューが満杯の場合は True を返すことにします。
次はクラスを定義します。
リスト : リングバッファによるキューの実装
class Queue:
def __init__(self, n = 16):
self.size = n
self.buff = [None] * n
self.front = 0
self.rear = 0
self.count = 0
インスタンス変数 size はキューの大きさ、buff には配列をセットします。デフォルトの大きさは 16 としました。インスタンス変数 count はキューに格納されたデータ数をカウントします。この変数を用意することで、キューが空なのか満杯なのか簡単にチェックすることができます。
次はデータを追加するメソッド enqueue を作ります。
リスト : データの追加
def enqueue(self, x):
if self.count == self.size: raise IndexError
self.buff[self.rear] = x
self.rear += 1
if self.rear == self.size: self.rear = 0
self.count += 1
まず、count と size を比較して、キューにデータを格納できるかチェックします。満杯の場合はエラー IndexError を送出します。データは rear の位置に格納し、count と rear の値を更新します。そして、rear の値が配列の範囲を超えたならば 0 に戻します。
次は、キューからデータを取り出すメソッド dequeue を作ります。
リスト : データの取り出し
def dequeue(self):
if self.count == 0: raise IndexError
data = self.buff[self.front]
self.front += 1
if self.front == self.size: self.front = 0
self.count -= 1
return data
まず、キューにデータがあるかチェックします。キューが空の場合はエラー IndexError を送出します。データがある場合は self.buff[self.front] のデータを取り出して data にセットします。次に count と front の値を更新し、front の値が配列の範囲を超えたら 0 に戻します。最後に return で data を返します。
あとのメソッド peek, isEmpty, isFull, __str__ は簡単なので説明は省略します。詳細は プログラムリスト３ をお読みください。
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
# テスト
if __name__ == '__main__':
q = Queue(8)
x = 0
while not q.isFull():
q.enqueue(x)
x += 1
print q
while not q.isEmpty():
print q.dequeue()
print q
実行結果を示します。
Queue(0) Queue(0, 1) Queue(0, 1, 2) Queue(0, 1, 2, 3) Queue(0, 1, 2, 3, 4) Queue(0, 1, 2, 3, 4, 5) Queue(0, 1, 2, 3, 4, 5, 6) Queue(0, 1, 2, 3, 4, 5, 6, 7) 0 Queue(1, 2, 3, 4, 5, 6, 7) 1 Queue(2, 3, 4, 5, 6, 7) 2 Queue(3, 4, 5, 6, 7) 3 Queue(4, 5, 6, 7) 4 Queue(5, 6, 7) 5 Queue(6, 7) 6 Queue(7) 7 Queue()
リスト : 循環リストによるキューの実装
class Queue:
# セルの定義
class Cell:
def __init__(self, x, y = None):
self.data = x
self.next = y
# 初期化
def __init__(self):
self.size = 0
self.rear = None
# データの追加
def enqueue(self, x):
if self.size == 0:
self.rear = Queue.Cell(x)
self.rear.next = self.rear # 循環リスト
else:
new_cell = Queue.Cell(x, self.rear.next)
self.rear.next = new_cell
self.rear = new_cell
self.size += 1
# データの取り出し
def dequeue(self):
if self.size == 0: raise IndexError
front = self.rear.next
self.rear.next = front.next
self.size -= 1
if self.size == 0: self.rear = None
return front.data
# キューは空か
def isEmpty(self):
return self.size == 0
# 先頭のデータを求める
def peek(self):
if self.size == 0: raise IndexError
return self.rear.next.data
# キューを回転する
def rotate(self, n= 1):
if self.size == 0 or n < 1: raise IndexError
while n > 0:
self.rear = self.rear.next
n -= 1
# キューの表示
def __str__(self):
if self.size == 0: return 'Queue()'
cp = self.rear.next
n = self.size
buff = 'Queue('
while n > 1:
buff += '%s, ' % cp.data
cp = cp.next
n -= 1
buff += '%s)' % cp.data
return buff
# 簡単なテスト
if __name__ == '__main__':
q = Queue()
print q.isEmpty()
for x in range(5): q.enqueue(x)
print q
q.rotate()
print q.peek()
q.rotate()
print q.peek()
q.rotate()
print q.peek()
q.rotate()
print q.peek()
q.rotate()
print q.peek()
while not q.isEmpty():
print q.dequeue(),
print q
print q
リスト : 双方向リストによるディーキューの実装
class Deque:
# セルの定義
class Cell2:
def __init__(self, x, y = None, z = None):
self.data = x
self.next = y
self.prev = z
# 初期化
def __init__(self):
head = Deque.Cell2(None) # ヘッダ
head.next = head # 循環リスト
head.prev = head
self.size = 0
self.head = head
# 後ろに追加
def push_back(self, x):
h = self.head
p = h.prev
q = Deque.Cell2(x, h, p)
h.prev = q
p.next = q
self.size += 1
# 先頭に追加
def push_front(self, x):
h = self.head
q = h.next
p = Deque.Cell2(x, q, h)
h.next = p
q.prev = p
self.size += 1
# 最後尾のデータを取り出す
def pop_back(self):
if self.size == 0: raise IndexError
h = self.head
q = h.prev
p = q.prev
p.next = h
h.prev = p
self.size -= 1
return q.data
# 先頭のデータを取り出す
def pop_front(self):
if self.size == 0: raise IndexError
h = self.head
q = h.next
p = q.next
p.prev = h
h.next = p
self.size -= 1
return q.data
# 最後尾のデータを返す
def peek_back(self):
if self.size == 0: raise IndexError
return self.head.prev.data
# 先頭のデータを返す
def peek_front(self):
if self.size == 0: raise IndexError
return self.head.next.data
# 空か
def isEmpty(self): return self.size == 0
# 表示
def __str__(self):
if self.size == 0: return 'Deque()'
buff = 'Deque('
n = self.size
cp = self.head.next
while n > 1:
buff += '%s, ' % cp.data
cp = cp.next
n -= 1
buff += '%s)' % cp.data
return buff
# テスト
if __name__ == '__main__':
q = Deque()
print q.isEmpty()
for x in range(5):
q.push_front(x)
q.push_back(x * 10)
print q
print q.peek_front()
print q.peek_back()
print q.isEmpty()
for x in range(5):
print q.pop_front()
print q.pop_back()
print q
リスト : リングバッファによるキューの実装
class Queue:
# 初期化
def __init__(self, n = 16):
self.size = n
self.buff = [None] * n
self.front = 0
self.rear = 0
self.count = 0
# データの追加
def enqueue(self, x):
if self.count == self.size: raise IndexError
self.buff[self.rear] = x
self.rear += 1
if self.rear == self.size: self.rear = 0
self.count += 1
# データの取り出し
def dequeue(self):
if self.count == 0: raise IndexError
data = self.buff[self.front]
self.front += 1
if self.front == self.size: self.front = 0
self.count -= 1
return data
# 先頭のデータを求める
def peek(self):
if self.count == 0: raise IndexError
return self.buff[self.front]
# 空か
def isEmpty(self): return self.count == 0
# 満杯か
def isFull(self): return self.count == self.size
# 表示
def __str__(self):
if self.count == 0: return 'Queue()'
buff = 'Queue('
n = self.count
i = self.front
while n > 1:
buff += '%s, ' % self.buff[i]
i += 1
if i == self.size: i = 0
n -= 1
buff += '%s)' % self.buff[i]
return buff
# テスト
if __name__ == '__main__':
q = Queue(8)
x = 0
while not q.isFull():
q.enqueue(x)
x += 1
print q
while not q.isEmpty():
print q.dequeue()
print q