栈和队列互相实现，一文弄懂它们的关系

前言

栈和队列是比较基础的数据结构。无论在工作中，还是在面试中，栈和队列都用的比较多。在计算机的世界，你会看到队列和栈，无处不在。

栈：一个先进后出的数据结构

队列：一个先进先出的数据结构

栈和队列这两种数据结构，同时也存在某种联系。用栈可以实现队列，用队列也可以实现栈。

海边风景不错，欣赏一下风景，下面开始步入正题。学完这篇，咱们再接着看风景。

两个栈实现一个队列

思路：让数据入stack1，然后栈stack1中的数据出栈并入到栈stack2，然后出stack2。

代码如下：

type CQueue struct {
    stack1, stack2 *list.List
}

//构造函数    
func Constructor() CQueue {
        return CQueue{
        stack1: list.New(),
        stack2: list.New(),
    }
}
    
//尾部插入
func (this *CQueue) AppendTail(value int)  {
    this.stack1.PushBack(value)
}

//头部删除,back函数返回其list最尾部的值
func (this *CQueue) DeleteHead() int {
    //如果第二个栈为空
    if this.stack2.Len() == 0 {
        for this.stack1.Len() > 0 {
            this.stack2.PushBack(this.stack1.Remove(this.stack1.Back()))
        }
    }
    if this.stack2.Len() != 0 {
        e := this.stack2.Back()
        this.stack2.Remove(e)
        return e.Value.(int)
    }
    return -1
}

先调用 AppendTail 函数将所有元素插入 stack1，在调用 DeleteHead 函数将 stack1 中的元素转移到 stack2 中，再将元素再出栈。

再调用 DeleteHead 时，先判断 statck2 是否为空，为空则将 stack1 元素移动到 stack2 中，然后将 stack2 中的栈顶元素保存，并弹栈。

两个队列实现一个栈

思路：两个队列实现一个栈，使用了队列交换的思想。

代码如下：

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存在元素，则将新插入元素前的所有元素出队，然后依次进队。这样新插入的元素就在队首了。

絮叨

栈和队列作为基础的数据，大家务必掌握其性质和功能，知道它们之间的某种依存关系，才能灵活运用。

上面的算法虽然很简单，但是思路很巧妙，还有其他解法，大家也可仔细研究，必有收获。有本数据结构的书<<大话数据结构>>推荐给大家。

点击关注公众号，领取学习资料