【Python】キュー【アルゴリズム】

2023年1月11日

Pythonでアルゴリズムのキューの解説をします。

キュー

キュー(queue)はスタックと同様にデータを一時的に蓄えるためのデータ構造のひとつです。

キューのデータの出し入れは先入れ先出し(FIFO/First In First Out)です。

つまり最初に入れたデータが最初に取り出されます。

エンキューとデキュー

キューにデータを追加する操作をエンキュー(en-queue)、データを取り出す操作をデキュー(de-queue)といいます。

また、データがエンキューすることを押し込むともいいます。

キューにおいてデータが取り出される側を先頭(front)といい、データが押し込まれる側を末尾(rear)といいます。

下の図はエンキューとデキューの操作を表したもので、デキューは先頭側から、エンキューは末尾側で行われています。

キューにおけるエンキューとデキューなどの操作を配列を使って実現することを考えます。

エンキュー

配列queueには5、1が格納されているとします。

先頭を添字0にした場合queue[0] = 5、queue[1] = 1ということになります。

この配列に2をエンキューします。

末尾要素であるqueue[1]の後ろの要素queue[2]に2を格納することで完了します。

このとき他の要素を移動させる必要はありません。

デキュー

次に2がエンキューされた配列queueでデキューによりデータを取り出します。

先頭要素であるqueue[0]に格納された5を取り出すとともに、2番目以降のすべての要素をひとつ前に移動させる必要があります。

デキューするたびにこのような処理を行うのは効率的とは言えません。

リングバッファによるキュー

リングバッファ(ring buffer)は、配列の末尾要素の後ろに先頭要素がつながっているとみなすデータ構造です。

そのためデキューの際に必要だった要素の移動が不要になります。

リングバッファでは、どの要素が論理的な先頭要素であって、どの要素が論理的な末尾要素であるかを識別する必要があります。

そのために使用する変数がfrontとrearです。

先頭要素を表すのがfrontで、末尾要素のひとつ後ろの要素を表すのがrearです。

rearが末尾要素そのものでないのは次にエンキューされる要素がどこかを認識するためです。

エンキューやデキューを行うとfrontとrearの値が変化します。

それぞれどのように変化するのかを見ていきます。

キューに要素がある

7個のデータ38、64、15、76、42、51、23がこの並びの順で、

queue[7]、queue[8]、…、queue[11]、queue[0]、queue[1]で格納されています(上の図)。

このときfrontの値は7で、rearの値は2です。

87をエンキュー

キューqueueに87をエンキューします。

末尾要素の次の要素であるqueue[rear]すなわちqueue[2]に87を格納します。

そしてrearの値をインクリメントして3とします。

38をデキュー

87をエンキューしたキューqueueに対してデキューします。

先頭要素であるqueue[front]すなわちqueue[7]の値である38を取り出します。

そしてfrontの値をインクリメントして8とします。

リングバッファによるキューを実現するプログラムの解説

リングバッファによりデキューの際でも要素を移動させる必要がなくなりました。

リングバッファを用いてキューを実現するプログラムを考えます。

今回も容量(押し込める最大データ数)を固定長としたキューとして考えます。

例外クラスEmptyとFull

# 固定長キュークラス

from typing import Any

class FixedQueue:

    class Empty(Exception):
        """空のFixedQueueに対してdequeまたはprint_dequeが呼び出された時に送出する例外"""
        pass

    class Full(Exception):
        """満杯のFixedQueueに対してenqueが呼び出された時に送出する例外"""
        pass

Emptyは空のキューに対してdequeメソッドやprint_dequeメソッドが呼び出された時に送出する例外です。

Fullは満杯のキューに対してenqueメソッドが呼び出された時に送出する例外です。

初期化__init__

def __init__(self, capacity: int) -> None:
        """初期化"""
        self.no = 0                     # 現在のデータ数
        self.front = 0                  # 先頭要素カーソル
        self.rear = 0                   # 末尾要素カーソル
        self.capacity = capacity        # キューの容量
        self.queue = [None] * capacity  # キュー本体

__init__メソッドではキュー本体用の配列を生成するなどの準備をします。

そのために次の5つのフィールドに値を設定します。

キュー本体用配列queue

押し込まれたデータを格納するキュー本体を表すlist型の配列です。

初期化時はすべてのデータが空の状態です。

キューの容量capacity

キューの容量(押し込める最大データ数)を表すint型の整数値です。

配列queueの要素数と一致します。

先頭要素カーソルfront
末尾要素カーソルrear

キューに格納されたデータの中で、最初に押し込まれた先頭要素の添字を表すのがfront、

最後に押し込まれた末尾要素のひとつ後ろの添字を表すのがrearです。

rearは次にエンキューが行われたときにデータが格納される要素の添字です。

データ数no

キューに押し込まれたデータ数を表すint型の整数値です。

変数frontとrearが等しいときに、キューが空か満杯なのかを区別するために必要になります。

キューが空の時はnoの値は0、満杯の時はcapacityと同じ値になります。

