「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#17

【出典】[「新・明解Pythonで学ぶアルゴリズムとデータ構造」](https://www.amazon.co.jp/%E6%96%B0%E3%83%BB%E6%98%8E%E8%A7%A3Python%E3%81%A7%E5%AD%A6%E3%81%B6%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%96%B0%E3%83%BB%E6%98%8E%E8%A7%A3%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E6%9F%B4%E7%94%B0%E6%9C%9B%E6%B4%8B/dp/4815603197/ref=sr_1_2?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&crid=1BG3JS7CKMZA0&keywords=Python%E3%81%A7%E5%AD%A6%E3%81%B6%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0&qid=1644336329&sprefix=python%E3%81%A7%E5%AD%A6%E3%81%B6%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0%2Caps%2C212&sr=8-2)
[前回の記事はこちら](https://qiita.com/kato_squalldeka/items/3afd84909196da4f3a99)


# 4-2 キュー
キューはデータ構造の一つで、先入先出の機構です。(レジの行列のイメージ)
キューに追加する操作をエンキュー、取り出す操作をデキューと呼び、取り出される側を先頭、データが押し込まれる側を末尾と呼びます。

|**コラム4-5 優先度付キュー**|
|-|

優先度付のキューを追加するとデキューする際に優先度順に取り出すことができる。
heapqモジュールで提供されており、heapq.heappsh(heap, data)でキューを、heap.heappop(heap)でデキューをします。(6章でまた扱います)

# リングバッファーによるキューの実現
デキューの際に配列内の要素をずらすことなくキューを実現するために用いるのがリングバッファーです。(切られたピザのようなイメージ)
先頭と末尾はfrontとrearで管理します。
リングバッファーを使うことで、要素の移動が不要になり、計算量はO(1)となります。

```python: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()
```   

```python: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 リングバッファの応用例**|
|-|

```python: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章が終了です。
ありがとうございました。