1 队列的概念
队列是有序集合，遵循 FIFO （First in first out，即先进先出）排队方法的容器。添加操作发生在队列的尾部，移除操作则发生在头部。新元素从尾部进入队列，然后一直向前移动到头部，直到下一个被移除的元素。
在日常生活中，我们经常需要排队，这就是队列数据结构的生活例子。排队的概念可以通过在快递驿站取快递的队伍来解释：
当我们进入排队时，我们站在队伍的末端，排在队伍最前面的人就是下一个被服务的人。他拿完快递，就可以退出队列。
当这种情况发生时，下一个人将来到队伍的最前面，将退出队列并得到服务。随着排在队首的每个人不断退出队列，我们向队首移动。最后，我们将到达队首，我们将退出队列并拿到快递。在需要保持先到先服务的情况下，这种行为是非常有用的。
队列的应用
在计算机系统内部，操作系统使用一些队列来控制计算机进程。调度机制往往基于一个队列算法，其目标是尽可能快地执行程序，同时服务尽可能多的用户。
在打字时，我们有时会发现字符出现的速度比击键速度慢。这是由于计算机正在做其他的工作。击键操作被放入一个类似于队列的缓冲区，以便对应的字符按正确的顺序显示。
队列还能用于：
2 队列抽象数据类型
如上，队列中的插入和删除必须遵循 FIFO 方案。为了简单起见，我们假设元素是整数。
主要的队列操作
EnQueue(item)：在队列的尾部添加一个元素，它需要一个元素作为参数，不返回任何值
DeQueue()：从队列的头部移除一个元素。它不需要参数，并修改队列的内容
Front()：返回前面的元素，但不删除它
Rear()：返回后面的元素，而不将其删除
Size() int：返回存储在队列中的元素数量。它不需要参数，且会返回一个整数
isEmpty() bool：判断队列是否为空。它不需要参数，且会返回一个布尔值
3 Go 如何实现队列
在 Go 语言中，队列的实现方式也有很多，一些常用的方法列举如下：
链表实现
切片实现
使用通道实现队列
基于循环数组的简单实现
基于动态循环数组的实现
3.1 List 实现
可以利用 Go 语言内置的 container/list 包来实现：
package main
import ( "container/list" "fmt")
type customQueue struct { queue *list.List}
func (c *customQueue) Enqueue(value string) { c.queue.PushBack(value)}
func (c *customQueue) Dequeue() error { if c.queue.Len() > 0 { ele := c.queue.Front() c.queue.Remove(ele) } return fmt.Errorf("Pop Error: Queue is empty")}
func (c *customQueue) Front() (string, error) { if c.queue.Len() > 0 { if val, ok := c.queue.Front().Value.(string); ok { return val, nil } return "", fmt.Errorf("Peep Error: Queue Datatype is incorrect") } return "", fmt.Errorf("Peep Error: Queue is empty")}
func (c *customQueue) Size() int { return c.queue.Len()}
func (c *customQueue) Empty() bool { return c.queue.Len() == 0}
func main() { customQueue := &customQueue{ queue: list.New(), } fmt.Printf("Enqueue: A\n") customQueue.Enqueue("A") fmt.Printf("Enqueue: B\n") customQueue.Enqueue("B") fmt.Printf("Size: %d\n", customQueue.Size()) for customQueue.Size() > 0 { frontVal, _ := customQueue.Front() fmt.Printf("Front: %s\n", frontVal) fmt.Printf("Dequeue: %s\n", frontVal) customQueue.Dequeue() } fmt.Printf("Size: %d\n", customQueue.Size())}
复制代码
输出：
Enqueue: AEnqueue: BSize: 2Front: ADequeue: AFront: BDequeue: BSize: 0
复制代码
3.2 切片实现
切片也可以实现相同的功能：
package main
import ( "fmt" "sync")
type customQueue struct { queue []string lock sync.RWMutex}
func (c *customQueue) Enqueue(name string) { c.lock.Lock() defer c.lock.Unlock() c.queue = append(c.queue, name)}
func (c *customQueue) Dequeue() error { if len(c.queue) > 0 { c.lock.Lock() defer c.lock.Unlock() c.queue = c.queue[1:] return nil } return fmt.Errorf("Pop Error: Queue is empty")}
func (c *customQueue) Front() (string, error) { if len(c.queue) > 0 { c.lock.Lock() defer c.lock.Unlock() return c.queue[0], nil } return "", fmt.Errorf("Peep Error: Queue is empty")}
func (c *customQueue) Size() int { return len(c.queue)}
func (c *customQueue) Empty() bool { return len(c.queue) == 0}
func main() { customQueue := &customQueue{ queue: make([]string, 0), }
fmt.Printf("Enqueue: A\n") customQueue.Enqueue("A") fmt.Printf("Enqueue: B\n") customQueue.Enqueue("B") fmt.Printf("Len: %d\n", customQueue.Size())
for customQueue.Size() > 0 { frontVal, _ := customQueue.Front() fmt.Printf("Front: %s\n", frontVal) fmt.Printf("Dequeue: %s\n", frontVal) customQueue.Dequeue() } fmt.Printf("Len: %d\n", customQueue.Size())}
复制代码
运行结果：
Enqueue: AEnqueue: BSize: 2Front: ADequeue: AFront: BDequeue: BSize: 0
复制代码
3.3 使用缓冲通道实现队列
从通道中写和读也经常是一个更好的选择。下面是一个使用通道实现队列的例子。
package main
import "fmt"
func main() { queueChan := make(chan int, 200) value1 := 5 value2 := 4 value3 := 6 // enqueue queueChan <- value1 queueChan <- value2 queueChan <- value3
// dequeue and return the value receice := <-queueChan fmt.Println("dequeue 1st time: ", receice) receice2 := <-queueChan fmt.Println("dequeue 2nd time: ", receice2)
if len(queueChan) == 0 { fmt.Println("Queue is empty") } else { fmt.Println("Queue is not empty") }}
复制代码
运行结果：
dequeue 1st time: 5dequeue 2nd time: 4Queue is not empty
复制代码
3.4 循环数组的实现
首先，让我们看看我们是否可以像对待堆栈那样使用简单的数组来实现队列。我们知道，在队列中，插入是在一端进行，删除是在另一端进行。在进行了一些插入和删除之后，这个过程就变得容易理解了。
如果是数组实现的话，随着我们队列的入队和出队，数组的初始内存位置被浪费了。所以简单的数组实现队列并不高效。
为了解决这个问题，可以使用圆形数组。这意味着，把最后一个元素和第一个数组元素视为连续的。使用这个方式，空间能够得到有效利用。
package main
import ( "bytes" "fmt")
const MaxInt = int(^uint(0) >> 1)const MinInt = -MaxInt
type Queue struct { array []interface{} front int rear int capacity int size int}
func New(capacity int) *Queue { return new(Queue).Init(capacity)}
func (q *Queue) Init(capacity int) *Queue { q.array = make([]interface{}, capacity) q.front, q.rear, q.size, q.capacity = -1, -1, 0, capacity return q}
func (q *Queue) length() int { return q.size}
func (q *Queue) isEmpty() bool { return q.size == 0}
func (q *Queue) isFull() bool { return q.size == q.capacity}
func (q *Queue) String() string { var result bytes.Buffer result.WriteByte('[') j := q.front for i := 0; i < q.size; i++ { result.WriteString(fmt.Sprintf("%v", q.array[j])) if i < q.size-1 { result.WriteByte(' ') } j = (j + 1) % q.capacity } result.WriteByte(']') return result.String()}
func (q *Queue) Front() interface{} { return q.array[q.front]}
func (q *Queue) Back() interface{} { return q.array[q.rear]}
func (q *Queue) enQueue(v interface{}) { if q.isFull() { return }
q.rear = (q.rear + 1) % q.capacity q.array[q.rear] = v if q.front == -1 { q.front = q.rear } q.size++}
func (q *Queue) dequeue() interface{} { if q.isEmpty() { return MinInt }
data := q.array[q.front] if q.front == q.rear { q.front = -1 q.rear = -1 q.size = 0 } else { q.front = (q.front + 1) % q.capacity q.size -= 1 } return data}
func main() { var q Queue q.Init(6) q.enQueue(1) q.enQueue(2) q.enQueue(3) q.enQueue(4) q.enQueue(5)
q.enQueue(2022) fmt.Println("现在的队列：", q.String())
fmt.Println("出队元素：", q.dequeue())
fmt.Println("队列的长度：", q.length()) fmt.Println("当前队首：", q.Front()) fmt.Println("当前队尾:", q.Back()) }
复制代码
运行结果：
3.5 动态数组的实现
当队列满的时候，在原有的代码上增加一个 resize() 函数，用于重新分配数组大小：
func (q *Queue) resize() { size := q.capacity q.capacity = q.capacity * 2 adjusted := make([]interface{}, q.capacity) if q.front < q.rear { copy(adjusted, q.array[q.front:q.rear+1]) } else { n := copy(adjusted, q.array[q.front:]) copy(adjusted[n:], q.array[:q.rear+1]) } q.array = adjusted q.front = 0 q.rear = size - 1}
复制代码
完整代码如下：
package main
import ( "bytes" "fmt")
const MaxInt = int(^uint(0) >> 1)const MinInt = -MaxInt
type Queue struct { array []interface{} front int rear int capacity int size int}
func New(capacity int) *Queue { return new(Queue).Init(capacity)}
func (q *Queue) Init(capacity int) *Queue { q.array = make([]interface{}, capacity) q.front, q.rear, q.size, q.capacity = -1, -1, 0, capacity return q}
func (q *Queue) length() int { return q.size}
func (q *Queue) isEmpty() bool { return q.size == 0}
func (q *Queue) isFull() bool { return q.size == q.capacity}
func (q *Queue) String() string { var result bytes.Buffer result.WriteByte('[') j := q.front for i := 0; i < q.size; i++ { result.WriteString(fmt.Sprintf("%v", q.array[j])) if i < q.size-1 { result.WriteByte(' ') } j = (j + 1) % q.capacity } result.WriteByte(']') return result.String()}
func (q *Queue) Front() interface{} { return q.array[q.front]}
func (q *Queue) Back() interface{} { return q.array[q.rear]}
func (q *Queue) resize() { size := q.capacity q.capacity = q.capacity * 2 adjusted := make([]interface{}, q.capacity) if q.front < q.rear { copy(adjusted, q.array[q.front:q.rear+1]) } else { n := copy(adjusted, q.array[q.front:]) copy(adjusted[n:], q.array[:q.rear+1]) } q.array = adjusted q.front = 0 q.rear = size - 1}
func (q *Queue) enQueue(v interface{}) { if q.isFull() { // return q.resize() }
q.rear = (q.rear + 1) % q.capacity q.array[q.rear] = v if q.front == -1 { q.front = q.rear } q.size++}
func (q *Queue) dequeue() interface{} { if q.isEmpty() { return MinInt }
data := q.array[q.front] if q.front == q.rear { q.front = -1 q.rear = -1 q.size = 0 } else { q.front = (q.front + 1) % q.capacity q.size -= 1 } return data}
func main() { var q Queue q.Init(1) // 初始化长度为 1 的队列 q.enQueue(1) q.enQueue(2) q.enQueue(3) q.enQueue(4) q.enQueue(5) q.enQueue(2012) q.enQueue(2022) fmt.Println("现在的队列：", q.String())
fmt.Println("出队元素：", q.dequeue())
fmt.Println("队列的长度：", q.length()) fmt.Println("当前队首：", q.Front()) fmt.Println("当前队尾:", q.Back())
}
复制代码
运行代码：
3.6 自定义链表实现
我们也可以自己定义链表结构来实现队列。
package main
import ( "bytes" "errors" "fmt")
type ListNode struct { data interface{} next *ListNode}
type Queue struct { front *ListNode rear *ListNode size int}
func (q *Queue) enQueue(data interface{}) { rear := new(ListNode) rear.data = data if q.isEmpty() { q.front = rear } else { oldLast := q.rear oldLast.next = rear } q.rear = rear q.size++}
func (q *Queue) deQueue() (interface{}, error) { if q.isEmpty() { q.rear = nil return nil, errors.New("unable to deQueue element, queue is empty") } data := q.front.data q.front = q.front.next q.size-- return data, nil}
func (q *Queue) frontElement() (interface{}, error) { if q.isEmpty() { return nil, errors.New("unable to peek element, queue is empty") } return q.front.data, nil}
func (q *Queue) isEmpty() bool { return q.front == nil}
func (q *Queue) length() int { return q.size}
func (q *Queue) String() string { var result bytes.Buffer result.WriteByte('[')
j := q.front for i := 0; i < q.size; i++ { result.WriteString(fmt.Sprintf("%v", j.data)) if i < q.size-1 { result.WriteByte(' ') } j = j.next } result.WriteByte(']') return result.String()}
func main() { q := new(Queue) q.enQueue(1) q.enQueue(2) q.enQueue(3)
fmt.Println(q.String()) fmt.Println(q.length()) fmt.Println(q.deQueue())
}
复制代码
运行结果：
$ go run main.go [1 2 3]31 <nil>
复制代码
4 总结
本文介绍了队列的概念，学习了队列这一数据结构的抽象数据类型，最后用 Go 语言的自带数据结构列表和切片实现了队列，也用循环数组和自定义链表分别实现队列。队列在计算机的运用广泛，希望读者能够好好利用这一容器。
希望本文能对你有所帮助，如果喜欢本文，可以点个关注。
这里是宇宙之一粟，下一篇文章见！
宇宙古今无有穷期，一生不过须臾，当思奋争。
评论