前言

很多语言框架都自带队列的实现，但是Go语言本身没有自带队列这种数据结构，最近在学习Go，于是很感兴趣并自己手动撸了一个队列，并用这个队列在leetcode中刷了几道题，效率还是很可观的。

思路

定义一个双向链表，定义队列具有头尾两个双向链表节点。当进行入队操作时将新增节点加入到队尾，入队节点即为新的队尾节点。当进行出队操作时，队头节点出队。出队节点的后驱节点即为新的头节点。以下图为例，当top节点出队时候，node1即为新的头节点。

双向链表

代码实现

package queue

type (
    //Queue 队列
    Queue struct {
        top    *node
        rear   *node
        length int
    }
    //双向链表节点
    node struct {
        pre   *node
        next  *node
        value interface{}
    }
)

// Create a new queue
func New() *Queue {
    return &Queue{nil, nil, 0}
}
//获取队列长度
func (this *Queue) Len() int {
    return this.length
}
//返回true队列不为空
func (this *Queue) Any() bool {
    return this.length > 0
}
//返回队列顶端元素
func (this *Queue) Peek() interface{} {
    if this.top == nil {
        return nil
    }
    return this.top.value
}
//入队操作
func (this *Queue) Push(v interface{}) {
    n := &node{nil, nil, v}
    if this.length == 0 {
        this.top = n
        this.rear = this.top
    } else {
        n.pre = this.rear
        this.rear.next = n
        this.rear = n
    }
    this.length++
}
//出队操作
func (this *Queue) Pop() interface{} {
    if this.length == 0 {
        return nil
    }
    n := this.top
    if this.top.next == nil {
        this.top = nil
    } else {
        this.top = this.top.next
        this.top.pre.next = nil
        this.top.pre = nil
    }
    this.length--
    return n.value
}

队列应用

图或者树的广度优先搜索算法需要使用队列，leetcode广度优先的题目不少。其中树的层序遍历会用到队列，利用已实现队列刷题验证执行效率如何，如下图，执行效率还是很可观的。