در این فصل چه یاد میگیری#
deque تا اینجا دو بار برنده شده و ما هنوز نگفتهایم چیست. این فصل میگوید — ولی از راهِ درستش، یعنی از راهِ دو انضباطی که ظرفها برایشان انتخاب میشوند.
stack آخرین ورودی را اول برمیدارد و queue اولین ورودی را اول. همان داده، همان ظرف، فقط قاعدهٔ برداشتن فرق میکند — و همین یک تفاوت باعث میشود یکی از این دو با list عالی کار کند و دیگری با list یک فاجعهٔ درجهدو باشد. در n = 80,000 فاصلهشان چند ده برابر است.

آخر این فصل میتوانی:
LIFOوFIFOرا روی یک مثالِ هشتتایی با دست دنبال کنی- یک
stackباlistبسازی و یکqueueباdeque - با عدد بگویی چرا
queueباlistساخته نمیشود
قبل از شروع#
از فصلِ ۴: pop() در برابرِ pop(0)، و اینکه deque هر دو سر را ارزان میکند.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. دو انضباط، با دست#
stack و queue ساختارِ داده نیستند؛ انضباطاند — قاعدههایی دربارهٔ اینکه اجازه داری از کجا اضافه کنی و از کجا برداری.
stack— اضافه در انتها، برداشتن از انتها. آخرین چیزی که گذاشتی، اولین چیزی است که برمیداری:LIFO.queue— اضافه در انتها، برداشتن از ابتدا. اولین چیزی که گذاشتی، اولین چیزی است که برمیداری:FIFO.
هشت حرف را از هر دو رد میکنیم و ترتیبِ خروج را نگاه میکنیم.
from collections import deque
letters = ["a", "b", "c", "d", "e", "f", "g", "h"]
stack = []
out_stack = []
for x in letters:
stack.append(x)
while stack:
out_stack.append(stack.pop())
queue = deque()
out_queue = []
for x in letters:
queue.append(x)
while queue:
out_queue.append(queue.popleft())
print("ورودی :", " ".join(letters))
print("stack (LIFO):", " ".join(out_stack))
print("queue (FIFO):", " ".join(out_queue))
ورودی : a b c d e f g h
stack (LIFO): h g f e d c b a
queue (FIFO): a b c d e f g h
stack ترتیب را برعکس میکند و queue نگهش میدارد. این تمامِ تفاوتشان است و همین تفاوت تعیین میکند کدامشان به کدام کار میخورد: stack وقتی خوب است که «آخرین کارِ نیمهتمام» را میخواهی و queue وقتی که «قدیمیترین کارِ منتظر» را.
۲. stack با list#
stack با list هیچ مشکلی ندارد، چون هر دو عملیاتش در انتهاست: append و pop(). و هر دو را در فصلهای ۳ و ۴ اندازه گرفتیم.
🤔 اول حدس بزن: ستونِ نسبتِ «
nبارpushو بعدnبارpop» چه عددی میدهد؟
def run_stack(n):
st = []
for i in range(n):
st.append(i)
total = 0
while st:
total += st.pop()
return total
STACK = [100_000, 200_000, 400_000, 800_000]
print("جوابِ درست است؟", run_stack(1_000) == sum(range(1_000)))
table([(n, 1000 * clock(lambda k=n: run_stack(k), repeat=3)) for n in STACK])
جوابِ درست است؟ True
n زمان (ms) نسبت به سطر قبل
100,000 7.3 —
200,000 16.8 2.32
400,000 32.7 1.94
800,000 68.0 2.08
نسبتِ 2: کلِ 2n عملیات روی هم O(n) است، یعنی هر عمل بهطورِ amortised ثابت. برای stack، list ظرفِ درست است و لازم نیست دنبالِ چیزِ دیگری بگردی.
۳. یک کاربردِ واقعیِ stack#
قبل از رفتن سراغِ queue، یک نمونهٔ کوتاه که نشان میدهد stack چرا اصلاً وجود دارد: بررسیِ اینکه پرانتزها درست بسته شدهاند یا نه.
def balanced(text):
"""آیا هر پرانتزِ باز، با همان نوعِ خودش و به ترتیبِ درست بسته شده؟"""
pairs = {")": "(", "]": "[", "}": "{"}
st = []
for ch in text:
if ch in "([{":
st.append(ch)
elif ch in pairs:
if not st or st.pop() != pairs[ch]:
return False
return not st
for sample in ["(a[b]{c})", "(a[b)c]", "((()", "", "a(b)c"]:
print(f"{sample!r:>12} -> {balanced(sample)}")
'(a[b]{c})' -> True
'(a[b)c]' -> False
'((()' -> False
'' -> True
'a(b)c' -> True
آخرین پرانتزِ باز، اولین پرانتزی است که باید بسته شود — و این دقیقاً LIFO است. کلِ الگوریتم یک stack است و یک حلقه، و هزینهاش O(n) روی طولِ متن.
✅ چک کن:
st.pop()را بهst.pop(0)تغییر بده و همان پنج نمونه را بزن."(a[b)c]"باید ازFalseبهTrueبرود — یعنی جوابِ غلط.queueکردنِ یکstackاینجا فقط کند نمیکند، جواب را عوض میکند.
۴. queue با list در برابرِ queue با deque#
queue از ابتدا برمیدارد. با list این یعنی pop(0) — و فصلِ ۴ نشان داد که چه هزینهای دارد.
🤔 اول حدس بزن: دو جدول میگیریم:
queueباlistوqueueباdeque. ستونِ نسبتِ هر کدام را حدس بزن، و بعد حدس بزن درn = 80,000چند برابر با هم فاصله دارند.
def run_queue_list(n):
q = []
for i in range(n):
q.append(i)
total = 0
while q:
total += q.pop(0)
return total
def run_queue_deque(n):
q = deque()
for i in range(n):
q.append(i)
total = 0
while q:
total += q.popleft()
return total
QUEUE = [10_000, 20_000, 40_000, 80_000]
print("دو نسخه یک جواب میدهند؟", run_queue_list(1_000) == run_queue_deque(1_000))
print("\n— queue با list و pop(0)")
table([(n, 1000 * clock(lambda k=n: run_queue_list(k), repeat=2)) for n in QUEUE],
"زمان (ms)", ",.2f")
print("\n— queue با deque و popleft()")
table([(n, 1000 * clock(lambda k=n: run_queue_deque(k), repeat=2)) for n in QUEUE],
"زمان (ms)", ",.2f")
دو نسخه یک جواب میدهند؟ True
— queue با list و pop(0)
n زمان (ms) نسبت به سطر قبل
10,000 5.02 —
20,000 21.25 4.23
40,000 96.69 4.55
80,000 447.14 4.62
— queue با deque و popleft()
n زمان (ms) نسبت به سطر قبل
10,000 0.65 —
20,000 1.32 2.04
40,000 2.76 2.09
80,000 5.86 2.12
4 در برابرِ 2. queue با list درجهدو است و با deque خطی.
و حالا عددِ صریحِ فاصله، که همان چیزی است که ردیفِ این فصل در نقشهٔ درسی وعده داده:
print(f"{'n':>10}{'list (ms)':>14}{'deque (ms)':>14}{'list ÷ deque':>16}")
for n in QUEUE:
a = 1000 * clock(lambda k=n: run_queue_list(k), repeat=2)
b = 1000 * clock(lambda k=n: run_queue_deque(k), repeat=2)
print(f"{n:>10,}{a:>14.2f}{b:>14.2f}{a / b:>16,.1f}")
n list (ms) deque (ms) list ÷ deque
10,000 6.33 0.62 10.3
20,000 25.11 1.22 20.6
40,000 85.07 2.77 30.7
80,000 501.66 5.79 86.6
نسبت خودش با n بزرگ میشود: از حدودِ ده برابر به چند ده برابر. این امضای مقایسهٔ یک O(n²) با یک O(n) است — فاصله ثابت نیست، خودش رشد میکند. اگر همین جدول را تا n = 640,000 ادامه بدهی، نسبت هم هشت برابرِ سطرِ آخر میشود.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک
queueباlistو یکqueueباdeque، با جوابِ عددیِ برابرِ تأییدشده. در کدام بازهٔn؟ ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ — و بالاتر نرفتیم چون نسخهٔlistدرn = 160,000تنهایی چند ثانیه میشود. با چند تکرار، و کمینه یا میانگین؟ دو تکرار بهعلاوهٔ گرمکننده، کمینه، هر اجرا با ظرفِ تازه.
۵. deque چه چیزی را در ازایش میدهد#
هیچ ظرفی مجانی بهتر نیست. deque هر دو سرش ارزان است چون داخلش یک نوارِ پیوستهٔ واحد نیست — چند تکهٔ پیوسته است که به هم وصل شدهاند، و برای همین میشود از هر دو سر بدونِ جابهجایی اضافه و کم کرد.
بهایش هم دقیقاً از همینجا میآید: رفتن به خانهٔ شمارهٔ i دیگر یک ضرب و یک جمع نیست.
BIG = 200_000
lst = list(range(BIG))
dq = deque(range(BIG))
READS = 20_000
def read_at(box, pos, times=READS):
seen = None
for _ in range(times):
seen = box[pos]
return seen
print(f"{'موقعیت':>10}{'list (µs)':>14}{'deque (µs)':>14}")
for name, pos in (("ابتدا", 0), ("وسط", BIG // 2), ("انتها", BIG - 1)):
a = 1e6 * clock(lambda p=pos: read_at(lst, p), repeat=3) / READS
b = 1e6 * clock(lambda p=pos: read_at(dq, p), repeat=3) / READS
print(f"{name:>10}{a:>14.4f}{b:>14.4f}")
موقعیت list (µs) deque (µs)
ابتدا 0.0196 0.0303
وسط 0.0215 6.4095
انتها 0.0200 0.0287
در دو سرِ deque خواندن بهارزانیِ list است و در وسطش صدها برابر گرانتر. list هر سه موقعیت را یکسان میخواند — همان O(1)ِ فصلِ ۱.
پس قاعدهٔ انتخاب یک جملهٔ ساده است: اگر فقط با دو سرِ دنباله کار داری، deque؛ اگر با اندیسهای وسط کار داری، list. فصلِ بعد این جمله را به یک جدولِ کامل تبدیل میکند.
🔧 اگر کار نکرد: هر دو ظرف روی ظرفِ خالی میشکنند، ولی اگر
queueرا باlistنوشته باشی، خطا شکلِ دیگری هم دارد:
try:
deque().popleft()
except IndexError as err:
print(f"{type(err).__name__}: {err}")
try:
deque([1, 2, 3]).pop(0)
except TypeError as err:
print(f"{type(err).__name__}: {err}")
IndexError: pop from an empty deque
TypeError: deque.pop() takes no arguments (1 given)
پیامِ دوم خیلی گویاست: deque.pop اصلاً اندیس قبول نمیکند. این یک محدودیتِ سلیقهای نیست — deque عمداً کاری را که نمیتواند ارزان انجام بدهد، اصلاً پیشنهاد نمیکند. اگر کدِ listیات را به deque منتقل کردی و این خطا را گرفتی، همانجا فهمیدهای که یک pop(0)ِ پنهان داشتهای.
🤖 از دستیارت بپرس: «تفاوتِ
LIFOوFIFOرا با یک مثالِ روزمره توضیح بده.» بعد این را هم بپرس: «چرا در پایتون برایqueueازdequeاستفاده میکنیم ولی برایstackازlistکافی است؟» — جوابِ درست باید بگوید هر دو عملیاتِstackدر انتهای ظرفاند وqueueیک سرِ دیگر هم لازم دارد.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| stack | استَک | انضباطی که آخرین ورودی را اول برمیدارد |
| queue | کیو | انضباطی که اولین ورودی را اول برمیدارد |
| LIFO | لایفو | آخرین ورودی، اولین خروجی |
| FIFO | فایفو | اولین ورودی، اولین خروجی |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
سه ظرف داریم و هر کدام در جایی برندهاند. فصلِ بعد بهجای یک ظرفِ تازه، یک جدول میسازد: هزینهٔ هر عملیاتِ اصلی، روی هر ظرف، اندازهگیریشده نه نقلشده. بعد نشان میدهد که با عوض کردنِ نسبتِ خواندن به نوشتن در یک بارِ کاریِ ثابت، برنده کاملاً جابهجا میشود — در یک حالت list بیش از ده برابر جلو است و در حالتِ دیگر deque صدها برابر. و آخر، دو ظرفِ تازه برای وقتی که حافظه دیوار است: array و bytearray.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.