首先讓我們先簡單地來認識一下隊列：
隊列介紹
隊列一種受限線性表润脸，只允許在一段進行插入，在另一端進行刪除倔矾。它還有個好搭檔叫“椡”柱锹，經(jīng)常被一起提起，棧是一種先進后出的數(shù)據(jù)結(jié)構(gòu)丰包，而隊列則是一種先進先出的數(shù)據(jù)結(jié)構(gòu)禁熏，在英文中被稱作First in,First out。故隊列又經(jīng)常被叫作FIFO表烫沙。
隊列分類
順序隊列匹层、循環(huán)隊列。
隊列的實現(xiàn)原理
先看順序隊列锌蓄，一個頭指針升筏，一個尾指針。進隊尾指針后移瘸爽，出隊時頭指針后移您访。并且出隊之后，所有元素可以前移（也可以不前移）剪决。
元素不前移機制的操作示意圖：
假溢出現(xiàn)象：
當我們采用順序隊列的時候灵汪，如果采用“元素不前移”的機制，當尾指針到達上邊界時柑潦，就會認為隊列已滿享言，但此時低端空間由于出隊可能還有空閑空間。如圖所示：
假溢出的解決辦法：
這便是循環(huán)隊列渗鬼。即當尾指針到達上邊界時览露，可以回到下邊界的位置，從而繼續(xù)進行入隊操作譬胎。
隊列的判空差牛、判滿
那么問題來了，我們使用了循環(huán)隊列之后堰乔，又該如何判斷隊列是空偏化，還是滿呢？使用以下的方法：
①判空：front=rear
②問題：想想镐侯，出隊時頭指針后移侦讨，遇尾指針相遇時隊空。入隊時苟翻，尾指針后移韵卤，與頭指針相遇時隊滿，也是front=read呀袜瞬！但這個公式判空已經(jīng)用了怜俐，那么判滿就不能使用front=rear了。
③判滿：使用公式：(rear+1)%size=front邓尤。判滿時拍鲤，隊列實際上并真正的滿贴谎，我們實際上是浪費了一個數(shù)組空間。還差一個滿時就認為已經(jīng)它滿了季稳。如圖（已滿隊列）：
java代碼實現(xiàn)
public class CirQueue {
private Object[] objs;
private int front = 0;// 頭指針
private int rear = 0;// 尾指針
private int size;// 空間大小
private int length = 0;
// 初始化
public CirQueue(int size) {
this.size = size;
objs = new Object[size];
}
// 計算長度（即隊列元素個數(shù)）
public int getLength() {
return length;
}
// 判空
public boolean isEmpty() {
if (front == rear) {
return true;
}
return false;
}
// 判滿
public boolean isFull() {
if ((rear + 1) % size == front) {
return true;
}
return false;
}
// 入隊
public boolean enQueue(Object n) {
if (isFull()) {
return false;
}
rear = (rear + 1) % size;// 體現(xiàn)循環(huán)
objs[rear] = n;
length++;
return true;
}
// 出隊
public Object deQueue() {
Object n = null;
if (!isEmpty()) {
front = (front + 1) % size;// 體現(xiàn)循環(huán)
n = objs[front];
objs[front] = null;
length--;
}
return n;
}
// 輸出
public void show() {
for (Object obj : objs) {
if (obj == null) {
System.out.print("空 ");
} else {
System.out.print(obj.toString() + " ");
}
}
System.out.println("");
}
}
//java入口
public class Main {
public static void main(String[]args){
CirQueue queue=new CirQueue(5);
queue.show();
System.out.println("是否為空:"+queue.isEmpty());
System.out.println("初始長度:"+queue.getLength());
queue.enQueue(1);
queue.enQueue(2);
queue.enQueue(3);
queue.enQueue(4);
queue.show();
System.out.println("是否已滿:"+queue.isFull());
System.out.println("現(xiàn)有長度:"+queue.getLength());
queue.enQueue(6);
queue.deQueue();
queue.deQueue();
queue.enQueue(5);
queue.enQueue(6);
queue.show();
System.out.println("是否已滿:"+queue.isFull());
System.out.println("現(xiàn)有長度:"+queue.getLength());
queue.deQueue();
queue.deQueue();
queue.deQueue();
queue.deQueue();
queue.show();
System.out.println("是否為空:"+queue.isEmpty());
System.out.println("現(xiàn)有長度:"+queue.getLength());
}
}
運行結(jié)果：
