数据结构——Golang实现队列

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

Golang

1. 介绍

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

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

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

image.png

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数据结构之队列

完