特点——先进先出：
只允许一端进行插入操作，另一端进行删除操作的 线性表
插入一段是队尾，删除的一端是队头
存储方式——顺序存储和链式存储
顺序存储
顺序存储用数组实现
假设有N个元素的一个队列，数组下标为0的一端是对头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，如果删除对头元素，后面的元素就要往前移动，这种方式性能不高
顺序队列的实现代码如下：
public class ArrayQueue {
private Array<E> data;
public ArrayQueue(){
this.data = new DynamicArray();
}
public boolean isEmpty() {
return data.isEmpty();
}
public int size() {
return data.size();
}
public void enqueue(E e) {
data.add(e);
}
public E dequeue() {
return data.remove(0);
}
public E head() {
return data.get(0);
}
@Override
public String toString() {
return "Head " + data.toString() + " Tail";
}
}
为了提高队的性能，于是出现了循环队列
循环队列
就是有两个指针，front指向队头，rear指向对尾元素的下一个位置
元素出队时front往后移动，如果到了对尾则转到头部，同理入队时rear后移，如果到了对尾则转到头部，这样通过下标front出队时，就不需要移动元素了
循环操作rear依次后移，然后再从头开始，出现rear和front相等时，队列满
注意（当队列为空时，front和rear相等 当队列为满时，front和rear也相等）
为了区分这种情况，规定数组还有一个空闲单元时，就表示队列已满
因为rear 可能在front后面，也可能循环到front前面，所以队列满的条件就变成了(rear+1)%maxsize = front ,同时队列元素个数的计算就是(rear -front+maxsize)%maxsize
循环队列的实现代码如下：
public class LoopQueue<E> {
private E[] data;
private int size;
private int tail;
private int head;
public LoopQueue(){
this(8);
}
public LoopQueue(int capcaity) {
this.data = (E[]) new Object[capcaity + 1];
this.head = 0;
this.tail = 0;
this.size = 0;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void enqueue(E e) {
if((tail + 1) % data.length == head % data.length){
resize(data.length * 2);
}
data[tail] = e;
tail = (tail + 1)% data.length;
size++;
}
public E dequeue() {
if(tail == head){
return null;
}
E e = data[head];
head = (head + 1)% data.length;
size--;
if(size == data.length / 4 && data.length / 2 != 0){
resize(data.length / 2);
}
return e;
}
public E head() {
return data[head];
}
private void resize(int newCapcaity){
E[] newData = (E[])new Object[newCapcaity + 1];
for(int i = 0 ; i < size ; i ++) {
newData[i] = data[(i + head) % data.length];
}
head = 0;
tail = size;
data = newData;
}
@Override
public String toString() {
StringBuilder sBuilder = new StringBuilder();
sBuilder.append("Head ");
for(int i = 0 ; i < size ; i ++) {
sBuilder.append(data[(i + head) % data.length]).append(",");
}
int lastIndex = sBuilder.lastIndexOf(",");
if(lastIndex != -1){
sBuilder.deleteCharAt(lastIndex);
}
sBuilder.append(" Tail");
return sBuilder.toString();
}
温馨提示：
循环队列要事先申请好空间，整个过程都不能释放，而且要有固定的长度
链式列表：
由于循环队列不够灵活，于是引入了链式存储队列，即线性表的单链表
它只能对尾进，队头出，并且规定队头指针指向链队列的头结点，对尾指针指向终端节点
当队列为空时，front和rear都指向头结点
具体实现代码如下：
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
typedef int Status;
typedef int QElemType;
//结点结构
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
//队列的链表结构
