005 — Implement Stack using Queues¶

Source¶

Original source: Classic design exercise
Platform: LeetCode — https://leetcode.com/problems/implement-stack-using-queues/
Topic: stack, queue, design
Difficulty: Easy
Pattern: design composition (queue-based)
Basic idea inherited from: problem 4 (queue via stacks)-এর mirror — এবার উল্টো দিক থেকে

1. Problem in simple words¶

তোমাকে একটা LIFO stack বানাতে হবে, কিন্তু শুধু queue-র operation (পেছনে push, সামনে থেকে pop/peek, size, empty) ব্যবহার করে। চারটা method support করতে হবে:

push(x) — উপরে একটা element রাখো।
pop() — উপরের (সবচেয়ে recent) element সরিয়ে return করো।
top() — উপরের element দেখো (না সরিয়ে)।
empty() — stack খালি কিনা বলো।

2. Which basic idea does this inherit from?¶

এটা problem 4 (Queue using Stacks)-এর mirror। সেখানে দুটো LIFO মিলে FIFO বানানো হয়েছিল; এখানে FIFO container দিয়ে LIFO behaviour বানাতে হবে। key idea একই — restricted structure-এর order-টাকে চালাকি করে উল্টে দেওয়া।

3. What is the hidden math or logic?¶

লুকানো logic হলো rotation দিয়ে order উল্টানো। queue স্বভাবতই সামনে-থেকে-পুরোনো দেয়। কিন্তু নতুন element ঢোকানোর সাথে সাথে যদি তার আগের সব element-কে একে একে পেছন থেকে তুলে আবার পেছনে রেখে দিই (rotate), তাহলে নতুন element সামনে চলে আসে। ফলে queue-র front সবসময় সবচেয়ে recent element ধরে রাখে — মানে stack-এর top।

invariant: প্রতিটা push-এর পরে, queue-র front = stack-এর top।

4. Which data structure is needed?¶

একটা queue — Python-এ collections.deque (front থেকে popleft, back-এ append, দুটোই O(1))। একটা queue-ই যথেষ্ট, যদি প্রতি push-এ rotate করি।

5. Why this data structure fits¶

queue শুধু FIFO দেয়, LIFO না — কিন্তু "push costly" trick দিয়ে আমরা front-কে সবসময় top বানিয়ে রাখি। deque ব্যবহার করি কারণ popleft আর append দুটোই O(1); সাধারণ list-এ pop(0) করলে প্রতিবার O(n) shift হতো (../concept.md-এ এই ফাঁদটা দেখানো আছে)।

6. Real-life analogy¶

একটা ঘূর্ণায়মান sushi belt ভাবো যা একমুখী ঘোরে। নতুন প্লেট পেছনে রাখার পর, যদি তুমি বাকি প্লেটগুলোকে একে একে তুলে আবার পেছনে রাখো (একপাক ঘোরাও), নতুন প্লেটটা ঠিক সামনে চলে আসে — গ্রাহক প্রথমেই সেটাই পায়। সবচেয়ে নতুন প্লেট সবার আগে — LIFO।

7. Visual explanation¶

push(1), push(2), push(3), তারপর pop (rotate-on-push পদ্ধতি):

op        কাজ                                   queue (front বাঁয়ে)
push(1)   append 1; rotate 0 বার               [1]
push(2)   append 2 -> [1,2]; rotate 1 বার       [2, 1]
          (front 1 তুলে পেছনে রাখো)
push(3)   append 3 -> [2,1,3]; rotate 2 বার     [3, 2, 1]
          (2 পেছনে, তারপর 1 পেছনে)
top       front = 3                              [3, 2, 1]
pop       popleft -> 3                           [2, 1]   (LIFO!)

প্রতিটা push-এর পর front-টাই হলো সদ্য-যোগ-করা element।

8. Example input and output¶

ops : push(1), push(2), top(), pop(), empty()
out :    -        -      2      2     False

তারপর: push(3), pop(), pop(), empty()
out :    -       3      1      True

লক্ষ: pop সবসময় সবচেয়ে recent push-টা ফেরত দেয় (2, তারপর 3, তারপর 1)।

9. Brute force thinking¶

বিকল্প: দুটো queue ব্যবহার করি, আর pop-কে costly বানাই। pop-এর সময় q1-এর শেষ element ছাড়া বাকি সব q2-তে সরাই, শেষ element-টা return করি, তারপর q2-কে q1 বানাই।

push: শুধু q1.append(x)  -> সস্তা
pop : q1-এর শেষটা ছাড়া সব q2-তে সরাও; শেষটা return; swap q1,q2

10. Why brute force is slow¶

ওই two-queue পদ্ধতিতে pop প্রতিবার O(n) (প্রায় সব element সরাতে হয়)। আমাদের one-queue rotate-on-push পদ্ধতিতে push O(n) কিন্তু pop/top O(1)। দুটোতেই কোনো-না-কোনো operation O(n) — queue দিয়ে stack বানানোর এটা অন্তর্নিহিত দাম (problem 4-এর দুই-stack-এ যেটা amortized O(1) ছিল)। আমরা single-queue, push-costly সংস্করণটা বেছে নিচ্ছি — সহজ আর compact।

11. Key observation¶

