# فصل ۰۷ — `stack` و `queue`: دو انضباط روی یک داده

<div dir="rtl">

# فصل ۰۷ — `stack` و `queue`: دو انضباط روی یک داده

## در این فصل چه یاد می‌گیری

`deque` تا اینجا دو بار برنده شده و ما هنوز نگفته‌ایم چیست. این فصل می‌گوید — ولی از راهِ درستش، یعنی از راهِ **دو انضباطی که ظرف‌ها برایشان انتخاب می‌شوند.**

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

![دیسپنسرِ فنری که فقط بشقابِ رویی را می‌دهد، کنارِ ریلی که بشقابِ اولی را](/lesson-assets/t2-s07-stack-queue/prompt/01-image-two-disciplines.png)

آخر این فصل می‌توانی:

- `LIFO` و `FIFO` را روی یک مثالِ هشت‌تایی با دست دنبال کنی
- یک `stack` با `list` بسازی و یک `queue` با `deque`
- **با عدد** بگویی چرا `queue` با `list` ساخته نمی‌شود

## قبل از شروع

**از فصلِ ۴:** `pop()` در برابرِ `pop(0)`، و اینکه `deque` هر دو سر را ارزان می‌کند.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-2-arrays-and-lists/session-07-stack-queue.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. دو انضباط، با دست

`stack` و `queue` **ساختارِ داده نیستند؛ انضباط‌اند** — قاعده‌هایی دربارهٔ اینکه اجازه داری از کجا اضافه کنی و از کجا برداری.

- **`stack`** — اضافه در انتها، برداشتن از انتها. آخرین چیزی که گذاشتی، اولین چیزی است که برمی‌داری: `LIFO`.
- **`queue`** — اضافه در انتها، برداشتن از **ابتدا**. اولین چیزی که گذاشتی، اولین چیزی است که برمی‌داری: `FIFO`.

هشت حرف را از هر دو رد می‌کنیم و ترتیبِ خروج را نگاه می‌کنیم.

</div>

```python
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))
```

```text
ورودی       : 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
```

<div dir="rtl">

**`stack` ترتیب را برعکس می‌کند و `queue` نگهش می‌دارد.** این تمامِ تفاوتشان است و همین تفاوت تعیین می‌کند کدامشان به کدام کار می‌خورد: `stack` وقتی خوب است که «آخرین کارِ نیمه‌تمام» را می‌خواهی و `queue` وقتی که «قدیمی‌ترین کارِ منتظر» را.

## ۲. `stack` با `list`

**`stack` با `list` هیچ مشکلی ندارد**، چون هر دو عملیاتش در انتهاست: `append` و `pop()`. و هر دو را در فصل‌های ۳ و ۴ اندازه گرفتیم.

> 🤔 **اول حدس بزن:** ستونِ نسبتِ «`n` بار `push` و بعد `n` بار `pop`» چه عددی می‌دهد؟

</div>

```python
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])
```

```text-approx
جوابِ درست است؟ 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
```

<div dir="rtl">

**نسبتِ `2`: کلِ `2n` عملیات روی هم `O(n)` است، یعنی هر عمل به‌طورِ `amortised` ثابت.** برای `stack`، `list` ظرفِ درست است و لازم نیست دنبالِ چیزِ دیگری بگردی.

## ۳. یک کاربردِ واقعیِ `stack`

قبل از رفتن سراغِ `queue`، یک نمونهٔ کوتاه که نشان می‌دهد `stack` چرا اصلاً وجود دارد: **بررسیِ اینکه پرانتزها درست بسته شده‌اند یا نه.**

</div>

```python
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)}")
```

```text
 '(a[b]{c})' -> True
   '(a[b)c]' -> False
      '((()' -> False
          '' -> True
     'a(b)c' -> True
```

<div dir="rtl">

**آخرین پرانتزِ باز، اولین پرانتزی است که باید بسته شود** — و این دقیقاً `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` چند برابر با هم فاصله دارند.

</div>

```python
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")
```

```text-approx
دو نسخه یک جواب می‌دهند؟ 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
```

<div dir="rtl">

**`4` در برابرِ `2`.** `queue` با `list` درجه‌دو است و با `deque` خطی.

**و حالا عددِ صریحِ فاصله، که همان چیزی است که ردیفِ این فصل در نقشهٔ درسی وعده داده:**

</div>

```python
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}")
```

```text-approx
         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
```

<div dir="rtl">

**نسبت خودش با `n` بزرگ می‌شود: از حدودِ ده برابر به چند ده برابر.** این امضای مقایسهٔ یک `O(n²)` با یک `O(n)` است — **فاصله ثابت نیست، خودش رشد می‌کند.** اگر همین جدول را تا `n = 640,000` ادامه بدهی، نسبت هم هشت برابرِ سطرِ آخر می‌شود.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک `queue` با `list` و یک `queue` با `deque`، با جوابِ عددیِ برابرِ تأییدشده. **در کدام بازهٔ `n`؟** ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ — و بالاتر نرفتیم چون نسخهٔ `list` در `n = 160,000` تنهایی چند ثانیه می‌شود. **با چند تکرار، و کمینه یا میانگین؟** دو تکرار به‌علاوهٔ گرم‌کننده، کمینه، هر اجرا با ظرفِ تازه.

## ۵. `deque` چه چیزی را در ازایش می‌دهد

