004 — Implement Queue using Stacks¶

Source¶

Original source: Classic design exercise
Platform: LeetCode — https://leetcode.com/problems/implement-queue-using-stacks/
Topic: stack, queue, design
Difficulty: Easy
Pattern: design composition (two stacks)
Basic idea inherited from: dynamic array-র amortized analysis (../../02-arrays-and-strings/) — কালেভদ্রে একটা দামি কাজ, যা অনেক সস্তা operation-এ ভাগ হয়ে যায়

1. Problem in simple words¶

তোমাকে একটা FIFO queue বানাতে হবে, কিন্তু শর্ত হলো — শুধু stack-এর operation (push, pop, peek, empty, size) ব্যবহার করতে পারবে, queue-র কোনো built-in operation না। চারটা method support করতে হবে:

push(x) — পেছনে একটা element ঢোকাও।
pop() — সামনের element সরিয়ে return করো।
peek() — সামনের element দেখো (না সরিয়ে)।
empty() — queue খালি কিনা বলো।

2. Which basic idea does this inherit from?¶

এটা dynamic array-র amortized argument (../../02-arrays-and-strings/)-এর বংশধর: মাঝে মাঝে একটা দামি কাজ (পুরো stack ঢেলে দেওয়া) করি, কিন্তু সেই খরচটা পরবর্তী অনেকগুলো সস্তা operation-এর ঘাড়ে ভাগ করে দিই — তাই গড়ে (amortized) প্রতিটা operation O(1)।

3. What is the hidden math or logic?¶

লুকানো logic হলো double reversal: একটা stack LIFO order দেয়; সেটাকে আরেকটা stack-এ ঢাললে order উল্টে যায় → আবার LIFO-র উল্টো = FIFO। তাই in stack-এ জমা করা element গুলো out stack-এ ঢাললে সঠিক queue order-এ বেরোয়।

amortized হিসাব: প্রতিটা element তার জীবনে বড়জোর চারবার ছোঁয়া হয় — in-এ push, in থেকে pop, out-এ push, out থেকে pop। সব O(1), তাই প্রতি operation amortized O(1)।

4. Which data structure is needed?¶

দুটো stack — একটা in_stack (নতুন element ঢোকার জন্য) আর একটা out_stack (পুরোনো element বেরোনোর জন্য)।

5. Why this data structure fits¶

একটা stack একাই FIFO দিতে পারে না, কারণ সে শুধু শেষ-ঢোকা element দেয়। কিন্তু দুটো stack মিলে capability-টা বানিয়ে ফেলে: in-এ push করলে নতুনরা উপরে জমে; out খালি হলে in-এর পুরোটা out-এ ঢেলে দিলে order উল্টে যায়, তাই out-এর top এখন সবচেয়ে পুরোনো element — মানে queue-র front। এই trick-এর জন্যই দুটো stack নিখুঁত।

6. Real-life analogy¶

দুটো খাড়া নলের কথা ভাবো যাতে marble ফেলা হয়। প্রথম নলে (in) তুমি একে একে marble ফেলো — শেষেরটা উপরে। এখন প্রথম নলটা উপুড় করে দ্বিতীয় নলে (out) সব marble ঢেলে দিলে, প্রথমে ফেলা marble-টা এবার দ্বিতীয় নলের উপরে চলে আসে। দ্বিতীয় নল থেকে তুললে marble গুলো ঠিক যে order-এ ফেলেছিলে সেই order-এই বেরোয় — FIFO।

7. Visual explanation¶

operation push 1, push 2, peek, pop, push 3, pop:

op       in_stack     out_stack    note
push 1   [1]          []
push 2   [1, 2]       []
peek     []           [2, 1]       out খালি -> in ঢালো; front = out top = 1
pop      []           [2]          out top pop -> 1   (FIFO!)
push 3   [3]          [2]
pop      [3]          []           out খালি না -> top pop -> 2   (FIFO)

