題目

https://leetcode.com/problems/implement-queue-using-stacks Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

Understand

使用兩個堆疊Stack模擬佇列Queue。兩者的差異在於

• 堆疊是後進先出
• 佇列是先進先出 Happy Case為 push(1) → push(2) → push(3) peek() → 回傳 1 pop() → 回傳 1 pop() → 回傳 2 empty() → false Edge Case 為

Match

題目要考堆疊的特性，以及如何轉換資料結構 佇列是先進先出，而堆疊是先進後出，所以使用兩個堆疊，一個堆疊A負責儲存資料，另一個堆疊B負責取出資料，將資料從A倒入B就剛好會讓先進入堆疊A的資料從堆疊B先出去

Stack A（push用）    Stack B（pop用）
  [1, 2, 3]    →倒入→    [3, 2, 1]
  top = 3                top = 1  ← 正好是 Queue 的 front！

Plan

設計兩個堆疊

• stack_in負責接收push()資料
• stack_out負責執行pop()與peek() 因此要實作佇列的
• push()：由stack_in接收
• pop/peek：從stack_out取出，如果stack_out為空就把stack_in倒進去
• empty：兩個stack都是空的才回傳True

Implement

class MyQueue

	def __init__():
		self.stack_in = []
		self.stack_out = []
		
	def push(self, x: int) -> None:
		self.stack_in.append(x)
		
	def migrate(self) -> None:
		if not self.stack_out:
			while self.stack_in:
				self.stack_out.append(slef.stack_in.pop())

    def pop(self) -> int:
		slef.migrate()
		self.stack_out.pop()		

    def peek(self) -> int:
	    slef.migrate()
	    self.stack_out[-1]

    def empty(self) -> bool:
		return not self.stack_out and not self.stack_in	

Review

Happy Case 跑過程式：

push(1): stack_in=[1], stack_out=[] 
push(2): stack_in=[1,2], stack_out=[] 
push(3): stack_in=[1,2,3], stack_out=[]

peek(): _migrate() → stack_out=[3,2,1], 
stack_in=[] return stack_out[-1] = 1 ✅

Evaluate