我們一起聊聊隊(duì)列和棧
一、定義和概念
順序隊(duì)列
隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。
圖片
隊(duì)列特點(diǎn)：先進(jìn)先出
三種溢出現(xiàn)象：
（1）下溢：隊(duì)列為空，出隊(duì)，正常?？捎米鳁l件邏輯判斷
（2）真上溢：隊(duì)列滿，入隊(duì)，異常，需要避免
（3）假上溢：隊(duì)列實(shí)際不滿，但由于對(duì)頭指針只增不減，空間無法重復(fù)利用，導(dǎo)致虛滿，無法正常入隊(duì)，可通過循環(huán)隊(duì)列解決
循環(huán)隊(duì)列
循環(huán)隊(duì)列就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列結(jié)構(gòu)中，當(dāng)存儲(chǔ)空間的最后一個(gè)位置已被使用而再要進(jìn)入隊(duì)運(yùn)算時(shí)，只需要存儲(chǔ)空間的第一個(gè)位置空閑，便可將元素加入到第一個(gè)位置，即將存儲(chǔ)空間的第一個(gè)位置作為隊(duì)尾。
在循環(huán)隊(duì)列中，當(dāng)隊(duì)列為空時(shí)，有 frnotallow=rear，而當(dāng)所有隊(duì)列空間全占滿時(shí)，也有 frnotallow=rear。為了區(qū)別這兩種情況，規(guī)定循環(huán)隊(duì)列最多只能有 MaxSize-1 個(gè)隊(duì)列元素，當(dāng)循環(huán)隊(duì)列中只剩下一個(gè)空存儲(chǔ)單元時(shí)，隊(duì)列就已經(jīng)滿了。因此，隊(duì)列判空的條件是 frnotallow=rear，而隊(duì)列判滿的條件是 front = (rear+1)%MaxSize
圖片
（1）a,b,c,d,e 入隊(duì)
（2）a,b 出隊(duì)，對(duì)頭指針指向 c
（3）假設(shè)隊(duì)列 maxSize=6，插入 e 之后就出現(xiàn)假上溢，這時(shí)候 f 要入隊(duì)，由于 a，b 元素已經(jīng)出隊(duì)位置空閑，所以 f 插入存儲(chǔ)空間的第一個(gè)位置，將 f 設(shè)置為隊(duì)尾。依次循環(huán)能避免假上溢的情況出現(xiàn)，從而將隊(duì)列循環(huán)裝滿。
空對(duì)接判斷條件：front = rear
滿隊(duì)列判斷條件：(rear + 1) % MAXSIZE = front
為什么判斷隊(duì)列是否滿的條件是 front = (rear+1)%MaxSize？
（1）正常情況判滿條件是 rear+1=front
（2）有一種特殊情況，隊(duì)列滿了之后 rear+1=0，所以當(dāng)隊(duì)列滿足了一個(gè) maxSize 的輪回的時(shí)候會(huì)就歸 0，所以此處需要根據(jù) maxSize 取余，即 (rear+1)%MaxSize = front
棧
棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表。它按照后進(jìn)先出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來）。棧具有記憶作用，對(duì)棧的插入與刪除操作中，不需要改變棧底指針。
棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。插入一般稱為進(jìn)棧（PUSH），刪除則稱為出棧/退棧（POP）。棧也稱為先進(jìn)后出表。
圖片
?？盏臈l件：因?yàn)橹羔槒?0 開始，所以棧滿的條件為 top == -1
棧滿的條件：因?yàn)橹羔槒?0 開始，所以棧滿的條件為 top==maxsize-1
溢出現(xiàn)象：
（1）下溢：棧為空，出棧，正常?？捎米鳁l件邏輯判斷
（2）真上溢：棧滿，入隊(duì)，異常，需要避免，不存在跟隊(duì)列類似的假上溢的情況。
堆棧的基本特點(diǎn)：
（1）先入后出，后入先出。
（2）除頭尾節(jié)點(diǎn)之外，每個(gè)元素有一個(gè)前驅(qū)，一個(gè)后繼。
二、算法實(shí)現(xiàn)
循環(huán)隊(duì)列
定義數(shù)組存儲(chǔ)元素，定義隊(duì)頭指針和隊(duì)尾指針
1、數(shù)組大小定義為元素個(gè)數(shù) +1
2、隊(duì)列判空：front == rear
3、隊(duì)列判滿：front == (rear + 1) % maxSize
4、入隊(duì)：當(dāng)前隊(duì)尾指針指向的空間存儲(chǔ)元素，隊(duì)尾指針 +1
5、出隊(duì)：返回當(dāng)前隊(duì)頭元素，隊(duì)頭指針 +1
import java.util.Arrays;
import java.util.stream.Collectors;
public class CircleQueue {
/**
* 數(shù)組長(zhǎng)度
*/
private int maxSize;
/**
* 隊(duì)頭指針
*/
private int front;
/**
* 隊(duì)尾指針
*/
private int rear;
private String[] queue;
/**
* 初始化循環(huán)隊(duì)列
* @param objSize 元素個(gè)數(shù)
*/
public CircleQueue(int objSize) {
// 循環(huán)隊(duì)列為了區(qū)分空隊(duì)列和滿隊(duì)列，所以多預(yù)留一個(gè)空元素空間，這里的maxSize比元素個(gè)數(shù)多1
this.maxSize = objSize + 1;
this.front = 0;
this.rear = 0;
this.queue = new String[this.maxSize];
}
/**
* 隊(duì)列是否空
* @return
*/
public boolean isEmpty() {
return front == rear;
}
/**
* 隊(duì)列是否滿
* @return
*/
public boolean isFull() {
return front == (rear+1) % maxSize;
}
/**
* 入隊(duì)
* @param a 入隊(duì)元素
*/
public void add(String a) {
if (isFull()) {
System.out.println("隊(duì)列滿");
return;
}
queue[rear%maxSize] = a;
rear = (rear+1)%maxSize;
}
/**
* 出隊(duì)
* @return 出隊(duì)元素
*/
public String remove() {
if (isEmpty()) {
System.out.println("隊(duì)列空");
return null;
}
String a = queue[front%maxSize];
queue[front%maxSize] = null;
front = (front+1)%maxSize;
return a;
}
public static void main(String[] args) {
// 模擬一個(gè)4個(gè)元素大小隊(duì)列的入隊(duì)出隊(duì)情況
// a,b,c入隊(duì)；【正常，元素a,b,c，frnotallow=0，rear=3】
// a出隊(duì)；【正常，元素b,c，frnotallow=1，rear=3】
// d,e入隊(duì)；【正常，元素b,c,d,e frnotallow=1，rear=0】// 循環(huán)隊(duì)列
// f入隊(duì)；【異常，隊(duì)列滿】
// b,c,d,e出隊(duì)【正常，隊(duì)列空 frnotallow=0，rear=0】
CircleQueue circleQueue = new CircleQueue(4);
System.out.print("a,b,c入隊(duì):");
circleQueue.add("a");
circleQueue.add("b");
circleQueue.add("c");
System.out.println(Arrays.stream(circleQueue.queue).collect(Collectors.toList()) + "frnotallow=" + circleQueue.front + "；rear" + circleQueue.rear);
System.out.print("a出隊(duì):");
String remove1 = circleQueue.remove();
System.out.println(remove1 + "；" + Arrays.stream(circleQueue.queue).collect(Collectors.toList()) + "frnotallow=" + circleQueue.front + "；rear" + circleQueue.rear);
System.out.print("d,e入隊(duì):");
circleQueue.add("d");
circleQueue.add("e");
System.out.println(Arrays.stream(circleQueue.queue).collect(Collectors.toList()) + "frnotallow=" + circleQueue.front + "；rear" + circleQueue.rear);
System.out.print("f入隊(duì):");
circleQueue.add("f");
System.out.println(Arrays.stream(circleQueue.queue).collect(Collectors.toList()) + "frnotallow=" + circleQueue.front + "；rear" + circleQueue.rear);
System.out.print("b,c,d,e出隊(duì):");
String remove2 = circleQueue.remove();
String remove3 = circleQueue.remove();
String remove4 = circleQueue.remove();
String remove5 = circleQueue.remove();
System.out.println(remove2+","+remove3+","+remove4+","+remove5+","+"；" + Arrays.stream(circleQueue.queue).collect(Collectors.toList()) + "frnotallow=" + circleQueue.front + "rear" + circleQueue.rear);
}
}執(zhí)行結(jié)果：
圖片
順序棧
定義數(shù)組存儲(chǔ)元素，定義棧頂指針
1、數(shù)組大小定義為元素個(gè)數(shù)
2、棧判空：top == -1
3、棧判滿：top == maxSize -1
4、入棧：當(dāng)前棧頂指針 +1，棧頂指針指向的空間存儲(chǔ)元素
5、出棧：返回當(dāng)前棧頂指針指向的元素，棧頂指針 -1
package cn.gov.zcy.announcement;
import java.util.Arrays;
import java.util.stream.Collectors;
public class Stack {
// 數(shù)組長(zhǎng)度
private int maxSize;
/**
* 棧頂指針
*/
private int top;
private String[] stack;
/**
* 初始化棧
* @param objSize 元素個(gè)數(shù)
*/
public Stack(int objSize) {
maxSize = objSize;
top = -1;
stack = new String[maxSize];
}
/**
* 判斷棧是否空
* @return
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 判斷棧是否滿
* @return
*/
public boolean isFull() {
return top == maxSize-1;
}
/**
* 入棧
* @param a 入棧元素
*/
public void push(String a) {
if (isFull()) {
System.out.println("棧滿");
return;
}
top = top + 1;
stack[top] = a;
}
/**
* 出棧
* @return 出棧元素
*/
public String pop() {
if (isEmpty()) {
System.out.println("?？?);
return null;
}
String a = stack[top];
top = top - 1;
return a;
}
public static void main(String[] args) {
// 模擬一個(gè)4個(gè)元素大小棧的入棧和出棧的情況
// a,b,c,d入棧【正常，元素a,b,c,d，top=3】
// e入棧【異常，棧滿】
// d,c,b,a出棧【正常，出棧順序d,c,b,a，top=-1】
// 出?！井惓＃瑮？铡? Stack test = new Stack(4);
System.out.print("a,b,c,d入棧：");
test.push("a");
test.push("b");
test.push("c");
test.push("d");
System.out.println(Arrays.stream(test.stack).collect(Collectors.toList()) + "；top=" + test.top);
System.out.print("e入棧：");
test.push("e");
System.out.println(Arrays.stream(test.stack).collect(Collectors.toList()) + "；top=" + test.top);
System.out.print("d,c,b,a出棧：");
String pop1 = test.pop();
String pop2 = test.pop();
String pop3 = test.pop();
String pop4 = test.pop();
System.out.println(pop1 + "," + pop2 + "," + pop3 + "," + pop4 + "," + "；top=" + test.top);
System.out.print("空棧出棧：");
String pop5 = test.pop();
System.out.println(pop5 + "；top=" + test.top);
}
}執(zhí)行結(jié)果：
圖片
隊(duì)列思想應(yīng)用實(shí)踐
應(yīng)用背景
一批已經(jīng)發(fā)布的公告數(shù)據(jù)需要推送，且推送時(shí)間點(diǎn)需要滿足發(fā)布后 10 分鐘
圖片
隊(duì)列實(shí)現(xiàn)介質(zhì)：數(shù)據(jù)庫表
隊(duì)列實(shí)現(xiàn)先進(jìn)先出：按照修改時(shí)間正序排序
入隊(duì)：插入數(shù)據(jù)庫表
出隊(duì)：刪除數(shù)據(jù)庫表
重新入隊(duì)：更新修改時(shí)間，通過重新入隊(duì)可以解決已經(jīng)被處理過并且處理異常的數(shù)據(jù)可以輪到后續(xù)的定時(shí)任務(wù)中處理
總結(jié)
隊(duì)列和棧的定義和概念都比較簡(jiǎn)單，但隊(duì)列和棧的思想都經(jīng)過包裝了各種介質(zhì)被廣泛應(yīng)用。
