スタックとキューとは？LIFOとFIFOの違いをPythonで解説

スタックとキューが解決する問題

多くのプログラムは、要素を覚えておき、あとから決まった順序で処理する必要があります。スタックは最新の要素を最初に返すので、関数呼び出し、undo履歴、括弧の対応チェック、深さ優先探索のような入れ子になった処理に向いています。キューは最も古い要素を最初に返すので、印刷ジョブ、タスクスケジューラ、メッセージキュー、幅優先探索のような、公平な順番待ちに向いています。

どちらも抽象データ型で、内部の格納方法ではなく操作によって定義されます。配列でも連結リストでも、どちらでも実装できます。

操作と呼び方

具体例：pushとpopを1ステップずつ

1、2、3を両方のデータ構造に追加し、その後2回取り出します。

Pythonでの実装

Pythonのlistは、そのままスタックとして優れています。appendとpop()はリストの末尾に対して働き、償却O(1)です。キューにはlist.pop(0)を使わないでください。残りの要素をすべてずらすのでO(n)かかります。両端でO(1)のcollections.dequeを使いましょう。

from collections import deque
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop(), stack[-1])   # 3 2
queue = deque()
queue.append("a")
queue.append("b")
queue.append("c")
print(queue.popleft(), queue[0])  # a b
print(len(stack), len(queue))     # 2 2

メソッド名を分かりやすくし、エラーも明確にしたい場合は、組み込み型を小さなクラスで包みます。

from collections import deque
class Queue:
    def __init__(self):
        self._items = deque()
    def enqueue(self, item):
        self._items.append(item)
    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()
    def __len__(self):
        return len(self._items)
q = Queue()
q.enqueue("job1")
q.enqueue("job2")
print(q.dequeue(), len(q))  # job1 1

定番のスタック問題：括弧の対応チェック

すべての括弧が正しい順序で閉じられているか調べるには、開き括弧をすべてpushします。閉じ括弧が来たら、スタックの一番上がそれに対応する開き括弧でなければなりません。

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
print(is_balanced("f(a[1], {b: 2})"))  # True
print(is_balanced("(]"))               # False
print(is_balanced("(("))               # False

同じ考え方で、逆ポーランド記法の式の評価、再帰のループへの書き換え、深さ優先探索ができます。呼び出しスタックを、自分で用意したlistに置き換えるわけです。

定番のキュー問題：幅優先探索

幅優先探索は、グラフをレベルごとに訪問します。キューを使えば、先に発見したノードから先に処理されるので、これが実現できます。

from collections import deque
def bfs_order(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs_order(graph, "A"))  # ['A', 'B', 'C', 'D']

時間計算量と空間計算量

償却（amortized）とは、たまにappendで内部配列のサイズ変更が起きてO(n)かかるものの、多数の操作で平均すると1回あたりO(1)になる、という意味です。

種類と、よくある間違い

• デック（両端キュー）：両端で追加・削除ができます。collections.dequeがその一例で、スタックとしてもキューとしても使えます。
• 優先度付きキュー：最も古い要素ではなく、最小（または最大）の要素を最初に取り出します。heapqを使います。二分ヒープのページも参照してください。
• 循環バッファ：インデックスを折り返して配列に格納する固定サイズのキューです。deque(maxlen=n)は、満杯になると最も古い要素を捨てます。
• スレッドセーフなキュー：スレッド用のqueue.Queueとコルーチン用のasyncio.Queueは、要素が来るまで待機（ブロック）します。
• 2つのスタックで作るキュー：入力用スタックにpushし、出力用スタックが空になったら全要素を移し替えます。各要素が移るのは1回だけなので、操作は償却O(1)です。