【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
4-2 キュー
キューはデータ構造の一つで、先入先出の機構です。(レジの行列のイメージ)
キューに追加する操作をエンキュー、取り出す操作をデキューと呼び、取り出される側を先頭、データが押し込まれる側を末尾と呼びます。
| コラム4-5 優先度付キュー |
|---|
優先度付のキューを追加するとデキューする際に優先度順に取り出すことができる。
heapqモジュールで提供されており、heapq.heappsh(heap, data)でキューを、heap.heappop(heap)でデキューをします。(6章でまた扱います)
リングバッファーによるキューの実現
デキューの際に配列内の要素をずらすことなくキューを実現するために用いるのがリングバッファーです。(切られたピザのようなイメージ)
先頭と末尾はfrontとrearで管理します。
リングバッファーを使うことで、要素の移動が不要になり、計算量はO(1)となります。
list4-3
#固定長キュークラス
from typing import Any
class FixedQueue:
class Empty(Exception):
"""空のFixedQueueに対してdequeあるいはpeekが呼び出されたときに送出する例外"""
class Full(Exception):
"""満杯のFixedQueueに対してenpueが呼び出されたときに送出する例外"""
pass
def __init__(self, capacity: int) -> None:
"""初期化"""
self.no = 0 #現在のデータ数
self.front = 0 #先頭要素カーソル
self.rear = 0 #末尾要素カーソル
self.capacity = capacity #キューの容量
self.que = [None] * capacity #キューの本体
def __len__(self) -> int:
"""キューに押し込まれているデータ数を返す"""
return self.no
def is_empty(self) -> bool:
"""キューは空であるか"""
return self.no <= 0
def is_full(self) -> bool:
"""キューは満杯か"""
return self.no >= self.capacity
def enque(self, x: Any) -> None:
"""データxをエンキュー"""
if self.is_full():
raise FixedQueue.Full
self.que[self.rear] = x
self.rear += 1
self.no += 1
if self.rear == self.capacity:
self.rear = 0
def deque(self) -> Any:
"""データをデキュー"""
if self.is_empty():
raise FixedQueue.Empty
x = self.que[self.front]
self.front += 1
if self.front == self.capacity:
self.front = 0
return x
def peek(self) -> Any:
"""データをピーク(先頭データをのぞく)"""
if self.is_empty():
raise FixedQueue.Empty #キューは空
return self.que[self.front]
def find(self, value: Any) -> Any:
"""キューからvalueを探して添字(見つからなければ-1)を返す"""
for i in range(self.no):
idx = (i + self.front) % self.capacity
if self.que[idx] == value: #探索成功
return idx
return -1 #探索失敗
def count(self, value: Any) -> bool:
"""キューに含まれるvalueの個数を返す"""
c = 0
for i in range(self.no): #底側から線形探索
idx = (i + self.front) % self.capacity
if self.que[idx] == value:
c += 1
return c
def __contains__(self, value: Any) -> bool:
"""キューにvalueは含まれているか"""
return self.count(value)
def clear(self) -> None:
"""キューを空にする"""
self.no = self.front = self.rear = 0
def dump(self) -> None:
"""全データを先頭→末尾の順に表示"""
if self.is_empty():
print('キューは空です')
else:
for i in range(self.no):
print(self.que[(i + self.front) % self.capacity], end=' ')
print()
list4-4
#固定長スタックStackの利用例
from enum import Enum
#from fixed_queue import FixedQueue
Menu = Enum('Menu', ['エンキュー', 'デキュー', 'ピーク', '探索', 'ダンプ', '終了'])
def select_menu() -> Menu:
"""メニュー選択"""
s = [f'({m.value}){m.name}' for m in Menu]
while True:
print(*s, sep=' ', end='' )
n = int(input('：'))
if 1 <= n <= len(Menu):
return Menu(n)
q = FixedQueue(64) #最大64個プッシュできるスタック
while True:
print(f'現在のデータ数：{len(q)} / {q.capacity}')
menu = select_menu() #メニュー選択
if menu == Menu.エンキュー: #エンキュー
x = int(input('データ：'))
try:
q.enque(x)
except FixedQueue.Full:
print('キューが満杯です。')
elif menu == Menu.デキュー: #デキュー
try:
x = q.deque()
print(f'デキューしたデータは{x}です。')
except FixedQueue.Empty:
print('キューが空です。')
elif menu == Menu.ピーク: #ピーク
try:
x = q.peek()
print(f'ピークしたデータは{x}です。')
except FixedQueue.Empty:
print('キューが空です。')
elif menu == Menu.探索: #探索
x = int(input('値：'))
if x in q:
print(f'{q.count(x)}個含まれ先頭の位置は{q.find(x)}です。')
else:
print('その値は含まれません。')
elif menu == Menu.ダンプ:
q.dump()
else:
break
| コラム4-6 両方向待ち行列(デック) |
|---|
デックと呼ばれる両方向待ち行列は、先頭末尾両方からデータの押し込み・取出しが行えるデータ構造で、collections.dequeとして提供されています。
| コラム4-7 リングバッファの応用例 |
|---|
list4C-2
#好きな個数だけ値を読み込んで要素数nの配列に最後のn個を格納
n = int(input('何個の整数を記憶しますか：'))
a = [None] * n #読み込んだ値を格納する配列
cnt = 0
while True:
a[cnt % n] = int(input((f'{cnt + 1}個目の整数：')))
cnt += 1
retry = input(f'続けますか？(Y…Yes / N…No) ：')
if retry in {'N', 'n'}:
break
i = cnt - n
if i < 0: i = 0
while i < cnt:
print(f'{i + 1}個目={a[i % n]}')
i += 1
以上です。今回で4章が終了です。
ありがとうございました。