数据结构与算法系列——队列
什么是队列
队列也是一种操作受限制的线性表，只允许在表的前端进行删除，也就是出队，而在表的后端进行插入，即入队。
举一个生活中常见的例子，我们经常会遇到排队办事，先来的排在前边先办理，后来的排在后边，不允许插队。先进先出，这就是典型的队列。
队列的实现
队列的概念很容易理解，操作也比较简单，很容易掌握。
跟栈一样，队列也能用数组和链表来实现，用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。
下面我们先来看一下用数组的实现方式。
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;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;
}
}
老办法，画图来展示这一过程。
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;i++){
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;
}
}
同样，上图。
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 的原子操作，可以实现非常高效的并发队列。因此，循环队列比链式队列应用的更为广泛。
欢迎关注公众号：「努力给自己看」
公众号200x200
