用隊(duì)列實(shí)現(xiàn)棧的兩種方法

兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

思路：兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧，使用了隊(duì)列交換的思想。

代碼如下：

type MyStack struct {
    queue1, queue2 []int
}

//構(gòu)造函數(shù)
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
}

先將元素入對(duì)到 queue2，此時(shí) queue1 為0，交換 queue2 和 queue1。此時(shí) queue2 為0，queue1 中有1個(gè)元素。

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

此時(shí)相當(dāng)于，插入 queue2 的兩個(gè)元素的位置發(fā)生了交換并保存在 queue1中。最后將 queue1 中的元素出隊(duì)，這樣就可以保證后插入的元素先出。

不斷執(zhí)行 push 操作就行。

一個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

思路：使用一個(gè)隊(duì)列時(shí)，將當(dāng)前插入元素前面的所有元素,先出隊(duì)再入隊(duì)即可。

代碼如下：

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
}

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