转载请注明出处: 数据结构——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实现队列

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传