兩個隊列實現一個棧

思路：兩個隊列實現一個棧，使用了隊列交換的思想。

代碼如下：

type MyStack struct {
    queue1, queue2 []int
}

//構造函數
func Constructor() (s MyStack) {
    return
}

func (s *MyStack) Push(x int) {
    s.queue2 = append(s.queue2, x)
    for len(s.queue1) > 0 {
        s.queue2 = append(s.queue2, s.queue1[0])
        s.queue1 = s.queue1[1:]
    }
    s.queue1, s.queue2 = s.queue2, s.queue1
}

func (s *MyStack) Pop() int {
    v := s.queue1[0]
    s.queue1 = s.queue1[1:]
    return v
}

func (s *MyStack) Top() int {
    return s.queue1[0]
}

func (s *MyStack) Empty() bool {
    return len(s.queue1) == 0
}

先將元素入對到 queue2，此時 queue1 為0，交換 queue2 和 queue1。此時 queue2 為0，queue1 中有1個元素。

再執行push操作時，len(queue1) > 0，此時再把 queue1 中的元素插入queue2 的尾部，然后將 queue2 和 queue1 進行交換。

此時相當于，插入 queue2 的兩個元素的位置發生了交換并保存在 queue1中。最后將 queue1 中的元素出隊，這樣就可以保證后插入的元素先出。

不斷執行 push 操作就行。

一個隊列實現一個棧

思路：使用一個隊列時，將當前插入元素前面的所有元素,先出隊再入隊即可。

代碼如下：

type MyStack struct {
    queue []int
}

func Constructor() (s MyStack) {
    return
}

func (s *MyStack) Push(x int) {
    n := len(s.queue)
    s.queue = append(s.queue, x)
    for ; n > 0; n-- {
        s.queue = append(s.queue, s.queue[0])
        s.queue = s.queue[1:]
    }
}

func (s *MyStack) Pop() int {
    v := s.queue[0]
    s.queue = s.queue[1:]
    return v
}

func (s *MyStack) Top() int {
    return s.queue[0]
}

func (s *MyStack) Empty() bool {
    return len(s.queue) == 0
}

每次執行 push 操作，如果queue存在元素，則將新插入元素前的所有元素出隊，然后依次進隊。這樣新插入的元素就在隊首了。