【数据结构与算法】队列

一、是什么

一种先进先出的线性表数据结构，只支持入队和出队操作

二、使用场景

• MySQL连接池
• Redis单线程特性
• 分布式消息队列

三、工作原理

队尾插入元素，队头删除元素

四、队列类型

• 顺序队列：
  数组实现的就是顺序队列（有数据搬移操作）
• 循环队列：
  将数组的首尾相连，形成一个环（没有数据搬移操作）
• 阻塞队列：
  当队列为空时，从队头取数据会被阻塞；当队列已满时，插入数据的操作将被阻塞，形成一个生产者-消费者模型。
• 并发队列：
  在多线程情况下， 会有多个线程同时操作队列，此时如果是线程安全的队列我们就叫作并发队列。一般使用CAS（类似乐观锁）和锁来实现并发队列。

四、实现

• 代码实现

type list []int

func NewList() *list {
    newList := make(list, 0)
    return &newList
}

func listPush(newList *list, a ...int) {
    *newList = append(*newList, a...)
}

func listPop(newList *list) (listObj int) {
    length := len(*newList)
    if length <= 0 {
        return
    }
    listObj = (*newList)[0]
    *newList = (*newList)[1:length]
    return
}

• Redis实现

rpush + lpop = list（队列）

五、优劣

• 优点：

1. 不涉及到数组搬移时，出队和入队的时间复杂度都为 O(1)
2. 操作受限，使用比较可控，不容易出错（和数组、链表相比较）

• 缺点：

1. 在内存中，队列结构里的数据大小和生命周期是固定的，缺乏灵活性

六、替代性技术

• 数组
• 链表
• 栈