转载请注明出处: 数据结构——Golang实现队列

1. 介绍

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

数据结构里的队列就是模仿现实中的排队。

1） 新来的都排在队尾；
2） 最前面的办理业务后离队，后面一个跟上。
根据特点，计算机砖家就归纳以下队列结构。

2. Golang 实现

2.1. 队列结构

同前文的栈一样，在这里，我把队列拆分为两个部分，容器和链表，容器用结构体实现，链表用单链表，当然大家也可以用其他链表结构，甚至数组来实现。

这里的例子，也是使用单链表实现的。

// Queue 队列信息 type Queue struct{ list *SingleList } 

2.2. 队列初始化

队列的初始化，也即是内部的链表初始化：

// Init 队列初始化 func (q *Queue)Init() { q.list = new(SingleList) q.list.Init() } 

2.3. 入队(Enqueue)

从队尾添加数据到队列，称为入队(Enqueue)

// Enqueue 进入队列 func (q *Queue) Enqueue(data interface{}) bool{ return q.list.Append(&SingleNode{Data:data}) } 

2.4. 出队(Dequeue)

从队头取出数据称为出队或出列(Dequeue)

// Dequeue 出列 func (q *Queue) Dequeue() interface{}{ node := q.list.Get(0) if node == nil{ return nil } q.list.Delete(0) return node.Data } 

2.5. 查看队头元素(Peek)

查看队头元素，但不取出：

// Peek 查看队头信息 func (q *Queue)Peek() interface{}{ node := q.list.Get(0) if node == nil{ return nil } return node.Data } 

2.6. 获取队列长度(Size)

获取当前队列中所有元素的数量：

// Size 获取队列长度 func (q *Queue) Size() uint{ return q.list.Size } 

3. 单元测试

package dstr import( "testing" ) func TestQueue_Init(t *testing.T) { q := new(Queue) q.Init() } func TestQueue_Enqueue(t *testing.T){ q := new(Queue) q.Init() q.Enqueue(1) if 1 == q.Size(){ t.Log("queue size and enquqeuesuccess") } else { t.Error("queue size and enqueue failed") } } func TestQueue_Dequeue(t *testing.T){ q := new(Queue) q.Init() d1 := q.Dequeue() if d1 == nil{ t.Log("empty queue dequeue success") } else { t.Error("empty queue dequeue failed") } q.Enqueue(1) d := q.Dequeue() if 1 == d.(int) && q.Size() == 0{ t.Log("queue dequeue success") } else { t.Error("queue dequeue failed") } } func TestQueue_Peek(t *testing.T){ q := new(Queue) q.Init() d1 := q.Peek() if d1 == nil{ t.Log("empty queue peek success") }else { t.Error("empty queue peek failed") } q.Enqueue(1) d := q.Peek() if 1 == d.(int) && q.Size() == 1{ t.Log("queue peek success") } else { t.Error("queue peek failed") } } 

4. 源码

github源码

5. 参考文献

Go数据结构之队列

完

转载请注明出处: 数据结构——Golang实现队列