লক্ষ করো: out খালি না থাকলে আমরা আবার ঢালি না — তাই নতুন push 3 পুরোনো 2-কে টপকে যায় না।

8. Example input and output¶

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

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

Edge case (interleaved push/pop): উপরে দেখানো — push 3 আগের element-দের পেছনে যায়, সামনে নয়।

9. Brute force thinking¶

সহজ (কিন্তু ব্যয়বহুল) চিন্তা: প্রতিটা push-এ নতুন element-কে queue-র সামনে আনি। মানে — সব পুরোনো element একটা helper stack-এ সরাও, নতুনটা রাখো, তারপর পুরোনো গুলো ফেরত আনো। তখন একটা stack-এর top-ই সবসময় queue-র front।

push costly: প্রতিবার পুরো stack উল্টে, নতুনটা নিচে বসিয়ে, আবার উল্টাও।
pop/peek: সরাসরি top.

10. Why brute force is slow¶

ওই "push-costly" পদ্ধতিতে প্রতিটা push O(n) (পুরো structure দুবার উল্টানো)। n-টা push করলে → O(n^2)। আমাদের lazy (দুই-stack) পদ্ধতি out খালি হলে তবেই ঢালে, আর প্রতিটা element সারা জীবনে একবারই ঢালা হয় — তাই amortized O(1)।

11. Key observation¶

মূল observation: ঢালার কাজটা পিছিয়ে দাও (lazy)। out stack-এ যতক্ষণ element আছে, ততক্ষণ সেগুলোই সঠিক front order-এ আছে — নতুন আসা element নিয়ে এখন মাথা ঘামানোর দরকার নেই। out খালি হলে তবেই in-এর পুরোটা একবারে ঢালো।

12. Optimized intuition¶

দুটো stack রাখো। push শুধু in_stack-এ append করে — সস্তা। peek/pop-এর সময় দেখো out_stack খালি কিনা; খালি হলে in_stack-এর সবকিছু out_stack-এ ঢেলে দাও (এক-একটা pop করে অন্যটায় push — order উল্টে যায়)। তারপর out_stack-এর top-ই হলো queue-র front।

13. Thinking tweak¶

মোচড়: "queue-র front সবসময় তৈরি রাখতে হবে" ভাবার বদলে ভাবো "front যখন দরকার হবে, তখনই তৈরি করব, এবং একবার তৈরি হলে সেটা যতক্ষণ পারি ব্যবহার করব।" এই laziness-ই O(n^2)-কে amortized O(1)-এ নামায়।

14. Step-by-step dry run¶

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

push(1) → in=[1], out=[]
push(2) → in=[1, 2], out=[]
peek() → out খালি, ঢালো: out=[2, 1]; front = out[-1] = 1
pop() → out খালি না; out.pop() = 1, out=[2]
push(3) → in=[3], out=[2]
pop() → out খালি না; out.pop() = 2, out=[]
pop() → out খালি, ঢালো: out=[3]; out.pop() = 3

বেরোনোর order: 1, 2, 3 — ঠিক FIFO।

15. Python solution¶

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x):
        self.in_stack.append(x)             # সবসময় in-এ জমাও

    def _transfer(self):
        if not self.out_stack:              # out খালি হলেই ঢালো (lazy)
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def peek(self):
        self._transfer()
        return self.out_stack[-1]           # out-এর top = front

    def pop(self):
        self._transfer()
        return self.out_stack.pop()         # front সরিয়ে return

    def empty(self):
        return not self.in_stack and not self.out_stack

# ---- tests ----
q = MyQueue()
q.push(1)
q.push(2)
assert q.peek() == 1          # front
assert q.pop() == 1           # FIFO
assert q.empty() is False
q.push(3)
assert q.pop() == 2           # পুরোনোটা আগে
assert q.pop() == 3
assert q.empty() is True
print("সব test pass!")

