Contents

# 225. Implement Stack using Queues

## 題目 :

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

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

### Example :

Note

Input [“MyStack”, “push”, “push”, “top”, “pop”, “empty”]

[[], [1], [2], [], [], []]

Output

[null, null, null, 2, 2, false]

Explanation

MyStack myStack = new MyStack();

myStack.push(1);

myStack.push(2);

myStack.top(); // return 2

myStack.pop(); // return 2

myStack.empty(); // return False

#### 解題思路 :

• 這題其實題目看似有些繁雜但是其實想法非常簡單
• 只要釐清Stacks是FILO(first in last out)，Queues是FIFO(fisrt in first out)的差別
• 再來需要考慮我們需要多少queue去實現一個stack，其實呢一個就夠了
• 我們push操作用append去做處理不斷的往後加，top就是使用提取最後一個元素出來也就是queue[len(queue)-1]，pop需要刪除stack內的元素，實現方法就是用golang的slice方法queue[:len(queue)-1]，就可以成功完成，easy!!

### 以下是我的解法

• 若要探討每一個function的時間複雜度的話，需要先了解所謂golang的 append 背後的原理，其實呢，append其實是根據其放入的slice他的base array的capacity來決定是否需要新allocate一個array，所以它的時間複雜度best case 會在O(1)，worst case 會在O(n)
• 所以push, pop, top也是best case O(1)，worst case O(n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Implement Stack using Queues.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 `````` `````` type MyStack struct { queue []int } /** Initialize your data structure here. */ func Constructor() MyStack { return MyStack{} } /** Push element x onto stack. */ func (this *MyStack) Push(x int) { this.queue = append(this.queue,x) } /** Removes the element on top of the stack and returns that element. */ func (this *MyStack) Pop() int { element := this.Top() this.queue = this.queue[:len(this.queue)-1] return element } /** Get the top element. */ func (this *MyStack) Top() int { return this.queue[len(this.queue)-1] } /** Returns whether the stack is empty. */ func (this *MyStack) Empty() bool { if len(this.queue) == 0 { return true } return false } /** * Your MyStack object will be instantiated and called as such: * obj := Constructor(); * obj.Push(x); * param_2 := obj.Pop(); * param_3 := obj.Top(); * param_4 := obj.Empty(); */ ``````