جلسهی 34: پشته و صف Stacks and Queues
پشته (stack, LIFO) و صف (queue, FIFO) را با list و collections.deque پیاده میکنیم و در مسائل واقعی مثل بررسی پرانتزها، واگرد (undo) و زمانبندی به کار میبریم.
در این جلسه یاد میگیری
- از
listباappend/popبهعنوان پشتهیO(1)استفاده کنید. - بدانید چرا
pop(0)برای صفO(n)است و ازdeque.popleftاستفاده کنید. - بررسیکنندهی پرانتزهای متوازن و ارزیاب عبارت پسوندی بنویسید.
- سازوکار
undo/redoو الگوی پشتهی یکنوا (monotonic stack) را پیاده کنید.
درس
پشته: آخرین واردشده، اولین خارجشده (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)مثالهای این جلسه
- مثال لیست در پایتون: stack = []
- مثال لیست در پایتون: queue.append("job3")
- مثال حلقه for در پایتون: for event in ["login", "view", "edit", "log…
- مثال تابع در پایتون: def balanced(text):
- مثال حلقه for در پایتون: for text in ["Hello", ", world"]:
چالشها
- Reverse with a Stack (آسان)
- Service Queue (آسان)
- Recent Log Lines (آسان)
- Balanced Brackets (متوسط)
- Undo Editor (متوسط)
- Postfix Calculator (متوسط)
- Round Robin (متوسط)
- Bracket Error Position (سخت)
- Undo and Redo (سخت)
- Next Greater Element (سخت)
- Browser History (متوسط)
- Sliding Window Maximum (سخت)