スタック・キューとリングバッファ
取り出し順の違いと、固定容量のリングバッファが空き領域を再利用する仕組みを学びます。
説明
スタックは最後に入れた要素から取り出すLIFO、キューは先に入れた要素から取り出すFIFOです。同じA・B・Cを入れても、取り出す順番が変わります。両端から追加・取り出しができるデータ構造はデックと呼びます。
最初にスタックとキューへ同じ値を入れます。その後、4個分の配列でキューを作り、先頭位置と使用数を更新して端から先頭へ折り返します。満杯と空の判定、最後にデックの両端操作まで扱います。
1後から入れた値を先に取り出す
スタックにはA・B・Cの順に追加します。末尾への追加と末尾からの取り出しを組み合わせます。
stack = []空のスタック; stack.extend(['A', 'B', 'C'])順に追加; first = stack.pop()末尾から取得; first, stack取得値と残り最初にCが取り出され、A・Bが残ります。操作の取り消しなど、直近の記録から処理したい場合にこの順序を使えます。
2先に入れた値を先に取り出す
キューでもA・B・Cを追加します。dequeは両端の操作を持ち、ここでは右から追加して左から取り出します。
from collections import dequeデックを利用; queue = deque(['A', 'B', 'C'])順に投入; first = queue.popleft()左端から取得; first, list(queue)取得値と残り最初にAが取り出され、B・Cが残ります。受付順に処理するならFIFOです。Pythonのlistの先頭削除とは異なり、dequeの両端操作では残る全要素をずらす必要がありません。
3固定容量のキュー
4個分の配列にA・B・Cを置きます。headは取り出す位置、countは使用数です。次に書く位置は(head+count)を容量で割った余りで求めます。
ring = ['A', 'B', 'C', None]4個分の領域; head = 0; count = 3先頭位置と使用数; capacity = len(ring)容量; (head, count, (head+count) % capacity), ring管理値と配置先頭0、使用数3、次の書き込み位置3です。実際の配列順と、キューとして取り出す順序は、折り返した後に一致しなくなります。
4先頭を一つ進める
Aを取り出した場所を空け、先頭位置を1進めます。BとCをコピーして前へ移動する必要はありません。
taken = ring[head]先頭の値を取得; ring[head] = Noneその場所を空ける; head = (head+1) % capacity先頭を進める; count -= 1使用数を減らす; taken, ring, head, count取得値と管理値Aが取れ、先頭は1、使用数は2です。配列の添字0が空きました。先頭を管理することで、要素を動かさず取り出せます。
5末尾まで書き込む
Dを次の書き込み位置へ入れます。位置は(1+2)%4で3です。
tail = (head+count) % capacity書き込み位置を計算; ring[tail] = 'D'Dを格納; count += 1使用数を増やす; tail, ring書き込み位置と配置Dは添字3へ入りました。キューの順序はB・C・Dで、次の書き込み位置は配列の先頭へ戻ります。
6先頭側の空きを再利用
Eを入れる位置は(1+3)%4で0です。余りを使うため、添字が容量を超えず先頭へ折り返します。
tail = (head+count) % capacity折り返し位置; ring[tail] = 'E'; count += 1Eを追加; ring配列上の配置, [ring[(head+i) % capacity] for i in range(count)]取り出す順に表示配列はE・B・C・Dですが、取り出す順序はB・C・D・Eです。物理的な並びだけを表示するとキューの順序を取り違えるため、先頭位置も必要になります。
7空と満杯の判定
現在は4個分を全て使用しています。先頭と次の書き込み位置が同じでも、使用数があれば空と満杯を判定できます。
head, (head+count) % capacity先頭と次の位置, count == 0空か, count == capacity満杯か先頭と次の位置はともに1ですが、空はFalse、満杯はTrueです。ここで無条件に書くと未処理のBを上書きします。追加前に満杯を判定し、拒否するか古い値を捨てるかを用途に合わせて決めます。
8デックの両端操作
デックへB・Cを入れ、左へA、右へDを追加します。左右から1個ずつ取り出します。
work = deque(['B', 'C'])初期値; work.appendleft('A'); work.append('D')左右へ追加; left = work.popleft(); right = work.pop()左右から取得; left, right, list(work)取得値と残り左からA、右からDが取れ、B・Cが残ります。デックは両端操作を提供する構造で、スタックやキューはどの端を使うかという取り出し規則です。
まとめ
スタックはLIFO、キューはFIFOです。同じ投入順でも取り出し順が変わります。
リングバッファでは先頭位置と使用数を更新し、剰余によって配列の空きを再利用します。
満杯時の扱いを決め、まだ取り出していない値を意図せず上書きしないようにします。
操作履歴と解説を振り返れます。
Python 3
stack = []; stack.extend(['A', 'B', 'C']); first = stack.pop(); first, stack('C', ['A', 'B'])from collections import deque; queue = deque(['A', 'B', 'C']); first = queue.popleft(); first, list(queue)('A', ['B', 'C'])ring = ['A', 'B', 'C', None]; head = 0; count = 3; capacity = len(ring); (head, count, (head+count) % capacity), ring((0, 3, 3), ['A', 'B', 'C', None])
taken = ring[head]; ring[head] = None; head = (head+1) % capacity; count -= 1; taken, ring, head, count('A', [None, 'B', 'C', None], 1, 2)tail = (head+count) % capacity; ring[tail] = 'D'; count += 1; tail, ring(3, [None, 'B', 'C', 'D'])
tail = (head+count) % capacity; ring[tail] = 'E'; count += 1; ring, [ring[(head+i) % capacity] for i in range(count)](['E', 'B', 'C', 'D'], ['B', 'C', 'D', 'E'])
head, (head+count) % capacity, count == 0, count == capacity(1, 1, False, True)
work = deque(['B', 'C']); work.appendleft('A'); work.append('D'); left = work.popleft(); right = work.pop(); left, right, list(work)('A', 'D', ['B', 'C'])演習完了