Skip to content

Stack and Queue — Core Operations

আমরা stack-কে ধরি এক প্রান্তে ব্যবহার করা একটা Python list হিসেবে, আর queue/deque-কে collections.deque হিসেবে। প্রতিটা operation-এ: এটা কী করে, খরচটা যা সেটা কেন, একটা before/after ছবি, code, আর pitfall।

1. Stack push — stack.append(x)

কী: x-কে stack-এর উপরে বসাও।

কেন O(1) amortized: এটা হুবহু শেষে একটা dynamic-array append — spare room-এ লেখো; শুধু কালেভদ্রে doubling copy হয় (দেখো ../02-arrays-and-strings/operations.md)।

before:  | 9 |          after push(2):  | 2 | <top
         | 4 | <top                     | 9 |
         +---+                          | 4 |
                                        +---+

stack = [4, 9]
stack.append(2)      # [4, 9, 2] — rightmost element is the top

Pitfalls: "top"-এর জন্য একটাই convention বেছে নাও (এখানে: list-এর ডান প্রান্ত) আর কখনো মেশাবে না। insert(0, x) দিয়ে push করা logically কাজ করে কিন্তু O(n) — একটা নীরব performance bug।

2. Stack pop — stack.pop()

কী: top element-টা সরাও আর return করো।

কেন O(1): array-র শেষ element সরালে কিছুই shift হয় না।

before:  | 2 | <top     after pop():    | 9 | <top      returns 2
         | 9 |                          | 4 |
         | 4 |                          +---+
         +---+

top = stack.pop()    # 2; stack is now [4, 9]

Pitfalls: খালি list-এ pop() করলে IndexError ওঠে। if stack: দিয়ে guard করো, অথবা algorithm এমনভাবে design করো যাতে ওই point-এ emptiness অসম্ভব হয় (আর comment-এ লেখো কেন)।

3. Stack peek — stack[-1]

কী: না সরিয়ে top-টা দেখো।

কেন O(1): জানা position-এ index access।

if stack:
    top = stack[-1]      # read, don't remove

Pitfalls: খালি stack-এ peek করলেও IndexError ওঠে। Monotonic-stack loop করে while stack and stack[-1] < x: — ওই stack and guard-টা load-bearing।

4. Enqueue — deque-তে q.append(x)

কী: লাইনের পেছনে যোগ দাও।

কেন O(1): deque পেছনের block-এর খালি slot-এ লেখে; কোনো shifting নেই, পুরো structure-এর কোনো reallocation নেই।

before: front -> [ A  B ] <- back       after append(C):
        front -> [ A  B  C ] <- back

from collections import deque
q = deque(['A', 'B'])
q.append('C')

Pitfalls: পেছনে কোনোটাই না — বিপদটা সামনে (পরের operation)।

5. Dequeue — q.popleft()

কী: লাইনের সামনের জনকে serve করো আর সরাও।

কেন O(1): deque তার front marker-টা front block-এর ভেতরে এগিয়ে নেয়। তুলনা করো: list.pop(0)-কে বাকি প্রতিটা element বাঁয়ে shift করতে হয় — O(n)।

before: front -> [ A  B  C ] <- back    after popleft():
        returns A;  front -> [ B  C ] <- back

first = q.popleft()    # 'A'

Pitfalls: BFS loop-এ list.pop(0) ব্যবহার করাই হলো THE classic Python ভুল — program-টা correct কিন্তু চুপচাপ O(n^2), বড় input-এ time out করে। খালি deque-তে popleft করলে IndexError ওঠে; BFS loop সেটা এড়ায় while q: দিয়ে।

6. Peek front / back — q[0], q[-1]

কী: না সরিয়ে যেকোনো প্রান্ত পরীক্ষা করো।

কেন O(1): deque দুই প্রান্তের block-এরই direct reference ধরে রাখে।

front = q[0]
back = q[-1]

Pitfalls: deque-র মাঝখানে index করা (q[k]) O(n) — deque শুধু প্রান্তের জন্য optimized। মাঝখানে fast access দরকার হলে আসলে তোমার দরকার ছিল একটা list।

7. Deque back-pop — q.pop()

কী: পেছন থেকে সরাও — যে operation একটা queue-কে deque বানায়।

