Stack dan queue: LIFO vs FIFO dengan contoh Python

Masalah apa yang diselesaikan stack dan queue

Banyak program perlu mengingat item dan memprosesnya nanti dalam urutan tertentu. Stack memberi item terbaru lebih dulu, cocok untuk pekerjaan bersarang: pemanggilan fungsi, riwayat undo, pencocokan tanda kurung, dan depth-first search. Queue memberi item terlama lebih dulu, cocok untuk antrean yang adil: pekerjaan cetak, task scheduler, message queue, dan breadth-first search.

Keduanya adalah abstract data type: didefinisikan oleh operasinya, bukan oleh cara penyimpanannya. Anda bisa membangun salah satunya di atas array atau linked list.

Operasi dan istilahnya

Contoh langkah demi langkah: push dan pop

Masukkan 1, 2, dan 3 ke kedua struktur, lalu keluarkan dua item.

Implementasi di Python

list Python sudah merupakan stack yang baik: append dan pop() bekerja di ujung list dalam waktu O(1) amortized. Untuk queue, jangan pakai list.pop(0), karena ia menggeser semua elemen yang tersisa dan butuh O(n). Gunakan collections.deque, yang O(1) di kedua ujung.

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

Jika Anda ingin method bernama dan pesan error yang jelas, bungkus tipe bawaan dalam kelas kecil:

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

Soal stack klasik: tanda kurung seimbang

Untuk memeriksa bahwa setiap tanda kurung ditutup dengan urutan yang benar, push setiap tanda kurung buka. Saat menemukan tanda kurung tutup, elemen teratas stack harus pasangan pembukanya.

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

Ide yang sama dipakai untuk mengevaluasi ekspresi dalam notasi Polandia terbalik (reverse Polish notation), mengubah rekursi menjadi loop, dan menjalankan depth-first search: ganti call stack dengan list Anda sendiri.

Soal queue klasik: breadth-first search

Breadth-first search mengunjungi graf level demi level. Queue membuat hal itu terjadi: node yang ditemukan lebih dulu diproses lebih dulu.

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']

Kompleksitas waktu dan ruang

Amortized berarti append sesekali mengubah ukuran array di baliknya dan butuh O(n), tetapi dirata-ratakan atas banyak operasi, setiap operasi adalah O(1).

Varian dan kesalahan umum

• Deque (double-ended queue): tambah dan hapus di kedua ujung. collections.deque adalah salah satunya, dan ia bisa berperan sebagai stack sekaligus queue.
• Priority queue: mengeluarkan item terkecil (atau terbesar) lebih dulu, bukan yang terlama. Gunakan heapq; lihat halaman binary heap.
• Circular buffer: queue berukuran tetap yang disimpan dalam array dengan indeks yang berputar. deque(maxlen=n) membuang item terlama saat penuh.
• Queue yang thread-safe: queue.Queue untuk thread dan asyncio.Queue untuk coroutine akan menunggu (blocking) sampai ada item.
• Queue dari dua stack: push ke in-stack, dan saat out-stack kosong pindahkan semuanya. Setiap item hanya berpindah sekali, jadi operasinya O(1) amortized.