🥞 धडा 04 — Stacks आणि queues: ट्रेची चळत आणि जेवणाची रांग

📍 तुम्ही इथे आहात: 12 पैकी धडा 04 · पुढे: lesson-05-hash-maps

📦 या ब्रँचमध्ये काय आहे

धडे 01–04. तुम्ही कोणते टोक वापरता यावरून ठरणारे दोन containers, एका ओळीचा bracket checker, आणि सरकवासरकवी न करणारी queue.

dsa/structures.py — list वर Stack; ring buffer म्हणून Queue, जी भरली की दुप्पट होते
dsa/demo.py — stackqueue: ट्रे, जेवणाची रांग, balanced brackets

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

कॅन्टीनमध्ये स्वच्छ ट्रे एका चळतीवर ठेवतात: शेवटी ठेवलेला ट्रे आधी उचलला जातो (LIFO). विद्यार्थी रांगेत थांबतात: आधी आलेल्याला आधी जेवण मिळते (FIFO). दोन्ही अशा lists आहेत जिथे तुम्हाला फक्त एकच टोक हाताळायची परवानगी आहे — आणि हे बंधनच त्यांना उपयोगी बनवते: undo, brackets आणि call stack या चळती आहेत; printing, tasks आणि breadth-first search या रांगा आहेत.

🗺️ आकृती

flowchart LR
  subgraph stack["🥞 stack (LIFO)"]
    T3["tray 3 ← top"] --- T2["tray 2"] --- T1["tray 1"]
  end
  subgraph queue["🍽️ queue (FIFO)"]
    F["front: Aishwarya"] --- Q2["Katrina"] --- B["back: Dipika"]
  end

❓ काय

Stack: push, pop, peek — सगळे O(1). Python list हाच stack आहे (append/pop). उपयोग: balanced brackets, undo/redo, back button, DFS, call stack (धडा 06).
Queue: मागे enqueue, पुढून dequeue. list.pop(0) O(n) आहे (सगळे सरकतात). ring buffer एक head index ठेवतो आणि गोल फिरून परत येतो: O(1). प्रत्यक्ष कामात collections.deque हे साधन. उपयोग: BFS (धडा 10), job queues, rate limiters, API school ची जेवणाची रांग.
प्रकार: deque (दोन्ही टोके), priority queue (धडा 09 चा heap).

🤔 का

stack वापरून bracket checker सहा ओळींचा होतो आणि त्याशिवाय जवळजवळ अशक्य; queue शिवाय BFS ची कल्पनाच करता येत नाही. list.pop(0) मधला O(n) सापळा माहीत असला तर एक खरा outage वाचतो.

🔧 कसे (या repo मध्ये)

Queue items एका ठरलेल्या list मध्ये head आणि n सह ठेवते; dequeue head ला capacity च्या modulo ने पुढे सरकवतो; भरली की _grow दुप्पट आकाराच्या list मध्ये copy करतो. demo.py stackqueue bracket checker एका चांगल्या आणि एका वाईट string वर चालवतो.

🧪 करून पाहा

python3 dsa/demo.py stackqueue
python3 - <<'EOF'
import time
from collections import deque
n = 200_000
lst = list(range(n)); t = time.perf_counter()
while lst: lst.pop(0)                                  # the trap
print(f"list.pop(0) × {n}: {(time.perf_counter() - t) * 1000:.0f} ms")
dq = deque(range(n)); t = time.perf_counter()
while dq: dq.popleft()
print(f"deque.popleft() × {n}: {(time.perf_counter() - t) * 1000:.0f} ms")
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

चळतीवरून tray 3, tray 2; रांगेतून Aishwarya, Katrina यांना जेवण; brackets साठी आधी True मग False. list.pop(0) loop सेकंद घेतो; deque milliseconds घेते — O(n²) विरुद्ध O(n).

🏁 तुम्ही आत्ताच काय सिद्ध केले

list ला एकाच टोकापुरते बांधले की दोन structures मिळतात, आणि त्यांपैकी एकाला दिलेले वचन पाळायला ring buffer (किंवा deque) लागतो — आणि तुम्ही तो सापळा मोजलात.

⚠️ नेहमीच्या चुका

