队列

什么是队列

  • 先进先出，也是一种操作受限的线性表数据结构。用数组实现的队列叫做顺序队列，用链表实现的队列叫做链式队列
  • 队列支持队头入队，队尾出队
  • 队列需要有两个指针 head 指向头指针，tail 指向队尾指针

队列实现

顺序队列

顺序队列当入队、出队时 head 指针和 tail都向后移。顺序队列当 tail 指针到达数组尾部，数组 索引 [0 - head] 之间的空间就会浪费掉，可以利用数据迁移的想法将在入队时将数据整体往前迁移。这样出队时间复杂度是 ${O(1)}$ ，入队时需要数据搬移，最好的情况就是 head 指针在数组索引 0 的位置，不需要迁移，否则假如队列有 n 个元素，则需要迁移 n 次。则平均时间复杂度$(1+2+3+…+n) / n = O(n)$。

链式队列

链式队列也需要两个指针，head 指针和 tail 指针。链式队列的出队、入队时间复杂度都是${O(1)}$。

1
2
3
4
5
// 入队操作
tail.next = newNode;
tail = tail.next;
// 出队操作
head = head.next;

循环队列

用数组实现的队列当出队时会造成空间浪费，所以需要数据搬移，利用循环队列来解决这个问题。

关键的地方是如何判断堆满和队空的条件：

1
2
head = (head + 1) % n;
tail = (tail + 1) % n;

阻塞队列

队列为空时出队操作会被阻塞，此时还无数据可取；队列满时入队被阻塞直到队列中有空闲位置。类似于 生产者-消费者 模型。当多个线程同时操作队列时就会出现线程安全问题。

并发队列

线程安全的队列叫做并发队列，需要在出队、入队操作上加锁。基于数组的循环队列利用 CAS 原子操作可以实现高效的并发队列。