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