কেন O(1): popleft-এর symmetric।

last = q.pop()

Pitfalls: monotonic-deque code-এ তুমি pop() (useless পেছনের element eject করতে) আর popleft() (expired সামনের element eject করতে) — দুটোই ডাকবে। এগুলো গুলিয়ে ফেললে এমন ভুল answer আসে যেগুলো ছোট test-এ plausible দেখায় — সন্দেহ হলেই visual-explanation.md section 7-এর centerpiece table-টা আবার trace করো।

8. Size আর emptiness — len(q), not q

কী: কয়টা item আছে; খালি কিনা।

কেন O(1): দুটো structure-ই একটা size counter maintain করে।

while q:               # idiomatic "while not empty"
    item = q.popleft()

Pitfalls: while len(q) > 0: কাজ করে কিন্তু while q:-ই idiom। Loop-এর শুরুতে n = len(q) cache করা level-by-level BFS-এর জন্য একদম ঠিক (প্রতি outer iteration-এ একটা full layer process করো) — কিন্তু পুরো queue শেষ করতে চাইলে ভুল।

9. Bounded deque — deque(maxlen=k)

কী: এমন একটা deque যেটা বড়জোর k-টা item ধরে; ভরা অবস্থায় add করলে উল্টো প্রান্ত থেকে চুপচাপ ফেলে দেয়।

কেন matter করে: "last k events" buffer-এর জন্য perfect (recent log, moving average)।

recent = deque(maxlen=3)
for x in [1, 2, 3, 4]:
    recent.append(x)
# recent is deque([2, 3, 4]) — the 1 fell off the front automatically

Pitfalls: চুপচাপ ফেলে দেওয়াটা এখানে feature, আর যেখানে তুমি আশা করোনি সেখানে bug। Sliding-window-maximum-এর জন্য maxlen ব্যবহার কোরো না — monotonic deque-কে নিজের eviction নিজে control করতেই হবে (front eviction নির্ভর করে index-এর উপর, count-এর উপর না)।

10. MinStack — twin stack দিয়ে O(1) minimum

কী: এমন একটা stack যেটা "current minimum কত?"-এর উত্তরও O(1)-এ দেয়।

কেন O(1): মূল stack-এর পাশে একটা দ্বিতীয় stack রাখো, যার top সবসময় মূল stack-এ এই মুহূর্তে থাকা সবকিছুর minimum। প্রতিটা push-এর সাথে twin-এ push করো min(x, current_min); দুটো একসাথে pop করো। Minimum-এর history আপনা থেকেই সংরক্ষিত থাকে।

push 5, 2, 7:    main: [5, 2, 7]       mins: [5, 2, 2]
                                              ^ top of mins = current min = 2
pop (7):         main: [5, 2]          mins: [5, 2]    min still 2
pop (2):         main: [5]             mins: [5]       min back to 5 — for free

# full class in implementation.py
self.stack.append(x)
self.mins.append(min(x, self.mins[-1] if self.mins else x))

Pitfalls: শুধু একটা current_min variable রাখলে minimum-টা pop হওয়া মাত্র fail করে — history ছাড়া আগের minimum-টা ফিরে পাওয়া যায় না। Twin stack-ই হলো সেই history।

Big-O summary table

Operation Stack (list) Queue (deque) Deque Wrong tool (list as queue)
push / append back O(1) am. O(1) O(1) O(1)
pop top / back O(1) — O(1) O(1)
dequeue / pop front — O(1) O(1) O(n) ← the trap
peek (either end) O(1) O(1) O(1) O(1)
index middle O(1) O(n) O(n) O(1)
search by value O(n) O(n) O(n) O(n)
size / empty check O(1) O(1) O(1) O(1)
MinStack get_min O(1) — — —

Table-টা column ধরে পড়ো: প্রতিটা structure ঠিক সেখানেই সস্তা যেখানে তার discipline থাকে, আর সেখানেই দামি যেখানে সে access নিষেধ করে। Structure বেছে নেওয়া = কোন column-এর cost তুমি দেবে সেটা বেছে নেওয়া।

এরপর: named technique গুলো — full Sliding Window Maximum walkthrough সহ — patterns.md-তে।