Contents

[Golang][Leetcode][Stack & Queue]刷題系列-232-Implement Queue using Stacks


232. Implement Queue using Stacks


Level : Easy

原題連結 : Click

題目 :

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.

Example :

Note

Input

[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]

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

Output

[null, null, null, 1, 1, false]

Explanation:

MyQueue myQueue = new MyQueue();

myQueue.push(1); // queue is: [1]

myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

myQueue.peek(); // return 1

myQueue.pop(); // return 1, queue is [2]

myQueue.empty(); // return false


解題思路 :

  • 這題需要用兩個stack來模擬出queue FIFO(First in first out)的情況,stack本身就是一種先進後出,單一出口的資料結構,若要模擬出queue可以有一個stack-in跟stack-out

  • 一個負責接收element(push),一個負責釋放element(pop/peek)

    1. push的實作非常簡單,就是直接將element append進stack-in array
    2. peek/pop的實作我用了一些邏輯,需要先將stack-in中的element搬到stack-out,這邊需要注意取出的方式是stack-in[len(stack-in)-1],然後append到stack-out這樣的取出方式可以達到將stack-in排序方式翻轉的效果,接下來再從stack-out用同樣方式取出時就符合FIFO的特性

以下是我的解法

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

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


 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
50
51
52
53
54
55
56
57
58
59

type MyQueue struct {
    stack_in []int
    stack_out []int
}


/** Initialize your data structure here. */
func Constructor() MyQueue {
    return MyQueue {
        stack_in : make([]int, 0),
        stack_out : make([]int, 0),
    }
}


/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {
    this.stack_in = append(this.stack_in, x)
    
}


/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
    val := this.Peek()
    this.stack_out = this.stack_out[:len(this.stack_out)-1]
    
    return val
}


/** Get the front element. */
func (this *MyQueue) Peek() int {
    if len(this.stack_out) == 0 {
        for len(this.stack_in) > 0 {
            val := this.stack_in[len(this.stack_in)-1]
            this.stack_in = this.stack_in[:len(this.stack_in)-1]
            this.stack_out = append(this.stack_out,val)
        }
    }
    return this.stack_out[len(this.stack_out)-1]
}


/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
    return len(this.stack_in) == 0 && len(this.stack_out) == 0
}


/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

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