মূল observation: নতুন element ঢোকানোর সাথে সাথে যদি queue-টাকে এমনভাবে ঘোরাই যে সে front-এ চলে আসে, তাহলে queue-র স্বাভাবিক front-from-old আচরণই LIFO হয়ে যায়। rotate-এর সংখ্যা = (নতুনটা ছাড়া) আগের element সংখ্যা।

12. Optimized intuition¶

একটা deque রাখো। push(x): আগে append(x), তারপর len-1 বার appendleft(popleft()) করে front-টা rotate করে নতুন element-কে সামনে আনো। pop(): popleft() — front, যেটা এখন top। top(): q[0]। empty(): queue খালি কিনা।

13. Thinking tweak¶

মোচড়: "queue তো LIFO দিতে পারে না" — এই বাধাটা সরাও order maintain করার দায়িত্ব push-এর কাঁধে দিয়ে। প্রতিটা push নিজেই queue-টাকে এমন অবস্থায় রেখে যায় যেখানে front = top; ফলে pop-কে আর কিছু ভাবতেই হয় না।

14. Step-by-step dry run¶

operations: push(1), push(2), top(), pop(), push(3), pop(), pop():

push(1) → append 1 → [1]; rotate 0 বার → [1]
push(2) → append 2 → [1, 2]; rotate 1 বার (front 1 পেছনে) → [2, 1]
top() → q[0] = 2
pop() → popleft() = 2 → [1]
push(3) → append 3 → [1, 3]; rotate 1 বার (front 1 পেছনে) → [3, 1]
pop() → popleft() = 3 → [1]
pop() → popleft() = 1 → []

বেরোনোর order: 2, 3, 1 — প্রতিবার সবচেয়ে recent push, ঠিক LIFO।

15. Python solution¶

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q) - 1):    # নতুনটাকে সামনে আনতে rotate
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()             # front = top

    def top(self):
        return self.q[0]

    def empty(self):
        return not self.q

# ---- tests ----
s = MyStack()
s.push(1)
s.push(2)
assert s.top() == 2          # সবচেয়ে recent
assert s.pop() == 2          # LIFO
assert s.empty() is False
s.push(3)
assert s.pop() == 3
assert s.pop() == 1
assert s.empty() is True
print("সব test pass!")

16. Line-by-line code explanation¶

self.q = deque() — একটা double-ended queue, যাতে দুই প্রান্তই O(1)।
push(x): append(x) দিয়ে পেছনে রাখো; তারপর len-1 বার append(popleft()) — front-এর element গুলো একে একে পেছনে গিয়ে নতুন x-কে front-এ আনে।
pop(): popleft() front সরায়, যেটা rotate-এর কল্যাণে সবচেয়ে recent।
top(): q[0] front-টা দেখায় (না সরিয়ে)।
empty(): queue খালি হলে True।

17. Output walkthrough¶

উপরের test: push(1), push(2)-এর পর queue [2, 1], তাই top() = 2, pop() = 2। push(3)-এর পর [3, 1], pop() = 3, তারপর pop() = 1। empty() শেষে True। সব assert pass — print: সব test pass!।

18. Time complexity¶

push: O(n) — প্রতি push-এ পুরো queue rotate হয়।
pop / top / empty: O(1)।

19. Space complexity¶

O(n) — একটাই queue, তাতে n-টা element জমে।

20. Common mistakes¶

collections.deque-এর বদলে list + pop(0) ব্যবহার — তাতে প্রতিটা popleft-সমতুল্য O(n) shift, পুরোটা ধীর।
rotate-এর সংখ্যা ভুল — len(self.q) - 1 বার ঘোরাতে হয় (নতুনটা ছাড়া বাকি সব); len(self.q) বার ঘোরালে আবার আগের অবস্থায় ফিরে যায়।
push-এর আগে rotate করা — আগে append করতে হবে, তারপর rotate, নাহলে নতুন element সামনে আসবে না।

21. Which basic problem this inherits from¶

ভিত্তি: problem 4 (Queue using Stacks)-এর design-composition idea, এবার mirror করা; chapter-এর ../patterns.md-এর Pattern 3 (Design Compositions)। ../concept.md-এর "queue-কে deque হতেই হবে" snippet এখানে কেন deque লাগছে তা ব্যাখ্যা করে।

22. Similar harder problems¶

Implement Queue using Stacks (এর mirror) — https://leetcode.com/problems/implement-queue-using-stacks/ (এই tracker-এর #4)
Min Stack — https://leetcode.com/problems/min-stack/ (#6)
Design Circular Deque — https://leetcode.com/problems/design-circular-deque/

23. Pattern learned¶

Queue-to-stack via rotation: push-এর সময় নতুন element-কে front-এ rotate করে আনো, তাহলে queue-র front-from-old আচরণই LIFO হয়ে যায়।

24. Final summary¶

ভবিষ্যতের আমাকে: "FIFO দিয়ে LIFO চাইলে — push-এ rotate করে নতুনটাকে সামনে আনো।" মনে রাখবে কোন operation-কে costly বানাবে সেটা তোমার পছন্দ (push-heavy বা pop-heavy)। আর queue মানেই Python-এ deque, কখনো list.pop(0) নয়।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।