数据结构队列-先进先出

一，概述

队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。

二，顺序队列和链式队列

队列和栈一样，也是一种抽象的数据结构，操作上具有“先进先出”的特性，队列只允许在"队首"进行删除操作，而在"队尾"进行插入操作。基于数组实现的顺序队列的C++代码如下：

// 用数组实现的队列
class ArrayQueue(){// 数组：items，数组大小：n
private:int n = 20;int head = 0;   // 队头下标int tail = 0;   // 队尾下标public:// 带参数的构造函数：申请一个大小为 capacity 的数组ArrayQueue(int capacity){// items = new int[capacity];vector<int> items(capacity);n = capacity;}// 入队bool enqueue(int item){if(tail == n) return False;items[tail] = item;++tail;return True;}// 时间复杂度为O(1)的入队操作bool enqueue2(int item){// tail == n，表示队列末尾没有空间了if(tail == n){// tail == n && head == 0，表示整个队列都占满了if(head == 0) return False;// 数据搬移for(i=head; i<tail; ++i){items[i-head] = items[i];}// 重新更新 head 和 tailtail = tail - head; // tail -= headhead = 0;   // 队首位置}items[tail] = item;++tail;return True;}// 出队bool dequeue(){// head == tail 表示队列为空if (head == tail) return null;int ret = items[tail];++head;return ret;}
}

入队时间复杂度为 O(1)。分析：大部分情况下入队操作时间复杂度为 O(1)，只有在 tail 在末尾时( tail=n )才进行数据迁移，此时的入队操作时间复杂度为 O(n)，根据均摊时间复杂度得到入队时间复杂度为 O(1)。

三，循环队列

前面用数组实现队列，当 tail = n 时，会有数据搬移操作。循环队列首尾相连，用数组实现循环队列代码的关键在于判断队列满和空的条件。

• 非循环队列:
  • 队满：tail = n
  • 队空：head = tail
• 循环队列：
  • 队满：(tail + 1) % n = head
  • 队空：head = tail

基于数组实现的循环队列的C++代码如下：

// 用数组实现的循环队列，关键在于创建队头和队尾下标
class CircularQueue(){
private:int n = 12;int items[];// head表示队头下标，tail表示队尾下标int head = 0;int tail = 0;
public:CircularQueue(int capacity){// items = new int[capacty];vector<int> items(capacity);n = capacity;}// 入队函数bool enqueue(int item){// 队列满了if((tail+1)%n = head) return False;items[tail] = item;tail = (tail + 1) % n}// 出队函数int dequeue(){// // 如果head == tail 表示队列为空if(head == tail) return null;int ret = items[head];head = (head + 1) % n;return ret;}
}

四，阻塞队列和并发队列

1. 阻塞队列就是入队、出队操作都可以阻塞，简单来说就是队列为空时，队首取数据会被阻塞，队列为满时，队尾插入数据会被阻塞，直到队列有空闲数据才允许在队尾插入数据。使用阻塞队列结构可以轻松实现“消费者-生产者模型”。
2. 并发队列就是队列的操作多线程安全。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

参考资料

《数据结构与算法之美》-队列