左側は空の状態で変数frontとrearの値は等しくなります。

右側は満杯の状態でこちらでもfrontとrearの値は等しくなります。

(queue[2]が先頭要素、queue[1]が末尾要素)

データ数を調べる__len__

def __len__(self) -> int:
        """キューに押し込まれているデータ数を返却"""
        return self.no

__len__メソッドではキューに押し込まれているデータ数を返却します。

noの値を返却します。

空であるかを判定するis_empty

def is_empty(self) -> bool:
        """キューは空であるか"""
        return self.no <= 0

is_emptyメソッドではキューが空(データが一つも押し込まれていない)かを判定します。

空ならTrue、空でなければFalseを返却します。

満杯であるかを判定するis_full

def is_full(self) -> bool:
        """キューは満杯であるか"""
        return self.no >= self.capacity

is_fullメソッドではキューが満杯(これ以上データを押し込むことができない)かを判定します。

満杯ならTrue、満杯でなければFalseを返却します。

エンキューenque

def enque(self, x: Any) -> None:
        """データxをエンキュー"""
        if self.is_full():
            raise FixedQueue.Full # キューが満杯
        self.queue[self.rear] = x
        self.rear += 1
        self.no += 1
        if self.rear == self.capacity:
            self.rear = 0

enqueメソッドではキューにデータをエンキューします。

ただし、キューが満杯の場合は例外FixedQueue.Fullを送出します。

下の図の左側は、先頭から順に38、64、15、76、42、51、23が格納されたキューに87をエンキューしています。

末尾要素queue[rear]すなわちqueue[2]にエンキューする87を格納して、rearとnoの値をインクリメントしています。

ところが、エンキュー前のrearが配列の物理的な末尾(図の場合は11)だった場合はインクリメントすると、

capacity(図の場合は12)と等しくなって配列の添字の上限を越えてしまいます。

その対策として上の図の右側のように、インクリメント後のrearの値がcapacityと等しくなった場合は、

rearを配列の物理的な先頭の添字である0に戻すようにします。

こうすることでqueue[0]にエンキューするデータが格納されるようになります。

デキューdeque

