数据结构与算法之美笔记

数据结构与算法之美笔记 - 队列

本文主要是介绍数据结构与算法之美笔记 - 队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构与算法之美 - 09

一、队列的概念

队列，是一种操作受限的线性表数据结构，先进先出。

队列的应用：

Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
队列可以应用在任何有限资源池中，用于线程池请求排队，比如数据库连接池等。

⚠️ CPU 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。

二、队列的实现方式

队列可以用数组来实现，也可以用链表来实现，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

队列的数组实现：

队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

// 用数组实现的队列
public class ArrayQueue {// 数组：items，数组大小：nprivate String[] items;private int n = 0;// head表示队头下标，tail表示队尾下标private int head = 0;private int tail = 0;// 申请一个大小为capacity的数组public ArrayQueue(int capacity) {items = new String[capacity];n = capacity;}// 入队public boolean enqueue(String item) {// 如果tail == n 表示队列已经满了if (tail == n) return false;items[tail] = item;++tail;return true;}// 出队public String dequeue() {// 如果head == tail 表示队列为空if (head == tail) return null;// 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了String ret = items[head];++head;return ret;}
}

以上的实现方式的实现流程为：

取出队首，head后移，增加队尾tail后移。随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。

在出队时可以不用搬移数据。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。修改入队代码：

  // 入队操作，将item放入队尾public boolean enqueue(String item) {// tail == n表示队列末尾没有空间了if (tail == n) {// tail ==n && head==0，表示整个队列都占满了if (head == 0) return false;// 数据搬移for (int i = head; i < tail; ++i) {items[i-head] = items[i];}// 搬移完之后重新更新head和tailtail -= head;head = 0;}items[tail] = item;++tail;return true;}