Contents

[Golang][Leetcode][Stack & Queue]刷題系列-225-Implement Stack using Queues


225. Implement Stack using Queues


Level : Easy

原題連結 : Click

題目 :

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();
 */

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!