queue साठी list.pop(0).
pop करण्याआधी "stack रिकामा आहे का?" हे तपासायला विसरणे (unbalanced ) चे उदाहरण).
जिथे explicit stack ने depth limit टाळता आला असता तिथे recursion वापरणे (धडा 06).

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: message queues, undo stacks, request pipelines, event loop — प्रत्येक म्हणजे नाव दिलेला stack किंवा queue. network cards आणि logging libraries सरकवासरकवी टाळायला ring buffer वापरतात.

⏭️ पुढे

धडा 05 — hash maps आणि sets: नावानुसार कप्पे, भाषेतला सर्वात उपयोगी structure.

🥞 Lesson 04 — Stacks & queues: the tray pile and the lunch line

📍 You are here: Lesson 04 of 12 · Next: lesson-05-hash-maps

📦 What's in this branch

Lessons 01–04. Two containers defined by which end you use, the one-line bracket checker, and a queue that does not shuffle.

dsa/structures.py — Stack on a list; Queue as a ring buffer that doubles when full
dsa/demo.py — stackqueue: trays, the lunch line, balanced brackets

🧒 Explain like I'm 5

In the canteen, clean trays go on a pile: the last tray put on is the first one taken off (LIFO). Pupils wait in a line: first to join is first served (FIFO). Both are lists where you are only allowed to touch one end — and that restriction is exactly what makes them useful: undo, brackets and the call stack are piles; printing, tasks and breadth-first search are lines.

🗺️ Diagram

flowchart LR
  subgraph stack["🥞 stack (LIFO)"]
    T3["tray 3 ← top"] --- T2["tray 2"] --- T1["tray 1"]
  end
  subgraph queue["🍽️ queue (FIFO)"]
    F["front: Aishwarya"] --- Q2["Katrina"] --- B["back: Dipika"]
  end

❓ What

Stack: push, pop, peek — all O(1). A Python list is a stack (append/pop). Uses: balanced brackets, undo/redo, the back button, DFS, the call stack (lesson 06).
Queue: enqueue at the back, dequeue at the front. list.pop(0) is O(n) (everyone shuffles). A ring buffer keeps a head index and wraps around: O(1). collections.deque is the tool at work. Uses: BFS (lesson 10), job queues, rate limiters, the API school's lunch line.
Variants: a deque (both ends), a priority queue (lesson 09's heap).

🤔 Why

The bracket checker is six lines with a stack and nearly impossible without one; BFS is unthinkable without a queue. Knowing the O(n) trap in list.pop(0) saves a real outage.

🔧 How (in this repo)

Queue stores items in a fixed list with head and n; dequeue moves head forward modulo capacity; when full, _grow copies into a list twice the size. demo.py stackqueue runs the bracket checker on a good and a bad string.

🧪 Try it

python3 dsa/demo.py stackqueue
python3 - <<'EOF'
import time
from collections import deque
n = 200_000
lst = list(range(n)); t = time.perf_counter()
while lst: lst.pop(0)                                  # the trap
print(f"list.pop(0) × {n}: {(time.perf_counter() - t) * 1000:.0f} ms")
dq = deque(range(n)); t = time.perf_counter()
while dq: dq.popleft()
print(f"deque.popleft() × {n}: {(time.perf_counter() - t) * 1000:.0f} ms")
EOF

✅ Verify — what you should see

tray 3, tray 2 off the pile; Aishwarya, Katrina served from the line; True then False for the brackets. The list.pop(0) loop takes seconds; the deque takes milliseconds — O(n²) versus O(n).

🏁 What you just proved

Restricting a list to one end gives you two structures, one of which needs a ring buffer (or a deque) to keep its promise — and you measured the trap.

⚠️ Common mistakes

list.pop(0) for a queue.
Forgetting to check "is the stack empty?" before popping (the unbalanced ) case).
Using recursion where an explicit stack would avoid the depth limit (lesson 06).

🏭 Why this matters in production: message queues, undo stacks, request pipelines, the event loop — every one is a stack or a queue with a name. The ring buffer is how network cards and logging libraries avoid shuffling.

⏭️ Next

Lesson 05 — hash maps & sets: pigeonholes by name, the most useful structure in the language.

← Previouslinked lists Next →hash maps

This page is the lesson's README from the lesson-04-stacks-queues branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.