def deque(self) -> Any:
        """データをデキュー"""
        if self.is_empty():
            raise FixedQueue.Empty # キューが空
        x = self.queue[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:
            self.front = 0
        return x

dequeメソッドではデータをデキューしてその値を返却します。

ただし、キューが空の場合は例外FixedQueue.Emptyを送出します。

下の図の左側は、先頭から順に38、64、15、76、42、51、23、87が格納されたキューから先頭の38をデキューしています。

先頭要素queue[front]すなわちqueue[7]に格納された値38を取り出し、frontのインクリメントとnoのデクリメントを同時にしています。

ところが、デキュー前のfrontが配列の物理的な末尾(図の場合は11)だった場合はインクリメントすると、

capacity(図の場合は12)と等しくなって配列の添字の上限を越えてしまいます。

その対策として上の図の右側のように、インクリメント後のfrontの値がcapacityと等しくなった場合は、

frontを配列の物理的な先頭の添字である0に戻すようにします。

こうすることで次にデキューを行う際はqueue[0]のデータが取り出されるようになります。

デキューされるデータを表示print_deque

def print_deque(self) -> Any:
        """次にデキューされるデータ(先頭データ)を表示"""
        if self.is_empty():
            raise FixedQueue.Empty # キューが空
        return self.queue[self.front]

print_dequeメソッドでは先頭データつまり次にデキューで取り出されるデータを表示します。

queue[front]の値を返却するだけなので、エンキューやデキューのようにfront、rear、noの値は変化しません。

ただし、キューが空の場合は例外FixedQueue.Emptyを送出します。

探索search

def search(self, value: Any) -> Any:
        """キューからvalueを探して添字(見つからなければ-1)を返却"""
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.queue[idx] == value: # 探索成功
                return idx
        return -1                        # 探索失敗

searchメソッドではキューの配列からvalueと等しいデータが格納された位置を調べます。

下の図のように配列の論理的な先頭から末尾側へと線形探索します。

そのため操作において着目する添字idxの計算は(i + front) % capacityとなり、上の図の場合だと以下のように変化します。

i 0 1 2 3 4 5 6
idx 7 8 9 10 11 0 1

探索成功時は見つけた要素の添字を返却し、失敗時は-1を返却します。

要素をカウントcount

def count(self, value: Any) -> bool:
        """キューに含まれるvalueの個数を返却"""
        counter = 0
        for i in range(self.no):         # 底側から線形探索
            idx = (i + self.front) % self.capacity
            if self.queue[idx] == value: # 探索成功
                counter += 1             # 入っていた
        return counter

countメソッドではキューに含まれるvalueの個数を返却します。

データが含まれているかを判定__contains__

def __contains__(self, value: Any) -> bool:
        """キューにvalueは含まれているか"""
        return self.count(value)

__contains__メソッドではキューにvalueが含まれているかを判定します。

countメソッドを利用することにより実現しています。

含まれていればTrue、含まれていなければFalseを返却します。

全要素の削除clear

def clear(self) -> None:
        """キューを空にする"""
        self.no = self.front = self.rear = 0

clearメソッドではキューに押し込まれた全データを削除します。

エンキューやデキューはno、front、rearの値によって実現するのでそれらの値を0にするだけで完了します。

よってキュー本体用の配列queueの要素の値を変更する必要はありません。

全データの表示print

def print(self) -> None:
        """全データを先頭から末尾の順に表示"""
        if self.is_empty(): # キューが空
            print('キューが空です。')
        else:
            for i in range(self.no):
                print(self.queue[(i + self.front) % self.capacity], end=' ')
            print()

printメソッドではキューに押し込まれたすべて(no個)のデータを先頭から末尾の順に表示します。

ただし、キューが空の場合は「キューが空です。」と表示します。

キューを実現するプログラム

# 固定長キュークラス

from typing import Any

class FixedQueue:

    class Empty(Exception):
        """空のFixedQueueに対してdequeまたはprint_dequeが呼び出された時に送出する例外"""
        pass

    class Full(Exception):
        """満杯のFixedQueueに対してenqueが呼び出された時に送出する例外"""
        pass

    def __init__(self, capacity: int) -> None:
        """初期化"""
        self.no = 0                     # 現在のデータ数
        self.front = 0                  # 先頭要素カーソル
        self.rear = 0                   # 末尾要素カーソル
        self.capacity = capacity        # キューの容量
        self.queue = [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.queue[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.queue[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:
            self.front = 0
        return x

    def print_deque(self) -> Any:
        """次にデキューされるデータ(先頭データ)を表示"""
        if self.is_empty():
            raise FixedQueue.Empty # キューが空
        return self.queue[self.front]

    def search(self, value: Any) -> Any:
        """キューからvalueを探して添字(見つからなければ-1)を返却"""
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.queue[idx] == value: # 探索成功
                return idx
        return -1                        # 探索失敗

    def count(self, value: Any) -> bool:
        """キューに含まれるvalueの個数を返却"""
        counter = 0
        for i in range(self.no):         # 底側から線形探索
            idx = (i + self.front) % self.capacity
            if self.queue[idx] == value: # 探索成功
                counter += 1             # 入っていた
        return counter

    def __contains__(self, value: Any) -> bool:
        """キューにvalueは含まれているか"""
        return self.count(value)

    def clear(self) -> None:
        """キューを空にする"""
        self.no = self.front = self.rear = 0

    def print(self) -> None:
        """全データを先頭から末尾の順に表示"""
        if self.is_empty(): # キューが空
            print('キューが空です。')
        else:
            for i in range(self.no):
                print(self.queue[(i + self.front) % self.capacity], end=' ')
            print()

このプログラムは「fixed_queue.py」という名前で保存してください。

キューを利用するプログラム

コード例

# 固定長キュークラスFixedQueueの利用例

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.エンキュー:    # エンキュー
        enque_value = int(input('データ : '))
        try:
            q.enque(enque_value)
        except FixedQueue.Full:
            print('キューが満杯です。')

    elif menu == Menu.デキュー:    # デキュー
        try:
            deque_value = q.deque()
            print(f'デキューしたデータは{deque_value}です。')
        except FixedQueue.Empty:
            print('キューが空です。')

    elif menu == Menu.先頭を表示:  # 先頭を表示
        try:
            front_value = q.print_deque()
            print(f'先頭のデータは{front_value}です。')
        except FixedQueue.Empty:
            print('キューが空です。')

    elif menu == Menu.探索:        # 探索
        search_value = int(input('値 : '))
        if search_value in q:
            print(f'{search_value}は{q.count(search_value)}個含まれ、先頭の位置は{q.search(search_value)}です。')
        else:
            print('その値は含まれていません。')

    elif menu == Menu.全表示:      # 全表示
        q.print()

    else:                          # 終了
        break

実行結果

現在のデータ数 : 0 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 1
データ : 1
現在のデータ数 : 1 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 1
データ : 4
現在のデータ数 : 2 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 1
データ : 1
現在のデータ数 : 3 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 1
データ : 2
現在のデータ数 : 4 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 1
データ : 3
現在のデータ数 : 5 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 5
1 4 1 2 3
現在のデータ数 : 5 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 4
値 : 1
1は2個含まれ、先頭の位置は0です。
現在のデータ数 : 5 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 3
先頭のデータは1です。
現在のデータ数 : 5 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 2
デキューしたデータは1です。
現在のデータ数 : 4 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 2
デキューしたデータは4です。
現在のデータ数 : 3 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 5
1 2 3
現在のデータ数 : 3 / 64
(1)エンキュー (2)デキュー (3)先頭を表示 (4)探索 (5)全表示 (6)終了 : 6

このプログラムは「fixed_queue_test.py」という名前で「fixed_queue.py」と同じフォルダに保存してください。

アルゴリズム

Posted by ほりえりお