先进先出的数据结构——队列
一、什么是队列
队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，队列是一种操作受限制的线性表。
进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素，在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。
因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
队列分为：
- 单向队列（Queue）：只能在一端插入数据，另一端删除数据。
- 双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。
队列的实现有两种方式：数组实现和链表实现，其中用数组实现的队列有两种：一种是顺序队列，另一种是循环队列。
二、队列的存储结构
用数组实现，初始化一个队列长度为6，队列有两个标记，一个队头的位置head，一个队尾的位置tail，初始都指向数组下标为0的位置
在插入元素时，tail标记+1，比如入队三个元素，依次为A，B，C（注意是有顺序的），则当前队列存储如图
当前head为0，tail为3，接下来进行出队操作，此处将A元素出队，则head+1，此时队列的存储情况如图
- 通过tail-head获得队列中元素的个数
- 当tail==head时，此时队列为空
- 当tail等于数组长度时，此时将无法出入元素，那么队列是否已经满呢？未必！因为head和tail在入队和出队操作中只增不减，因此head和tail都会最终指向队列之外的存储位置，此时虽然数组为空，但也无法将元素入队。
上溢：当队列中无法插入元素时，称之为上溢；
假上溢：在顺序队列中，数组还有空间（不一定全空）但无法入队称之为假上溢；
真上溢：如果head为0，tail指向数组之外，即数组真满了，称之为真上溢；
下溢：如果空队中执行出队操作，此时队列中无元素，称之为下溢
如何解决“假上溢”的问题呢？此时引入循环队列。出现假上溢时，此时数组还有空闲的位置，将tail从新指向数组的0索引处即可
如果继续入队E和F，则队列的存储结构如图：
通常而言，在对head和tail加1时，为了方便采用对数组长度取余操作。另外由于顺序队列存在“假上溢”的现象，所以一般用循环队列实现。
在采用循环队列实现的过程中，当队列满队时，tail等于head，而当队列空时，tail也等于head，为了区分两种状态，一般规定循环队列的长度为数组长度-1，即有一个位置不放元素，此时head==tail时为空队，而当head==(tail+1)%数组长度，说明对满。
三、队列的实现
- 数组实现
public class ArrayQueue {
private final Object[] queue; //声明一个数组
private int head;
private int tail;
/**
* 初始化队列
* @param capacity 队列长度
*/
public ArrayQueue(int capacity){
this.queue = new Object[capacity];
}
/**
* 入队
* @param o 入队元素
* @return 入队成功与否
*/
public boolean put(Object o){
if(head == (tail+1)%queue.length){
//说明队满
return false;
}
queue[tail] = o;
tail = (tail+1)%queue.length; //tail标记后移一位
return true;
}
/**
* 返回队首元素，但不出队
*/
public Object peak() {
if(head==tail){
//队空
return null;
}
return queue[head];
}
/**
* 出队
*/
public Object pull(){
if(head==tail){
return null;
}
Object item = queue[head];
queue[head] = null;
return item;
}
/**
* 判断是否为空
*/
public boolean isEmpty(){
return head == tail;
}
/**
* 判断是否为满
*/
public boolean isFull(){
return head == (tail+1)%queue.length;
}
/**
* 获取队列中的元素个数
*/
public int getsize(){
if(tail>=head){
return tail-head;
}else{
return (tail+queue.length)-head;
}
}
}- 链表实现
public class LinkQueue<T> {
//链的数据结构
private class Node{
public T data;
public Node next;
//无参构造函数
public Node(){}
public Node(T data,Node next){
this.data=data;
this.next=next;
}
}
//队列头指针
private Node front;
//队列尾指针
private Node rear;
//队列长度
private int size=0;
public LinkQueue(){
Node n=new Node(null,null);
n.next=null;
front=rear=n;
}
/**
* 队列入队算法
*/
public void enqueue(T data){
//创建一个节点
Node s=new Node(data,null);
//将队尾指针指向新加入的节点，将s节点插入队尾
rear.next=s;
rear=s;
size++;
}
/**
* 队列出队算法
*/
public T dequeue(){
if(rear==front){
try {
throw new Exception("堆栈为空");
} catch (Exception e) {
e.printStackTrace();
}
return null;
}else{
//暂存队头元素
Node p=front.next;
T x=p.data;
//将队头元素所在节点摘链
front.next=p.next;
//判断出队列长度是否为1
if(p.next==null)
rear=front;
//删除节点
p=null;
size--;
return x;
}
}
/**
* 队列长队
*/
public int size(){
return size;
}
/**
* 判断队列是否为空
*/
public boolean isEmpty(){
return size==0;
}
}三、循环队列
这种头尾相接的顺序存储结构称为循环队列（circular queue）。
循环队列中需要注意的几个重要问题：
①队空的判定条件，队空的条件是front=rear；
②队满的判定条件，（rear+1）%QueueSize=front。QueueSize为队列初始空间大小。
public class CircleQueue {
private Object[] array;
private int capacity;//队列容量
private int count;//队列中元素的个数
private int front;
private int rear;
public CircleQueue(int capacity){
this.capacity = capacity;
array = new Object[capacity];
count = 0;
front = 0;
rear = 0;
}
//入队
public boolean append(Object data){
boolean ret = (array != null) && (capacity > 0);
if(ret){
array[rear] = data;
rear = (rear + 1) % capacity;
count++;
if(count > capacity){
count = capacity;
}
}
return ret;
}
//出队
public Object retrieve(){
Object data = null;
if((array != null) && (capacity > 0) && (count > 0)){
data = array[front];
array[front] = null;
front = (front + 1) % capacity;
count--;
}
return data;
}
//获取队列中元素的个数
public int getCount(){
return count;
}
//获取队列的容量
public int getCapacity(){
return capacity;
}
//查看队头的数据，只查看，不删除。
public Object getHead(){
Object ret = null;
if(array != null && capacity > 0 && count > 0){
ret = array[front];
}
return ret;
}
public boolean isEmpty(){
return count == 0;
}
//清空队列中的元素
public void clear(){
array = null;
array = new Object[capacity];
count = 0;
front = 0;
rear = 0;
}
public void destroy(){
array = null;
count = 0;
front = 0;
rear = 0;
}
}四、队列的应用场景
队列先入先出的特点，使得其应用非常广泛，比如队列作为“缓冲区”，可以解决计算机和外设速度不匹配的问题，FIFO的特点保证了数据传输的顺序；除此之外队列在后面树的层序遍历中也有应用，FIFO的特点保证了处理顺序不会出错。