队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。

下面我们用Go来实现一下Queue

实现

在内部,队列将用一个slice类型表示,我将公开以下方法

  • New()
  • Enqueue()
  • Dequeue()
  • Front()
  • IsEmpty()
  • Size()

New() 用作构造函数,在我们开始使用它时初始化内部切片。

我将创建一个Queue通用类型,并发安全,可以通过使用生成包含任何类型的队列,创建特定于类型的队列实现,封装包含数据的实际值特定数据结构。

// 一个存放Item带锁安全的队列(先进先出(FIFO—first in first out))
type Queue struct {
    items []Item
    lock  sync.RWMutex
}

// 创建一个队列
func (q *Queue) New() *Queue {
    q.items = []Item{}
    return q
}

// 入队(添加一个元素到队尾)
func (q *Queue) Enqueue(t Item) {
    q.lock.Lock()
    q.items = append(q.items, t)
    q.lock.Unlock()
}

// 出队(删除对头元素)
func (q *Queue) Dequeue() *Item {
    q.lock.Lock()
    item := q.items[0]
    q.items = q.items[1:len(q.items)]
    q.lock.Unlock()
    return &item
}

// 获取对头元素
func (q *Queue) Front() *Item {
    q.lock.RLock()
    item := q.items[0]
    q.lock.RUnlock()
    return &item
}

// 判断队列是否为空
func (q *Queue) IsEmpty() bool {
    return len(q.items) == 0
}

// 返回队列中元素大小
func (q *Queue) Size() int {
    return len(q.items)
}

测试

测试上述公开的方法

import (
    "testing"
)

var q Queue

func initQueue() *Queue {
    if q.items == nil {
        q = Queue{}
        q.New()
    }
    return &q
}

func TestEnqueue(t *testing.T) {
    s := initQueue()
    s.Enqueue(1)
    s.Enqueue(2)
    s.Enqueue(3)

    if size := s.Size(); size != 3 {
        t.Errorf("wrong count, expected 3 and got %d", size)
    }
}

func TestDequeue(t *testing.T) {
    q.Dequeue()
    if size := len(q.items); size != 2 {
        t.Errorf("wrong count, expected 2 and got %d", size)
    }

    q.Dequeue()
    q.Dequeue()
    if size := len(q.items); size != 0 {
        t.Errorf("wrong count, expected 0 and got %d", size)
    }

    if !q.IsEmpty() {
        t.Errorf("IsEmpty should return true")
    }
}