225. Implement Stack using Queues

We can’t use the similar solution we did for Design a Queue with Stack. It is because unlike Stack, moving elements from one Queue to another one won’t change the sequence of elements. We have to pop out all previous elements added into the queue when adding a new element, in this way we can simulate a Stack.

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
type Queue []int

func (q *Queue)Empty() bool {
    return len(*q) == 0
}

func (q *Queue)Push(x int) {
    *q = append(*q, x)
}

func (q *Queue)Pop() int {
    var ret int
    if !q.Empty() {
        ret = (*q)[0]
        *q = (*q)[1:]
    }
    return ret
}

func (q *Queue)Top() int {
    var ret int
    if !q.Empty() {
        ret = (*q)[0]
    }
    return ret
}

type MyStack struct {
    m *Queue
}

func Constructor() MyStack  {
    return MyStack{
        &Queue{},
    }
}

func (s *MyStack) Empty() bool {
    return s.m.Empty()
}

func (s *MyStack) Top() int {
    return s.m.Top()
}

func (s *MyStack) Pop() int {
    return s.m.Pop()
}

func (s *MyStack) Push(x int) {
    n := len(*((*s).m))
    s.m.Push(x)
    for n > 0 {
        s.m.Push(s.m.Pop())
        n--
    }
}