一、隊列結(jié)構(gòu)
1、基礎(chǔ)概念
隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。
2、特點描述
隊列是一個有序列表，可以用數(shù)組或是鏈表來實現(xiàn)，遵循先進先出的原則。即:先進入隊列的數(shù)據(jù)，會先取出；后進入隊列的數(shù)據(jù)，要后取出；即FIFO原則。
入隊列示意圖：
出隊列示意圖：
通過上述兩張圖解，不難發(fā)現(xiàn)隊列結(jié)構(gòu)的一些特點：
- 先進入的數(shù)據(jù)先出去；
- 數(shù)據(jù)從隊尾進入，從隊首出去；
- 基于數(shù)組描述隊列下標變更頻繁；
- 出隊列算法可以基于容器大小取模；
隊列結(jié)構(gòu)的核心是對容器內(nèi)是否空、是否滿標志的判斷算法，即容器為空不可再取，容器已滿無法再存；該算法結(jié)構(gòu)在倉儲領(lǐng)域的適應(yīng)非常廣泛。
3、消息隊列
消息隊列就是基于數(shù)據(jù)結(jié)構(gòu)中的“先進先出”策略實現(xiàn)的，將消息以排隊的方式放入隊列中，然后出隊列被消費：
有時候某類消息消費需要有順序控制，即可以對消息中的公共ID做取模處理，即把某類消息都置于一個隊列中即可。
4、API使用案例
LinkedList類實現(xiàn)Queue隊列接口，因此可以基于LinkedList模擬隊列效果。
import JAVA.util.LinkedList;
import java.util.Queue;
public class M01_Queue {
public static void main(String[] args) {
// 入隊列
Queue<String> queue = new LinkedList<>();
queue.add("head") ;
queue.add("middle") ;
queue.add("tail") ;
// 當隊列出數(shù)據(jù)之后，size是不斷變化的
int queueSize = queue.size() ;
int loop = 0 ;
// 根據(jù)隊列大小，不斷出隊列
while (loop < queueSize) {
System.out.println(queue.poll());
System.out.println(queue);
loop ++ ;
}
}
}
二、棧結(jié)構(gòu)
1、基礎(chǔ)概念
棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧(push)，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧(pop)，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
2、特點描述
棧是一個先入后出的有序列表，添加和刪除只能在棧頂端(Top)操作，另一端為固定的一端，稱為棧底(Bottom)。
入棧示意圖：
出棧示意圖：
通過上述兩張圖解，棧結(jié)構(gòu)的一些特點如下：
- 進棧出棧都要通過棧頂端操作；
- 進出棧都不移動棧底指針；
- 進出棧都要移動棧頂指針；
基于棧的定義可知，最先放入棧中元素在棧底，最后放入的元素在棧頂，從棧容器中而刪除元素剛好相反，最后放入的元素最先刪除，最先放入的元素最后刪除。
3、遞歸應(yīng)用
棧在Java編程中的常見應(yīng)用，(1)子程序的調(diào)用：在跳往子程序前，會將下個指令的地址存到堆棧中，直到子程序執(zhí)行完后再將地址取出，退回到原來的程序中;(2)處理遞歸調(diào)用：和子程序的調(diào)用類似，除了存儲下一個指令的地址外，也要將參數(shù)、區(qū)域變量等數(shù)據(jù)存入堆棧中。
4、API使用案例
Stack棧API是Vector的一個子類，它實現(xiàn)了一個標準的后進先出的棧，堆棧只定義了默認構(gòu)造函數(shù)，用來創(chuàng)建一個空棧，堆棧除了包括由Vector定義的所有方法，也定義了自己的一些方法。
import java.util.Stack;
public class M02_Stack {
public static void main(String[] args) {
// 入堆棧
Stack<String> stack = new Stack<>() ;
stack.push("First") ;
stack.push("Second") ;
stack.push("Third") ;
int stackSize = stack.size() ;
int loop = 0 ;
// 根據(jù)棧大小，不斷出棧
while (loop < stackSize) {
System.out.println(stack.pop());
System.out.println(stack);
loop ++ ;
}
}
}