هیچ ظرفی مجانی بهتر نیست. **`deque` هر دو سرش ارزان است چون داخلش یک نوارِ پیوستهٔ واحد نیست** — چند تکهٔ پیوسته است که به هم وصل شده‌اند، و برای همین می‌شود از هر دو سر بدونِ جابه‌جایی اضافه و کم کرد.

**بهایش هم دقیقاً از همین‌جا می‌آید:** رفتن به خانهٔ شمارهٔ `i` دیگر یک ضرب و یک جمع نیست.

</div>

```python
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}")
```

```text-approx
    موقعیت     list (µs)    deque (µs)
     ابتدا        0.0196        0.0303
       وسط        0.0215        6.4095
     انتها        0.0200        0.0287
```

<div dir="rtl">

**در دو سرِ `deque` خواندن به‌ارزانیِ `list` است و در وسطش صدها برابر گران‌تر.** `list` هر سه موقعیت را یکسان می‌خواند — همان `O(1)`ِ فصلِ ۱.

**پس قاعدهٔ انتخاب یک جملهٔ ساده است: اگر فقط با دو سرِ دنباله کار داری، `deque`؛ اگر با اندیس‌های وسط کار داری، `list`.** فصلِ بعد این جمله را به یک جدولِ کامل تبدیل می‌کند.

> 🔧 **اگر کار نکرد:** هر دو ظرف روی ظرفِ خالی می‌شکنند، ولی اگر `queue` را با `list` نوشته باشی، خطا شکلِ دیگری هم دارد:

</div>

```python
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}")
```

```text
IndexError: pop from an empty deque
TypeError: deque.pop() takes no arguments (1 given)
```

<div dir="rtl">

**پیامِ دوم خیلی گویاست:** `deque.pop` اصلاً اندیس قبول نمی‌کند. این یک محدودیتِ سلیقه‌ای نیست — **`deque` عمداً کاری را که نمی‌تواند ارزان انجام بدهد، اصلاً پیشنهاد نمی‌کند.** اگر کدِ `list`ی‌ات را به `deque` منتقل کردی و این خطا را گرفتی، همان‌جا فهمیده‌ای که یک `pop(0)`ِ پنهان داشته‌ای.

> 🤖 **از دستیارت بپرس:** «تفاوتِ `LIFO` و `FIFO` را با یک مثالِ روزمره توضیح بده.» بعد این را هم بپرس: **«چرا در پایتون برای `queue` از `deque` استفاده می‌کنیم ولی برای `stack` از `list` کافی است؟»** — جوابِ درست باید بگوید هر دو عملیاتِ `stack` در انتهای ظرف‌اند و `queue` یک سرِ دیگر هم لازم دارد.

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| stack | استَک | انضباطی که آخرین ورودی را اول برمی‌دارد |
| queue | کیو | انضباطی که اولین ورودی را اول برمی‌دارد |
| LIFO | لایفو | آخرین ورودی، اولین خروجی |
| FIFO | فایفو | اولین ورودی، اولین خروجی |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا `stack` با `list` مشکلی ندارد ولی `queue` دارد؟

**تمرینِ اجباری:** `balanced` را طوری گسترش بده که به‌جای `True`/`False`، **جای اولین خطا** را برگرداند: اندیسِ نویسه‌ای که با آن پرانتز مشکل پیدا شد، یا `-1` اگر همه‌چیز درست بود. (راهنمایی: به‌جای خودِ نویسه، جفتِ `(نویسه, اندیس)` را در `stack` بگذار.) با پنج نمونهٔ همین فصل امتحانش کن. **بعد یک جدولِ چهار اندازه‌ای بگیر روی متنی که طولش دو برابر می‌شود** و مرتبه‌اش را اعلام کن.

**تمرینِ ستاره‌دار ⭐:** یک `queue` بساز که **فقط از دو `list` استفاده کند** و هزینهٔ `amortised`ِ ثابت داشته باشد: یک `list` برای ورودی و یک `list` برای خروجی؛ وقتی `list`ِ خروجی خالی شد، همهٔ ورودی را یکجا برعکس داخلش بریز. **قبل از اجرا پیش‌بینی کن ستونِ نسبتش چه می‌شود** و بنویس چرا — به فصلِ ۳ و تحلیلِ `amortised` برگرد. بعد جدولش را بگیر و با هر دو نسخهٔ بخشِ ۴ مقایسه کن. **اگر از `deque` کندتر درآمد ولی ستونِ نسبتش `2` بود، این یک شکست نیست؛ بنویس دقیقاً چه چیزی را ثابت کردی.**

## در فصل بعد

سه ظرف داریم و هر کدام در جایی برنده‌اند. **فصلِ بعد به‌جای یک ظرفِ تازه، یک جدول می‌سازد:** هزینهٔ هر عملیاتِ اصلی، روی هر ظرف، **اندازه‌گیری‌شده نه نقل‌شده**. بعد نشان می‌دهد که با عوض کردنِ **نسبتِ خواندن به نوشتن** در یک بارِ کاریِ ثابت، برنده کاملاً جابه‌جا می‌شود — در یک حالت `list` بیش از ده برابر جلو است و در حالتِ دیگر `deque` صدها برابر. و آخر، دو ظرفِ تازه برای وقتی که **حافظه** دیوار است: `array` و `bytearray`.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t2/s07-stack-queue (یادستان, Yaadestan)