16. Line-by-line code explanation¶

self.in_stack, self.out_stack — দুটো খালি stack; নতুন in-এ, বেরোনো out থেকে।
push(x) — শুধু in_stack-এ append; O(1)।
_transfer() — out_stack খালি হলে in_stack-এর সব element pop-করে-append করে ঢেলে দেয়, order উল্টে যায়। খালি না হলে কিছুই করে না (lazy)।
peek() — ঢালার পর out_stack[-1], মানে সবচেয়ে পুরোনো element।
pop() — ঢালার পর out_stack.pop(), front সরিয়ে দেয়।
empty() — দুটো stack-ই খালি হলে queue খালি।

17. Output walkthrough¶

উপরের test: push(1), push(2)-এর পর peek() out-কে [2, 1] বানায়, front 1 দেয়। pop() 1 দেয়। push(3)-এর পর out=[2] থাকায় পরের pop() 2 দেয়, তারপর pop() আবার ঢেলে 3 দেয়। empty() শেষে True। সব assert pass — print: সব test pass!।

18. Time complexity¶

প্রতি operation amortized O(1) — প্রতিটা element সারা জীবনে বড়জোর চারবার (in-push, in-pop, out-push, out-pop) ছোঁয়া হয়। একক pop/peek worst case O(n) (যেদিন ঢালা হয়), কিন্তু গড়ে O(1)।

19. Space complexity¶

O(n) — n-টা element দুটো stack-এ মিলে জমা থাকে।

20. Common mistakes¶

প্রতিটা peek/pop-এ ঢালা — out_stack খালি না হলেও ঢেলে দিলে order ভেঙে যায় (নতুন element সামনে চলে আসে) এবং complexity O(n) হয়ে যায়। শুধু খালি হলেই ঢালো।
empty()-এ শুধু একটা stack check করা — দুটোই খালি কিনা দেখতে হবে।
ঢালার সময় উল্টো দিকে copy করা (একই order-এ) — তখন আর reversal হয় না, FIFO ভাঙে।

21. Which basic problem this inherits from¶

ভিত্তি: stack-এর LIFO discipline (problem 1) + amortized analysis (../../02-arrays-and-strings/)। chapter-এর ../patterns.md-এর Pattern 3 (Design Compositions) আর ../concept.md-এর "queue: array কেন fail করে" আলোচনা এখানে সরাসরি কাজে লাগছে।

22. Similar harder problems¶

Implement Stack using Queues (এর mirror) — https://leetcode.com/problems/implement-stack-using-queues/ (এই tracker-এর #5)
Min Stack (twin-structure design) — https://leetcode.com/problems/min-stack/ (#6)
Design Circular Queue — https://leetcode.com/problems/design-circular-queue/

23. Pattern learned¶

Two-stack composition for FIFO: এক stack-এ জমাও, খালি হলে অন্যটায় ঢেলে order উল্টাও — দুটো LIFO মিলে একটা amortized-O(1) FIFO।

24. Final summary¶

ভবিষ্যতের আমাকে: "দুই stack = এক FIFO; দ্বিতীয়টা খালি হলে তবেই ঢালো।" laziness-ই amortized O(1)-এর চাবি। "X structure দিয়ে Y structure বানাও" দেখলেই জিজ্ঞেস করবে — কোন history twin-structure-এ রাখলে অসম্ভব operation-টা সম্ভব হয়।

25. JavaScript solution (with test cases)¶

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class MyQueue {
  constructor() {
    this.inStack = [];               // নতুন element এখানে জমে
    this.outStack = [];              // পুরোনো element এখান থেকে বেরোয়
  }
  push(x) { this.inStack.push(x); }  // সবসময় in-এ — O(1)
  _transfer() {
    if (this.outStack.length === 0) {          // out খালি হলেই ঢালো (lazy)
      while (this.inStack.length) this.outStack.push(this.inStack.pop());
    }
  }
  peek() { this._transfer(); return this.outStack[this.outStack.length - 1]; }
  pop()  { this._transfer(); return this.outStack.pop(); }
  empty() { return this.inStack.length === 0 && this.outStack.length === 0; }
}

