3.隊(duì)列(Queue) ——————本質(zhì)為："線性表"
隊(duì)列是一種運(yùn)算受限制的線性表馅巷，元素的插入（入隊(duì)）在表的一端(表尾, rear)進(jìn)行卷雕，刪除（出對）則在另一端(表頭, front)進(jìn)行。
允許插入的一端稱為表尾(rear)敢茁，允許刪除的一端稱為表頭(front)
隊(duì)列的主要操作：
① 初始化
② 入隊(duì)：插入
③ 出隊(duì)：刪除
④ 獲取隊(duì)頭 —— 不刪除元素
⑤ 求長度：隊(duì)列元素個(gè)數(shù)
⑥ 判空
⑦ 正序遍歷
⑧ 銷毀
表示形式：
㈠邏輯結(jié)構(gòu):
q = (a1, a2, ... , an), a1為隊(duì)頭元素篡帕，an為隊(duì)尾元素
┌───┬───┬───┬───┬───┐
出隊(duì)<—— │a1 │a2 │a3 │...│an │ <——入隊(duì)
└───┴───┴───┴───┴───┘
↑ ↑
隊(duì)頭 隊(duì)尾
特點(diǎn)：'先進(jìn)先出(FIFO, first in first out)',因此又被稱之先進(jìn)先出的線性表
㈡'物理存儲結(jié)構(gòu)'
(1) 順序存儲結(jié)構(gòu)：順序隊(duì)列
其實(shí)質(zhì)為：線性表的順序表
順序隊(duì)列用一維數(shù)組實(shí)現(xiàn)，還需設(shè)置兩個(gè)指針 front 和 rear 分別指示隊(duì)列的隊(duì)頭元素和隊(duì)尾元素的'下一個(gè)位置'次询。
注意：其實(shí)這里荧恍，將隊(duì)頭指針front指向隊(duì)列元素的前一個(gè)空的位置處，而rear指針指向隊(duì)列最后一個(gè)元素的位置處屯吊，也是可行的送巡。
注意：
1.這種單向的順序隊(duì)列極易造成假溢出(即隊(duì)列中明明還有存儲單元，就是不能插入新的元素)
解決辦法：
(1) 每次出隊(duì)一個(gè)元素后盒卸，將整個(gè)隊(duì)列元素均向隊(duì)頭方向移動一個(gè)單元骗爆，即始終保證整個(gè)隊(duì)的隊(duì)頭指示器始終在數(shù)組的第一個(gè)存儲單元處。時(shí)間復(fù)雜度：O(n)
(2) 將順序隊(duì)列的存儲結(jié)構(gòu)改造成頭尾相連(只是表現(xiàn)在邏輯上的)的圓環(huán)蔽介，當(dāng)隊(duì)尾指示器rear到達(dá)數(shù)組的上限(數(shù)組最大下標(biāo)處)時(shí), 如果還有數(shù)據(jù)元素需要入隊(duì)且數(shù)組的第 0 個(gè)存儲單元空閑時(shí)淮腾，就可以讓rear指向數(shù)組的0存儲位置。同理屉佳，對頭front指示器達(dá)到數(shù)組的上限(數(shù)組最大下標(biāo)處)時(shí),若果還有元素要出隊(duì)時(shí)谷朝，就將front指向數(shù)組的0端。這樣武花，就可以將隊(duì)列中空閑的空間利用上圆凰。
方法分析：第一種解決方法會造成系統(tǒng)額外的開銷，不是最佳解決辦法体箕。故采用第二種方法专钉。
- 在循環(huán)隊(duì)列中挑童，判斷隊(duì)列是空還是滿是個(gè)需要重點(diǎn)考慮的問題。單純的依靠 front==rear并不能判斷隊(duì)列空間是空還滿(因?yàn)榭栈驖M時(shí)跃须，均有這個(gè)關(guān)系)站叼。
解決辦法：
(1)設(shè)定一個(gè)輔助標(biāo)識位：flag，初始為0,當(dāng)入隊(duì)一個(gè)元素就加1菇民，出隊(duì)一個(gè)元素就減1尽楔。最后結(jié)合flag是否為大于零的數(shù)和front==rear來判斷當(dāng)前循環(huán)隊(duì)列是滿的還是空
(2)第二種方式就是，在循環(huán)隊(duì)列中少用一個(gè)存儲單元第练。因此阔馋，rear和front只相差一個(gè)位置。但是請注意：由于是循環(huán)結(jié)構(gòu)娇掏，所以這個(gè)差1,有可能是相差整整一圈呕寝，因此，隊(duì)滿的條件：(rear + 1) % queueArray.length == front
方法分析：第一種解決辦法要多設(shè)定一個(gè)參數(shù)婴梧，還要一直對這個(gè)參數(shù)執(zhí)行運(yùn)算下梢，這樣會增加一部分系統(tǒng)開銷。因此塞蹭，采用第二中解決辦法怔球。
順序循環(huán)隊(duì)列為"空"的條件：front == rear == 0
為"滿"的條件：(rear + 1) % queueArray.length == front
隊(duì)列的長度：(rear - front + queueArray.length) % queueArray.length
注意：取模的目的是為了整合rear和front大小為一個(gè)問題
'代碼描述'（順序循環(huán)結(jié)構(gòu)隊(duì)列）：
public class sequenceQueue<T> {
private final int maxSize = 10; //默認(rèn)是隊(duì)列容量
private T queueArray[]; //實(shí)現(xiàn)隊(duì)列的數(shù)組
private int front; //隊(duì)頭指示器
private rear; //隊(duì)尾指示器,指向隊(duì)尾元素的下一個(gè)位置（始終保持所指的位置是空內(nèi)容，即未被利用的那個(gè)存儲單元）
/**
* 順序隊(duì)列初始化
*/
//采用默認(rèn)容量初始化順序隊(duì)列
public sequenceQueue() {
front = rear = 0;
queueArray = (T[])new Object[maxSize];
}
//采用指定容量初始化順序隊(duì)列
public sequenceQueue(int n) {
front = rear = 0;
queueArray = (T[])new Object[n];
}
/**
* 入隊(duì)操作：插入
*/
public void enQueue(T obj) {
//隊(duì)列是否已滿,若滿了則需要擴(kuò)容
if ((rear + 1) % queueArray.length == front) {
//擴(kuò)容
T[] p = (T[])new Object[queueArray.length * 2];
//復(fù)制原數(shù)組中的數(shù)據(jù)至新的數(shù)組中
//表明rear指示器現(xiàn)在數(shù)組的末尾處浮还，front指示器在數(shù)組的0下標(biāo)處
if (rear == ((T[])queueArray).length - 1) {
for (int i = 1; i <= rear; i++) {
p[i] = queueArray[i];
}
}else {
/**
* 表明rear指示器在數(shù)組的其他位置處竟坛，則將隊(duì)列分為兩部分：
* (1) front位置到數(shù)組末尾
* (2) 0存儲單元到rear指針器處
* 因此,得分段復(fù)制
*/
int i, j = 1;
// 復(fù)制front到末尾這段的數(shù)據(jù)
for (i = front + 1; i < queueArray.length; i++, j++) {
p[j] = queueArray[i];
}
// 復(fù)制從0存儲單元到rear指示器處的數(shù)據(jù)
// 注意：這里將queueArray[0]位置的數(shù)據(jù)(為0)也復(fù)制到新的數(shù)組中，表明
// 新數(shù)組的扔是以0存儲單元作為"判滿"的輔助單位
for (i = 0; i < rear; i++, j++) {
p[j] = queueArray[i];
}
front = 0; // 將front調(diào)整到數(shù)組頭部位置
rear = queueArray.length - 1; //將rear調(diào)整到數(shù)組中含有數(shù)據(jù)的尾部的位置
}
queueArray = p;
}
/**
* 執(zhí)行插入數(shù)據(jù)的過程,
* 若將rear指向隊(duì)尾元素的下一個(gè)位置時(shí)钧舌，front在隊(duì)頭元素處
* rear = (rear + 1) % queueArray.length;
* queueArray[rear] = obj; //因?yàn)閞ear指針在隊(duì)尾元素的下一個(gè)位置處担汤，因此先放元素，再移動指針
*/
//這個(gè)表示rear指向隊(duì)尾的元素洼冻，注意和上面這段代碼的區(qū)別
//取模是為了防止rear指針越界崭歧，
rear = (rear + 1) % queueArray.length; //因?yàn)閞ear指針在隊(duì)尾元素處，因此先移動rear指針撞牢，再放元素
queueArray[rear] = obj;
}
//出隊(duì)操作：刪除
public T deQueue() {
//判空
if (isEmpty()) {
System.out.println("順序隊(duì)列為空率碾，不能進(jìn)行出隊(duì)操作");
return null;
}
/**
* 進(jìn)行出隊(duì)的操作過程
* 由于：front在隊(duì)頭元素的前一個(gè)位置處，所以屋彪，插入數(shù)據(jù)時(shí)所宰，要先移動指針，后放數(shù)據(jù)
*/
front = (front + 1) % queueArray.length; //front指針取模也是為了front防止越界
return queueArray[front];
}
//獲取操作：返回隊(duì)頭的元素畜挥，不刪除該元素
public T getTop() {
//判空
if (isEmpty()) {
System.out.println("順序隊(duì)列為空仔粥，不能進(jìn)行獲取隊(duì)頭元素的操作");
return null;
}
return queueArray[(front + 1) % queueArray.length];
}
//求長度
public int size() {
return (rear - front + queueArray.length) % queueArray.length;
}
//判空
public boolean isEmpty() {
return front == rear;
}
//正向遍歷
public void nextOrder() {
System.out.print("[");
int j = front;
for (int i = 1; i <= size(); i++) {
j = (j + 1) % queueArray.length;
if (j == rear) {
System.out.print(queueArray[j]);
}else {
System.out.print(queueArray[j] + ", ");
}
}
System.out.println("]");
}
//銷毀
public void clear() {
front = rear = 0;
}
}
(2) 鏈?zhǔn)酱鎯Y(jié)構(gòu)：鏈隊(duì)列
用鏈表實(shí)現(xiàn)的隊(duì)列稱為鏈隊(duì)列,
其實(shí)質(zhì)是：線性表的單鏈表（只是在'頭刪尾插'而已）
注意：
1.鏈隊(duì)列的長度是不固定的，因此不存在假溢出的問題，故用一般的(非循環(huán))隊(duì)列即可躯泰。
2.同線性表的單鏈表一樣谭羔，為了操作方便，在鏈隊(duì)列中添加一個(gè)頭結(jié)點(diǎn)麦向，并令頭指針(front)指向頭結(jié)點(diǎn)瘟裸。(在鏈棧中沒有使用頭結(jié)點(diǎn))
鏈隊(duì)列為'空'的條件(front和rear均指向頭結(jié)點(diǎn))：front.next == null
'代碼描述'(鏈隊(duì)列):
public class LinkQueue<T> {
private Node<T> front, rear; //這里的Node和前面的鏈表的Node是一樣的
private int length; //記錄隊(duì)列元素的個(gè)數(shù)
//1.初始化鏈隊(duì)列
public LinkQueue() {
length = 0;
front = rear = new Node<T>(null); //初始時(shí)，front和rear均指向表頭結(jié)點(diǎn)
}
//2.入隊(duì)：插入（不用考慮隊(duì)滿的情況诵竭，也就沒有擴(kuò)容的現(xiàn)象）
public void enQueue(T obj) {
rear.next = new Node<T>(obj, null);
rear = rear.next; //將rear指針移動到新的隊(duì)尾結(jié)點(diǎn)處话告。
length ++; //增加一個(gè)元素個(gè)數(shù)
}
//3.出隊(duì)：刪除(刪除的是頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)，即第一個(gè)結(jié)點(diǎn))
public T deQueue() {
//判空
if (isEmpty()) {
System.out.println("鏈隊(duì)列為空秀撇，不可以進(jìn)行出棧操作");
return null;
}
//出棧過程
Node<T> p = front.next; //輔助結(jié)點(diǎn)
front.next= p.next; //由于表頭（頭結(jié)點(diǎn)）的"位置"固定不動，因此向族，只能變動第一個(gè)結(jié)點(diǎn)呵燕。
length --;
/**
* 這部分是不是多余呢？不是多余的件相，當(dāng)隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí)再扭，出隊(duì)后，此時(shí)隊(duì)列為空了夜矗。
* 就要將rear指針指向頭結(jié)點(diǎn)泛范，即front的位置處
*/
if (front.next == null) {
front = rear;
}
return p.data;
}
//4.獲取：返回隊(duì)頭元素
public T getHead() {
//判空
if (isEmpty()) {
System.out.println("鏈隊(duì)列為空紊撕，不可以進(jìn)行獲取隊(duì)頭元素的操作");
return null;
}
//獲取隊(duì)頭元素的過程
return front.next.data;
}
//5.求長度
public int size() {
return length;
}
//6. 判空
public boolean isEmpty() {
return front.next == null;
}
//7.正向遍歷
public void nextOrder() {
System.out.print("[");
Node<T> p = front.next;
while (p != null) {
if (p.next == null) {
System.out.print(p.data);
}else {
System.out.print(p.data + ", ");
}
p = p.next;
}
System.out.println("]");
}
//8.銷毀
public void clear() {
length = 0;
front.next = rear.next = null;
}
}
循環(huán)隊(duì)列和鏈隊(duì)列的比較：
它們的基本操作都是：O(1)
循環(huán)隊(duì)列長：度固定罢荡，所以會存在浪費(fèi)空間的情況。但是对扶，在頻繁出入隊(duì)的時(shí)候区赵，不需要申
請、釋放結(jié)點(diǎn)浪南，因此笼才，空間開銷少點(diǎn)
鏈隊(duì)列：長度靈活可變，但會頻繁的申請络凿、釋放結(jié)點(diǎn)骡送，造成一頂?shù)南到y(tǒng)開銷
總結(jié)：長度確定時(shí)，用循環(huán)鏈表
長度不可測時(shí)絮记，選擇鏈隊(duì)列
典型應(yīng)用：鍵盤輸入各種字符的過程
