无基础学数据结构与算法（数据结构与算法）

头条的代码显示做的不大美观，建议去微信公众号阅读，行知老王

队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()，而队列也只支持两个操作：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

队列分为单向队列、双向队列和优先级队列，其中单向队列又分为顺序队列、链式队列和循环队列。双向队列使用场景很少，本文不做赘述。

顺序队列

用数组实现的栈叫做顺序栈，用数组实现的队列也就叫做顺序队列。下边我们看下如何用数组实现简单的队列：

public class ArrayQueue { // 数组：items，数组大小：n private 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; } public void printAll() { for (int i = head; i < tail; i) { System.out.print(items[i] " "); } System.out.println(); } }

解释一下上面的代码，栈只需要一个栈顶指针就可以了，但是队列需要两个指针，一个是head指针，指向队头，一个是tail指针，指向队尾。如下图所示，当A、B、C、D依次入队之后，队列中的head指针指向下标为0的位置，tail指针指向下标为4的位置，这时没有进行出队操作。当我们调用两次出队操作之后，队列中的head指针指向下标为2的位置，tail指针仍然指向下标为4的位置，因为队列是先进先出的线性表嘛，所以出队操作时的顺序也是A、B、C、D，请看下图：

随着不停的进行入队、出队操作，head指针和tail指针都会持续性的向后移动。当tail移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据，这时候就需要进行数据搬移，当然没必要每次入队出队操作都进行数据搬移，只在入队时进行判断，如果没有空闲空间了再进行一次集中的数据搬移即可。改造后的入队操作如下：

// 优化后的入队操作，主要解决队列tail移动到最右边后无法继续入队的问题，将 item 放入队尾 public boolean enqueueBaseOptimize(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 和 tail tail -= head; head = 0; } items[tail] = item; tail; return true; }

从代码中我们看到，当队列的tail指针移动到数组的最右边后，如果有新的数据入队，我么可以将head到tail之间的数据，整体搬移到数组中0到tail-head的位置。

链式队列

用链表实现的栈叫做链式栈，那用链表实现的队列也就叫做链式队列。链表实现队列，同样需要两个指针，head指针和tail指针。入队操作时，指针变化为：

tail——>next = 新入队的节点，tail = tail——>next

出队操作时，指针变化为：

head = head ——>next

具体代码如下：

public class QueueBasedOnLinkedList { // 队列的队首和队尾 private Node head = null; private Node tail = null; // 入队 public void enqueue(String value) { if (tail == null) { Node newNode = new Node(value, null); head = newNode; tail = newNode; } else { tail.next = new Node(value, null); tail = tail.next; } } // 出队 public String dequeue() { if (head == null) return null; String value = head.data; head = head.next; if (head == null) { tail = null; } return value; } public void printAll() { Node p = head; while (p != null) { System.out.print(p.data " "); p = p.next; } System.out.println(); } private static class Node { private String data; private Node next; public Node(String data, Node next) { this.data = data; this.next = next; } public String getData() { return data; } } }

循环队列

循环队列，顾名思义，就是一个环状的队列，它的head和tail是相连的，组成一个环状结构。如下图所示：

从上图我们可以看到，这个循环队列的大小为8，当前状态head=4,tail=7，当有一个新的元素H入队时，我们放入下标为7的位置，但是这个时候，tail指针并不是更新为8，而是后移一位，更新到下标为0的位置，当再有一个元素I入队时，我们将I放入下标为0的位置，然后tail指针更新为1，如下图所示：

循环队列可以避免数据搬移的操作，但是最主要的是，如何判断队列空和队列满的状态。在用数组实现的非循环队列中，队列满的判断条件是tail==数组的大小n，队列空的判断条件是head==tail，在循环队列中，队列空的判断条件仍然是head==tail，但是队列满的判断条件就有些复杂了，一般情况下，我们知道，当队列满时，tail 1 = head，但是有个特殊情况，就是tail = n - 1、head = 0，这时候，tail 1 = n，而head = 0，也就是tail正好在最后一个存储空间、head还在第一个存储空间时，这时候就必须使用(tail 1)%n == n%n == 0 == head，tail 1的最大值就是n，不会大于n，这样tail 1除了最大值，不然怎么%n都是tail 1本身。也就是head，所以到现在，循环队列满的判断表达式就出来了，就是(tail 1)%n=head，循环队列满的状态如下图所示：

当队列满时，tail指向的位置上是没有数据的，所以，循环队列会浪费一块存储空间。代码实现如下：

public class CircularQueue { // 数组：items，数组大小：n private String[] items; private int n = 0; // head表示队头下标，tail表示队尾下标 private int head = 0; private int tail = 0; // 申请一个大小为capacity的数组 public CircularQueue(int capacity) { items = new String[capacity]; n = capacity; } // 入队 public boolean enqueue(String item) { // 队列满了 if ((tail 1) % n == head) return false; items[tail] = item; tail = (tail 1) % n; return true; } // 出队 public String dequeue() { // 如果head == tail 表示队列为空 if (head == tail) return null; String ret = items[head]; head = (head 1) % n; return ret; } public void printAll() { if (0 == n) return; for (int i = head; i % n != tail; i) { System.out.print(items[i] " "); } System.out.println(); } }

优先级队列

优先级队列（priority queue）是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

优先级队列是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有：查找、插入、删除。一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。

本文我们用数组实现优先级队列，这种方式比较简单，适用于数据量比较小并且不要求插入速度的情况。声明为int类型的数组，关键字是数组里面的元素，在插入的时候按照从大到小的顺序排列，也就是越小的元素优先级越高。代码如下：

public class PriorityQue { private int maxSize; private int[] priQueArray; private int nItems; public PriorityQue(int s) { maxSize = s; priQueArray = new int[maxSize]; nItems = 0; } // 插入数据 public void insert(int value) { int j; if (nItems == 0) { priQueArray[nItems ] = value; } else { j = nItems - 1; // 选择的排序方法是插入排序，按照从大到小的顺序排列，越小的越在队列的顶端 while (j >= 0 && value > priQueArray[j]) { priQueArray[j 1] = priQueArray[j]; j--; } priQueArray[j 1] = value; nItems ; } } // 移除数据,由于是按照大小排序的，所以移除数据我们指针向下移动 // 被移除的地方由于是int类型的，不能设置为null，这里的做法是设置为 -1 public int remove() { int k = nItems - 1; int value = priQueArray[k]; priQueArray[k] = -1;// -1表示这个位置的数据被移除了 nItems--; return value; } // 查看优先级最高的元素 public int peekMin() { return priQueArray[nItems - 1]; } // 判断是否为空 public boolean isEmpty() { return (nItems == 0); } // 判断是否满了 public boolean isFull() { return (nItems == maxSize); } }

insert方法，先检查队列中是否有数据项，如果没有，则直接插入到下标为0的单元里，否则，从数组顶部开始比较，找到比插入值小的位置进行插入，并把 nItems 加1。remove方法直接获取顶部元素。优先级队列的插入操作需要O(N)的时间，而删除操作则需要O(1)的时间。

双端队列、阻塞队列、并发队列

双端队列就是一个两端都是结尾或者开头的队列， 队列的每一端都可以进行插入数据项和移除数据项，如果严格禁止调用从同一边进出的操作，那么双端队列的功能就和前面讲的栈功能一样。如果严格禁止调用从一边进另一边出的操作，那么双端队列的功能就和单向队列一样了。

阻塞队列其实就是在队列的基础上增加了阻塞操作，也就是队列为空的时候，从队头取数据会阻塞，因为这时候队列中没有数据可取，直到队列有了数据才能返回，如果队列已经满了，那么插入数据的操作将被阻塞，直到队列中有空闲位置后再插入数据才能返回。这其实就是“生产者-消费者”模型，我们可以用阻塞队列实现一个“生产者-消费者”模型。

并发队列解决多个线程操作同一个队列时，引发的线程安全问题。简单的实现方式就是在入队和出队的操作上加锁，但是，加锁后速度会降低，同一时刻仅允许一个线程存或者取的操作。

实际上，基于数组的循环队列，利用CAS原子操作，可以实现非常高效的并发队列，这也是循环队列比链式队列应用更加广泛的原因。

有关CAS（Conmpare And Swap 比较和交换）的知识可以参考下面几篇文章：

• https://blog.csdn.net/hanchao5272/article/details/79947785
• https://blog.csdn.net/ma15732625261/article/details/82620730
• https://www.cnblogs.com/dongguacai/p/6003078.html
• https://cloud.tencent.com/developer/article/1347598

思考

线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？

两种方式：

1. 非阻塞的处理方式，直接拒绝任务请求。
2. 阻塞的处理方式，将请求排队，等有空闲线程时，取出排队的请求进行处理。

基于链表的链式队列，可以实现一个无限排队的无界队列（unbounded queue），这样会导致过多的请求排队等待，请求的处理时间过长，针对响应时间比较敏感的系统，基于链表的无界队列线程池不合适。

而基于数组的有界队列，队列的大小有限，线程池中排队的请求超过队列大小时，新的请求就会被拒绝，这种方式适合于对响应时间敏感的系统。

总结

吃多了拉就是队列，吃多了吐就是栈。

行知老王

,