栈是一种具有先进后出的线性数据结构，常见操作是入栈(push)和出栈(pop)。可以使用链表或数组实现。最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top）。

对于数组和链表（知道尾部节点地址的情况下），入栈和出栈都是O(1)复杂度。

 

 

队列是一种先进先出的线性结构，队列的 出口端叫作队头（front），队列的入口端叫作队尾（rear）。可以使用链表或数组实现。

下面是以数组为基础的队列：

 

很简单，我们不对数组中的元素做移位操作，而是用两个指针标记队头和队尾。当有元素从队头弹出，就将队头指针移向下一个下标位置。当有元素入队则放到数组后面，如果数组后面的位置满了而队头前的元素位置变成空闲的位置，这个元素就放到前面这些空闲位置，而此时队尾也会移向前面的这个新加入的元素所在下标。

如果队列数组放满了元素之后还要再放入元素，则对数组扩容，并将旧数组的内容拷贝到新数组上。

 

如下图所示

 

继续放入 8 5 1 4。

需要注意的是，队尾指针是不指向任何元素的，数组需要留出一个位置不存储任何元素。当整个队列满了之后，此时可以有两种策略，一种是扩容，一种是队尾的元素覆盖队首的元素。

结合队列和栈的特点，既能先进先出，也能先进后出的数据结构是双端队列。

双端队列也是可以用数组或队列为基础。如果以数组为基础，依旧是使用循环队列的思路进行入队出队和入栈出栈。如果是以链表为基础，只需为节点加上向前和向后两个指针即可。

 

下面是用双端队列（链表）实现的一个队列

/** 链表节点 **/
type IntNode struct{	// 值为整型的链表节点
	Prev *IntNode		// 向前指针
	Next *IntNode		// 向后指针
	Key int		// key
	Val  int	// 值
}

func InitIntNode(key, val int) *IntNode{
	node := IntNode{Key:key, Val:val}
	return &node
}

/** 双向链表 **/
type DoubleLinkedList struct{
	Head *IntNode		// 头部节点
	Tail *IntNode		// 尾部节点
	Length int		// 节点数
}

func initDoubleLinkedList() *DoubleLinkedList{
	linkedList := DoubleLinkedList{}
	linkedList.Head = &IntNode{}	// 虚拟头尾节点
	linkedList.Tail = &IntNode{}
	linkedList.Head.Next = linkedList.Tail
	linkedList.Tail.Prev = linkedList.Head
	return &linkedList
}

// 移除某个节点
func (ll *DoubleLinkedList) remove(node *IntNode) *IntNode{
	if node.Prev != nil{
		node.Prev.Next = node.Next
	}

	if node.Next != nil {
		node.Next.Prev = node.Prev
	}

	ll.Length--
	return node
}

// 从头部弹出一个节点
func (ll *DoubleLinkedList) shift() (deleteNode *IntNode){
	if(ll == nil || ll.Length == 0){
		return
	}

	return ll.remove(ll.Head.Next)
}

// 往后插入一个节点
func (ll *DoubleLinkedList) append(key, val int) *IntNode{
	if(ll == nil){
		ll = initDoubleLinkedList()
	}

	node := InitIntNode(key, val)
	ll.appendNode(node)
	return node
}

func (ll *DoubleLinkedList) appendNode(node *IntNode) *IntNode{
	if(ll == nil){
		ll = initDoubleLinkedList()
	}

	lastNode := ll.Tail.Prev
	lastNode.Next = node
	ll.Tail.Prev = node
	node.Prev = lastNode
	node.Next = ll.Tail
	ll.Length++
	return node
}

func (ll *DoubleLinkedList) getHead() *IntNode{
	if ll.Length == 0{
		return nil
	}
	return ll.Head.Next
}

func (ll *DoubleLinkedList) getTail() *IntNode{
	if ll.Length == 0{
		return nil
	}
	return ll.Tail.Prev
}

代码中在头部和尾部加了两个虚拟节点，通过虚拟节点可以在入队和出队以及在链表中间插入节点时减少很多边界条件的判断（例如当链表只有一个节点时弹出节点，或者链表没有节点时链入一个节点）。这是实现链表的有用小技巧。

 

· 用队列实现栈

队列实现栈比较简单，入栈时和正常的队列入队没有区别，但出栈时需要把除了队尾最后一个元素之外的其他所有元素出队并且全部按出队顺序入队。这么一来队首元素就是原本的队尾元素，也就是容器中最新的那个元素，将这个元素出队即可实现逻辑上的出栈。

 

实现如下：

package practice

import "container/list"

type StackByQueue struct{
   queue *list.List      // 单向链表实现的队列
   lastNode *list.Element       // 栈顶节点
}

func InitStackByQueue() *StackByQueue{
   return &StackByQueue{queue:list.New()}
}

func (this *StackByQueue) Enqueue(val int){
   this.queue.PushBack(val)
   this.lastNode = this.queue.Back()
}

func (this *StackByQueue) Dequeue() *list.Element{
   if this.queue.Len() == 0{
      return nil
   }
   for this.lastNode != this.queue.Front(){
      popNode := this.queue.Front()
      this.queue.MoveToBack(popNode)
   }
   enqueueNode := this.queue.Front()
   this.queue.Remove(enqueueNode)
   this.lastNode = this.queue.Back()
   return enqueueNode
}

func (this *StackByQueue) Len() int{
   return this.queue.Len()
}

 

 

· 栈实现队列

使用两个栈可以实现一个队列，假设栈为S1和S2，S1只负责接收入队元素（模拟队尾），S2只负责把元素出队。入队操作就是把元素入栈S1，当出队时需要从S2出栈，如果S2没有元素，则从S1出栈所有元素并放入到S2，这么一来栈S1的元素就会按照相反的顺序被存放到S2中，使得S2出栈时会先出栈早入队的元素实现先进先出。

 

入队时

 

出队时

 

代码实现：

import "zbp_struct/struct/list"

// 用栈模拟队列
type QueueByStack struct{
   StackForIn *list.LinkedList // 入队栈
   StackForOut *list.LinkedList   // 出队栈
   Length int
}

func InitStackQueue() (qbs *QueueByStack){
   stackForIn := list.InitLinkedList()
   stackForOut := list.InitLinkedList()
   return &QueueByStack{
      StackForIn: stackForIn,
      StackForOut: stackForOut,
   }
}

func (qbs *QueueByStack) Enqueue(val interface{}){
   qbs.StackForIn.UnShift(val)
   qbs.Length++
}

func (qbs *QueueByStack) Dequeue() (val interface{}) {
   if qbs.Length == 0{
      return nil
   }

   if qbs.StackForOut.Length == 0 {   // 如果出队栈没有元素则将入队栈的元素转移到出队栈
      for qbs.StackForIn.Length > 0 {
         qbs.StackForOut.UnShift(qbs.StackForIn.Shift())
      }
   }
   qbs.Length--
   return qbs.StackForOut.Shift()
}