一：概述
????關于隊列的操作嫂伞，我們這里主要實現(xiàn)入隊孔厉，出隊，判斷空隊列和清空隊列等操作帖努，聲明隊列接口Queue（隊列抽象數(shù)據(jù)類型）如下：
public interface Queue<T> {
//隊列長度
int size();
//隊列是否為空
boolean isEmpty();
//入隊
boolean enqueue(T data);
//返回隊列頭
T peek();
//出隊
T dequeue();
}
二：順序循環(huán)隊列
????所以，對于循環(huán)隊列來說款慨，front不一定小于rear儒飒，這樣設計的好處很明顯，能夠循環(huán)利用存儲單元檩奠。
????上面的方法解決了空間浪費的問題约素，但是考慮的還不夠全面；80入隊后笆凌，這根"水管"的頭和尾都被堵住了，那么如果還想入隊怎么辦士葫？辦法總是有的乞而，這個時候就要考慮擴容了；那么什么時候擴容呢慢显？真的要等到所有位置都填充了數(shù)據(jù)才開始擴容嗎爪模？并不是的欠啤，如上圖所示，隊列中還有個空位屋灌，但是明顯無法入隊了洁段；這時候如果可能的話，就要擴容了共郭；另外祠丝，如果真的還可以入隊，那么front和rear就勢必相等了除嘹；需要注意的是写半，空隊列的front和rear也是相等的；當然尉咕，我們通過設置標記位來判斷到底是空隊列還是滿隊列叠蝇，不過一個更好的方案是預留一個位置，當隊列還剩一個位置沒有數(shù)據(jù)填充時年缎，就認為該隊列是滿的悔捶，例如上圖的隊列，雖然1號位置是空的单芜，但是我們還是認為該隊列已經(jīng)滿了蜕该，不宜再入隊了。
????綜上可知缓溅，隊列的front和rear的取值范圍應該是0 - size-1蛇损；需要注意的是，隊里中的元素坛怪，除了隊頭和隊尾外淤齐，其他元素之間的位置是相連的，在上圖中袜匿，不存在2和4號位有數(shù)據(jù)更啄，而3號位卻空出來的場景，所以有如下的約定：
????1.front是隊頭元素的下標居灯；rear指向下一個入隊的元素存儲的位置的下標
????2.當front == rear時祭务，此隊列是空隊列
????3.入隊改變rear的指向，出隊改變front的指向怪嫌，size是指隊列的長度(不是容量)
????4.約定滿隊列的條件是front == (rear + 1) % size义锥；此時，隊列中還有一個空的位置岩灭，主要是方便區(qū)分空隊列和滿隊列拌倍；如上圖中，rear == 1，front == 2柱恤，(1 + 1) % 5 == 2数初。
????下面就通過數(shù)組來實現(xiàn)一個簡單的隊列：
public class SeqQueue<T> implements Queue<T> {
//默認容量，必要的時候可以擴容
private static final int DEFAULT_SIZE = 10;
//存儲數(shù)據(jù)的數(shù)組
private T elementData[];
//隊頭和隊尾指針
private int front,rear;
//隊列長度
private int size;
@SuppressWarnings("unchecked")
public SeqQueue() {
elementData = (T[]) new Object[DEFAULT_SIZE];
front = rear = 0;
}
//隊列長度梗顺，直接返回size好了
@Override
public int size() {
return size;
}
//按照上面的約定泡孩，front == rear時為空隊列
@Override
public boolean isEmpty() {
return front == rear;
}
//入隊
@Override
public boolean enqueue(T data) {
//如果隊列滿了，那么擴容寺谤，隊列滿的條件上面解釋過
if(this.front == (this.rear + 1) % this.elementData.length) {
ensureCapacity(elementData.length*2+1);
}
//將數(shù)據(jù)存入rear指向的位置
elementData[this.rear] = data;
//更新rear指向下一個空元素的位置仑鸥，當rear指向最后一個位置時，
//(this.rear + 1) % elementData.length就等于0矗漾，也就是
//說锈候，此時rear指向了隊頭，只有這樣做敞贡，才能做到存儲單元的復用
this.rear = (this.rear + 1) % elementData.length;
//長度+1泵琳，沒毛病
size ++;
return true;
}
//獲取隊頭元素，直接返回數(shù)組指定的數(shù)據(jù)即可誊役，簡單
@Override
public T peek() {
return elementData[front];
}
//出隊
@Override
public T dequeue() {
//獲取頭元素获列，最終返回的也是他
T tmp = this.elementData[front];
//將front指向下一個元素，需要注意的是蛔垢，原來的頭元素并沒有置空
//因為front已經(jīng)指向下一個元素击孩，原來的頭元素的位置雖然還有數(shù)據(jù)
//但是他已經(jīng)沒有意義了，下次入隊的時候鹏漆，就會把這個元素的數(shù)據(jù)
//更新巩梢，在這里置空操作是非必要的，這跟上圖的操作是不太一樣的
this.front = (this.front + 1) % this.elementData.length;
//長度-1艺玲，沒毛病
size --;
return tmp;
}
//擴容括蝠，思路很簡單，就是重新創(chuàng)建一個數(shù)組饭聚，
//然后將原來的數(shù)據(jù)按照秩序拷到新的數(shù)組
@SuppressWarnings("unchecked")
private void ensureCapacity(int capacity) {
//臨時存儲老的數(shù)據(jù)
T[] old = elementData;
//創(chuàng)建新的數(shù)組
elementData = (T[]) new Object[capacity];
int j = 0;
//這里的循環(huán)條件有點不一樣忌警，首先肯定是從隊頭開始拷貝，
//這個隊頭的索引不一定是0秒梳，只能取this.front法绵；循環(huán)結
//束的條件是i != this.rear，也就是從隊頭開始拷酪碘，一
//到隊尾結束朋譬；自增的條件是i = (i + 1) % old.length，
//這里千萬不能用i++兴垦，因為有時候rear小于front此熬，如果i++
//那么永遠也到不了隊尾，同時還會拋出數(shù)組越界的異常，而
//(i + 1) % old.length能夠保證當rear小于front的時候犀忱，
//i能及時，正確的回到正確的位置扶关，也就是上圖中的"水管"的左邊
//這樣才能保證新隊列的順序能和老隊列的順序保持一致阴汇，很重要
for(int i = this.front ; i != this.rear ; i = (i + 1) % old.length) {
elementData[j++] = old[i];
}
this.front = 0 ;
this.rear = j;
}
//清空隊列
public void clear(){
//循環(huán)的條件和上面擴容的條件一樣
for(int i = this.front ; i != this.rear ; i = (i + 1) % elementData.length){
//把每個元素置空
elementData[i] = null;
}
this.front = this.rear = -1;
size = 0;
}
}
????上面就是順序隊列的實現(xiàn)方式，稍稍有點繞节槐，總體還是比較簡單的搀庶。
三：鏈式隊列
????從圖中可以看出食茎，鏈式隊列的入隊和出隊蒂破，只需要改變尾節(jié)點和頭結點的指向即可，而且還不存在順序鏈表中的假溢出問題别渔，下面代碼實現(xiàn)他：
public class LinkQueue<T> implements Queue<T> {
//對于鏈式隊列來說附迷，頭尾節(jié)點是必不可少的
private Node<T> front,rear;
//鏈表的長度
private int size;
//鏈式隊列沒有容量的限制，但是最好是給它設置一個上線
private static final int MAX_SIZE = 128;
public LinkQueue() {
this.front = this.rear = null;
}
//簡單哎媚，不解釋
@Override
public int size() {
return size;
}
//頭尾節(jié)點均為空代表空隊列
@Override
public boolean isEmpty() {
return this.front == null && this.rear == null;
}
@Override
public boolean add(T data) {
if(size >= MAX_SIZE) {
return false;
}
Node<T> node = new Node<T>(data);
//空隊列插入
if(this.front == null) {
this.front = node;
//非空隊列插入
}else {
this.rear.next = node;
}
//新插入的節(jié)點就是尾節(jié)點
this.rear = node;
size ++;
return true;
}
//返回頭節(jié)點的數(shù)據(jù)喇伯，簡單
@Override
public T peek() {
return this.front == null ? null : this.front.data;
}
@Override
public T poll() {
//空隊列返回空
if(isEmpty()) {
return null;
//非空隊列返回頭節(jié)點，然后將頭結點指向他的后繼節(jié)點
}else {
T tmp = this.front.data;
this.front = this.front.next;
//如果隊列只有一個節(jié)點抄伍，那么出隊后就成了空隊列艘刚，所以隊尾也要置空
if(this.front == null) {
this.rear = null;
}
size --;
return tmp;
}
}
//清除隊列
public void clear() {
//頭尾節(jié)點都不存在了，鏈表也就不存在了截珍，這樣隊列就沒了
this.front = this.rear = null;
this.size = 0;
}
@SuppressWarnings("hiding")
class Node<T> {
public T data;
public Node<T> next;
public Node() {
}
public Node(T data) {
this.data = data;
}
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}
}
????以上就是兩種隊列的設計和實現(xiàn)攀甚，比較簡單；相對來說岗喉，鏈式隊列更簡單秋度，出隊和入隊比順序循環(huán)隊列簡潔，而且沒有假溢出的問題钱床。
摘自：https://blog.csdn.net/javazejian/article/details/53375004#%E9%98%9F%E5%88%97%E7%9A%84%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B
