بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 34: پشته و صف Stacks and Queues

پشته (stack, LIFO) و صف (queue, FIFO) را با list و collections.deque پیاده می‌کنیم و در مسائل واقعی مثل بررسی پرانتزها، واگرد (undo) و زمان‌بندی به کار می‌بریم.

در این جلسه یاد می‌گیری

درس

پشته: آخرین واردشده، اولین خارج‌شده (LIFO). list.append و list.pop() روی انتهای لیست O(1) هستند؛ stack[-1] بالای پشته (peek) است. همیشه پیش از pop خالی نبودن را بررسی کنید.

stack = []
stack.append("open file")
stack.append("edit line 3")
print(stack.pop(), stack[-1], len(stack))

صف: اولین واردشده، اولین خارج‌شده (FIFO). list.pop(0) همه‌ی عناصر را جابه‌جا می‌کند (O(n))؛ collections.deque در هر دو سر O(1) است: append، popleft، appendleft، pop.

from collections import deque

queue = deque(["job1", "job2"])
queue.append("job3")
print(queue.popleft(), list(queue))

deque(maxlen=n) بافر چرخشی است: وقتی پر شد، افزودن از یک سر عنصری را از سر دیگر بیرون می‌اندازد. برای «آخرین n رویداد» یا لاگ‌های اخیر عالی است.

from collections import deque

recent = deque(maxlen=3)
for event in ["login", "view", "edit", "logout"]:
    recent.append(event)
print(list(recent))

پرانتزهای متوازن کاربرد کلاسیک پشته است: هر بازکننده را push کنید؛ با هر بسته‌کننده بالای پشته باید جفتش باشد. در پایان پشته باید خالی باشد. زمان O(n).

PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(text):
    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(balanced("f(a[1]) {x}"), balanced("(]"))

واگرد (undo) یعنی پشته‌ای از وضعیت‌ها یا عملیات‌های قبلی. برای redo پشته‌ی دوم لازم است و هر عمل جدید باید پشته‌ی redo را خالی کند؛ همان رفتار ویرایشگرهای واقعی.

doc, undo = "", []
for text in ["Hello", ", world"]:
    undo.append(doc)
    doc += text
doc = undo.pop()
print(doc)

مثال‌های این جلسه

چالش‌ها

  1. Reverse with a Stack (آسان)
  2. Service Queue (آسان)
  3. Recent Log Lines (آسان)
  4. Balanced Brackets (متوسط)
  5. Undo Editor (متوسط)
  6. Postfix Calculator (متوسط)
  7. Round Robin (متوسط)
  8. Bracket Error Position (سخت)
  9. Undo and Redo (سخت)
  10. Next Greater Element (سخت)
  11. Browser History (متوسط)
  12. Sliding Window Maximum (سخت)

بیشتر بخوان

← جلسه‌ی 33: مرتب‌سازی جلسه‌ی 35: درهم‌سازی و گراف‌ها →