// ---- test cases ----
const q = new MyQueue();
q.push(1);
q.push(2);
assert(q.peek() === 1, "front 1");        // সবচেয়ে পুরোনো
assert(q.pop() === 1, "FIFO 1");
assert(q.empty() === false, "not empty");
q.push(3);
assert(q.pop() === 2, "পুরোনোটা আগে");    // push 3 সামনে আসে না
assert(q.pop() === 3, "then 3");
assert(q.empty() === true, "empty শেষে");
console.log("সব JS test pass!");

JS টীকা: JS-এ array নিজেই একটা নিখুঁত stack — push/pop দুটোই array-র শেষ প্রান্তে কাজ করে, amortized O(1)। outStack খালি কিনা বলতে .length === 0 ব্যবহার করো; !this.outStack ভুল হবে কারণ খালি array-ও truthy। দুটো array দিয়েই double-reversal করে FIFO পাওয়া যায়, আলাদা কোনো linked-list দরকার নেই।

26. TypeScript solution (with test cases)¶

class MyQueue {
  private inStack: number[] = [];
  private outStack: number[] = [];

  push(x: number): void { this.inStack.push(x); }

  private transfer(): void {
    if (this.outStack.length === 0) {
      while (this.inStack.length) this.outStack.push(this.inStack.pop()!);
    }
  }
  peek(): number { this.transfer(); return this.outStack[this.outStack.length - 1]; }
  pop(): number  { this.transfer(); return this.outStack.pop()!; }
  empty(): boolean { return this.inStack.length === 0 && this.outStack.length === 0; }
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }

const q = new MyQueue();
q.push(1); q.push(2);
expect(q.peek(), 1, "front");
expect(q.pop(), 1, "FIFO");
q.push(3);
expect(q.pop(), 2, "old first");
expect(q.pop(), 3, "then 3");
expect(q.empty(), true, "empty");
console.log("সব TS test pass!");

TS টীকা: inStack/outStack-কে number[] টাইপ দিলে ভুল টাইপ push করা compile-এ ধরা পড়ে। pop()-এর return type number | undefined, কিন্তু আমরা আগে length check করেছি বলে ! (non-null assertion) দিয়ে TypeScript-কে নিশ্চিত করি। private modifier-এ transfer বাইরে থেকে call করা আটকে যায় — internal helper গোপন থাকে।

27. কোথায় কাজে লাগে (real-world use)¶

Message/task queue on a constrained API: কখনো এমন SDK পাও যেখানে শুধু stack-জাতীয় push/pop আছে কিন্তু FIFO দরকার — তখন এই two-stack trick দিয়ে queue বানানো হয়।
Undo/redo-র উল্টো: দুই stack দিয়ে order উল্টানোর ধারণা editor-এর history management ও batch-processing pipeline-এ কাজে লাগে।
Streaming/lazy processing: "যখন দরকার তখনই ব্যয়বহুল কাজ করো" (lazy transfer) — এই amortized চিন্তা database buffer flush, log batching-এ সরাসরি প্রযোজ্য।
Interview design round: "X structure দিয়ে Y structure বানাও" — composition design-এর সবচেয়ে common warm-up প্রশ্ন, যা bigger system design-এর ভিত্তি।
Functional/immutable queue: Okasaki-র functional data structure-এ অপরিবর্তনীয় (immutable) queue ঠিক এই দুই-list front/back কৌশলেই বানানো হয়।

এক কথায়, যখন available primitive (stack) আর প্রয়োজনীয় behavior (FIFO) আলাদা, তখন amortized দুই-stack composition-ই সবচেয়ে পরিষ্কার সেতু।

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