Go的数据结构与实现【Queue】

介绍

与栈一样，队列也是最基本的数据结构之一。队列也是值的一种容器，其中值的插入和删除遵循“先进先出”（First-In-First-Out, FIFO）的原则⎯⎯也就是说，每次删除的只能是最先插入的值。

实现

队列的抽象数据类型就是一个数组，其中的值排成一个序列，我们只能访问和取出排在最前端（Front）的对象，只能在队列的尾部（Rear）插入新值。正是按照这一规则，才能保证最先被插入的对象首先被删除（FIFO）。

队列首先支持下面的两个基本方法：

在这里插入图片描述

此外，与栈类似，队列还支持如下的方法：
在这里插入图片描述

基于数组的简单实现

我们使用一个数组来模拟队列，队列的数据结构定义如下：

type T int

type Queue struct {
   sync.RWMutex
   array []T
}

我们依次去实现队列的方法，对于进队Enqueue()方法，直接利用go原生语句将值添加到数组切片中。

// Enqueue adds t to the end of the queue
func (q *Queue) Enqueue(t T) {
   q.Lock()
   q.array = append(q.array, t)
   q.Unlock()
}

出队Dequeue()和取队首元素Front()时注意数组空判断。

// Dequeue removes the start of from the queue
func (q *Queue) Dequeue() (error, *T) {
   q.Lock()

   if len(q.array) == 0 {
      q.Unlock()
      return fmt.Errorf("queue is empty"), nil
   }
   ret := q.array[0]
   q.array = q.array[1:len(q.array)]
   q.Unlock()

   return nil, &ret
}

// Front returns the start in the queue, without removing it
func (q *Queue) Front() (error, *T) {
   q.Lock()

   if len(q.array) == 0 {
      q.Unlock()
      return fmt.Errorf("queue is empty"), nil
   }
   ret := q.array[0]
   q.Unlock()

   return nil, &ret
}

剩下Size()以及IsEmpty()即对队列的数组大小进行判断取值。

// Size returns the size of the queue
func (q *Queue) Size() int {
   q.RLock()
   defer q.RUnlock()

   return len(q.array)
}

// IsEmpty returns true if the queue is empty
func (q *Queue) IsEmpty() bool {
   q.RLock()
   defer q.RUnlock()

   return len(q.array) == 0
}

单元测试

这里测试进队和出队方法：

import "testing"

var (
   t1 T = 1
   t2 T = 2
   t3 T = 3
)

func TestQueue_Enqueue(t *testing.T) {
   queue := NewQueue()
   queue.Enqueue(t1)
   queue.Enqueue(t2)
   queue.Enqueue(t3)

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

func TestQueue_Dequeue(t *testing.T) {
   queue := NewQueue()
   queue.Enqueue(t1)
   queue.Enqueue(t2)
   queue.Enqueue(t3)
   _, ret := queue.Dequeue()
   if *ret != t1 {
      t.Errorf("wrong result, expected %d and got %d", *ret, t1)
   }

   _, _ = queue.Dequeue()
   _, ret = queue.Dequeue()
   if *ret != t3 {
      t.Errorf("wrong result, expected %d and got %d", *ret, t3)
   }

   err, _ := queue.Dequeue()
   if !queue.IsEmpty() {
      t.Errorf("IsEmpty should return true")
   }
   if err == nil {
      t.Errorf("cannot operate dequeue when queue is empty")
   }
}