数据结构与算法系列——队列

什么是队列

队列也是一种操作受限制的线性表，只允许在表的前端进行删除，也就是出队，而在表的后端进行插入，即入队。

举一个生活中常见的例子，我们经常会遇到排队办事，先来的排在前边先办理，后来的排在后边，不允许插队。先进先出，这就是典型的队列。

队列的实现

队列的概念很容易理解，操作也比较简单，很容易掌握。

跟栈一样，队列也能用数组和链表来实现，用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。

下面我们先来看一下用数组的实现方式。

public class ArrayQueue {
 private String[] items;
 private int n = 0;
 private int head = 0;
 private int tail = 0;
 public ArrayQueue(int n){
 items = new String[n];
 this.n = n;
 }
 public boolean Enqueue(String item){
 if(tail == n){
 return false;
 } 

 items[tail++] = item;
 return true;
 }
 public String Dequeue(){
 if(head == tail){
 return null;
 }
 String item = items[head++];
 return item;
 }
}

队列的数组实现比栈的实现稍微复杂一点点，队列需要两个指针，一个指向队头的 head 指针，一个指向队尾的 tail 指针。同样老办法，我们用画图来更清楚的了解一下这个过程。

image.png

如果这个时候我们调用一次出队，那么 head 指针就指向 1 的位置，并把 0 的位置的元素移除出队。如图。

image.png

如果这个时候插入一个新的元素，那么 tail 指针就指向 5 的位置，然后把新的元素放到 4 的位置。

image.png

我们通过图可以看到，这种实现方法有一个缺点，那就是随着我们不断的入队操作，等到 tail 指向最后一位的时候就没有办法接受新的元素入队了，即使前边有空闲的空间没有元素。所以我们来优化一下我们的代码，当 tail 等于数组的长度 n 的时候，这个时候如果再有新的元素入队，我们就看数组前边是不是有空闲的空间，如果有我们就把队列的元素整体向前移动几个单位。

public class ArrayQueue {
 private String[] items;
 private int n = 0;
 private int head = 0;
 private int tail = 0;
 public ArrayQueue(int n){
 items = new String[n];
 this.n = n;
 }
 public boolean Enqueue(String item){
 if(tail == n){
 if(head == 0){
 return false;
 }
 for (int i = head; i<tail> items[i-head] = items[I];
 }
 tail -= head;
 head = 0;
 }
 items[tail++] = item;
 return true;
 }
 public String Dequeue(){
 if(head == tail){
 return null;
 }
 String item = items[head++];
 return item;
 }
}
/<tail>

老办法，画图来展示这一过程。

image.png

这样就不会有空间的浪费了，但是还有个问题就是数组不能动态扩展，数组满了之后就不能再入队新的元素了，我们来再来修改一下让数组支持动态扩展。当数组满了的时候我们重新申请一个新的数组，长度为原数组的两倍，然后把原数组的元素移到新数组里，然后再进行入队操作。

public class ArrayQueue {
 private String[] items;
 private int n = 0;
 private int head = 0;
 private int tail = 0;
 private String[] newItems;
 public ArrayQueue(int n){
 items = new String[n];
 this.n = n;
 }
 public boolean Enqueue(String item){
 if(tail == n){
 if(head == 0){
 newItems = new String[2*n];
 for (int i=0;i<tail> newItems[i] = items[I];
 }
 items = newItems;
 }else {
 for (int i = head; i < tail; i++) {
 items[i - head] = items[I];
 }
 tail -= head;
 head = 0;
 }
 }
 items[tail++] = item;
 return true;
 }
 public String Dequeue(){
 if(head == tail){
 return null;
 } 

 String item = items[head++];
 return item;
 }
}
/<tail>

同样，上图。

image.png

还有一种特殊的数组实现是循环队列，当 tail == n 的时候我们不迁移数组的元素，而是去看数组下标为 0 的位置为不为空，如果为空的话我们直接入队新的元素，tail 就等于 1 。我们来看一下代码实现。

public class CycleArrayQueue {
 private String[] items;
 private int n;
 private int head = 0;
 private int tail = 0;
 public CycleArrayQueue(int n){
 items = new String[n];
 this.n = n;
 }
 public boolean Enqueue(String item){
 //数组满了
 if((tail+1)%n == head)
 return false;
 items[tail] = item;
 tail = (tail+1)%n;
 return true;
 }
 public String Dequeue(){
 if(head == tail) return null;
 String str = items[head];
 head = (head+1)%n;
 return str;
 }
}

下边我们来看一下队列的链表实现，同样我们需要两个指针，head 指向链表第一个结点，tail 指向链表最后一个结点。入队时 tail->next=new_node，tail=tail->next。出队时 head=head->next。

public class ListNodeQueue {
 private ListNode head;
 private ListNode tail;
 public void Enqueue(String val){
 ListNode node = new ListNode(val, null);
 if(tail == null){
 head = node;
 tail = node;
 }else {
 tail.next = node;
 tail = tail.next;
 }
 }
 public String Dequeue(){
 if(head == null){
 return null; 

 }
 String string = head.val;
 head = head.next;
 if(head == null){
 tail = null;
 }
 return string;
 }
 class ListNode{
 private String val;
 private ListNode next;
 public ListNode(String x, ListNode next) {
 val = x;
 this.next = next;
 }
 public String GetValue() {
 return val;
 }
 }
}

队列的应用

前边将的都是一些基本的理论知识，那队列在实际的项目中都在什么情况下使用呢？阻塞队列和并发队列应用的比较广泛。

• 阻塞队列
• 阻塞队列实际就是在队列的基础上加上了阻塞操作，当队列为空时，出队操作就会被阻塞，因为队列里没有数据，直到队列里有数据之后才能返回；当队列满的时候，入队操作就会被阻塞，直到队列中有空闲的空间时再执行入队操作。
• 我们可以用阻塞队列很容易的实现一个”生产者-消费者“模型，这样我们可以有效的控制生产和消费的速度。当生产者生产的过快时，队列很快就满了，这个时候生产者就阻塞等待，直到消费者消费了，生产者才会被唤醒继续生产。反之消费者消费过快时也同样被阻塞。不仅如此，我们还可以通过调整生产者和消费者的个数，来实现生产和消费的供需平衡。
• 并发队列
• 在多线程应用中，多个线程同时操作队列，就会存在线程安全问题，处理这个问题的队列我们称为并发队列。最简答的方法就是在入队和出队的时候加锁，保证同时只有一个线程执行队列的入队或出队，但是这样以来就会大大降低线程的并发度。
• 我们可以用上边提到的数组实现的循环队列来解决这个问题，利用 CAS 的原子操作，可以实现非常高效的并发队列。因此，循环队列比链式队列应用的更为广泛。