這篇“Java棧和隊(duì)列怎么應(yīng)用”文章的知識(shí)點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來(lái)看看這篇“Java棧和隊(duì)列怎么應(yīng)用”文章吧。
讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：空間域名、虛擬主機(jī)、營(yíng)銷軟件、網(wǎng)站建設(shè)、高明網(wǎng)站維護(hù)、網(wǎng)站推廣。
在學(xué)習(xí)棧和隊(duì)列 之前，先了解一下什么是線性表：一次保存單個(gè)同類型的元素，多個(gè)元素之間邏輯上連續(xù)，比如數(shù)組，鏈表，字符串，棧和隊(duì)列
棧和隊(duì)列其實(shí)操作受限的線性表，數(shù)組也罷，鏈表也罷，既可以在頭部插入和刪除，也能在尾部插入和刪除，但是棧和隊(duì)列只能在一端插入，在一端刪除
只能在一端插入元素，也只能在這一端刪除元素（棧頂），可以把棧看作一個(gè)“水杯”，只能從一端添加元素，也只能從一段刪除元素，而且，先進(jìn)入水杯的水在杯底，后進(jìn)入水杯的水在杯頂，往出倒水的時(shí)候，也是倒出的杯頂?shù)乃?，棧也是一樣，先入棧的元素在棧底，后入棧的元素在棧頂，所以先入棧的元素后出，后入棧的元素先出，這也是棧的特性“先進(jìn)后出，后進(jìn)先出”Last In First Out(LIFO),取出元素和添加元素只能在棧頂。
將1 2 3 4 5，一次放入棧中
在任何一個(gè)編輯器中輸錯(cuò)一個(gè)內(nèi)容后，使用Ctrl + z就返回到了輸入的內(nèi)容；
在任何一個(gè)瀏覽器中點(diǎn)擊后退操作
都是棧的這個(gè)結(jié)構(gòu)的應(yīng)用
1.使用編輯器使用撤銷操作，一次輸入就把內(nèi)容壓入棧中，再輸入就就再壓入棧中，發(fā)現(xiàn)一次輸入錯(cuò)誤，就使用撤銷操作，把當(dāng)前棧頂?shù)腻e(cuò)誤內(nèi)容彈出，那么當(dāng)前棧頂?shù)膬?nèi)容就是上次輸入的內(nèi)容。
2.瀏覽網(wǎng)頁(yè)其實(shí)也是相同原理的，就像打開百度 -> 打開csdn -> 打開創(chuàng)作中心，也是使用棧這個(gè)結(jié)構(gòu)，先把百度網(wǎng)頁(yè)壓入棧中 ，然后csdn網(wǎng)頁(yè)壓入棧中，然后創(chuàng)作中心網(wǎng)頁(yè)壓入棧中，想要返回到csdn主頁(yè)，按下后頭箭頭，就把當(dāng)前棧頂?shù)膭?chuàng)作中心網(wǎng)頁(yè)彈出，取出csdn主頁(yè)。
程序再執(zhí)行的過(guò)程中，從A函數(shù)調(diào)用B函數(shù)，從B函數(shù)調(diào)用C函數(shù)，調(diào)用結(jié)束，返回執(zhí)行時(shí)，如何得知從哪繼續(xù)開始執(zhí)行呢，背后也是棧這個(gè)結(jié)構(gòu)
基于鏈表實(shí)現(xiàn)的棧 – 鏈?zhǔn)綏?br/>基于數(shù)組實(shí)現(xiàn)的棧 – 順序棧（使用較多）
定義一個(gè)基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的棧
//基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的順序棧public class MyStack{ //記錄當(dāng)前棧的元素個(gè)數(shù) private int size; //實(shí)際存儲(chǔ)數(shù)據(jù)的動(dòng)態(tài)數(shù)組，此時(shí)在棧中只能在數(shù)組的尾部添加和刪除元素 private List data = new ArrayList<>(); }
1.向棧中添加一個(gè)元素
只能在棧頂添加
重慶分公司
重慶分公司
/**
* 向當(dāng)前棧中添加元素 -- >壓棧操作
* @param val
*/
public void push(E val){
data.add(val);
size++;
}2.當(dāng)前從棧頂彈出一個(gè)元素
/**
* 彈出當(dāng)前棧頂元素,返回棧頂元素的值
* @return
*/
public E pop(){
if (isEmpty()){
//棧為空無(wú)法彈出
throw new NoSuchElementException("stack is empty!cannot pop!");
}
//在數(shù)組末尾刪除元素
E val = data.get(size - 1);
data.remove(size - 1);
size --;
return val;
}3.查看當(dāng)前棧頂元素，但不彈出
/**
* 查看當(dāng)前棧頂元素值，不彈出該元素
* @return
*/
public E peek(){
if (isEmpty()){
throw new NoSuchElementException("stack is empty!cannot peek!");
}
return data.get(size - 1);
}隊(duì)列：先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)i，元素只能從隊(duì)尾添加到隊(duì)列中，也只能從隊(duì)首出隊(duì)列，元素的出隊(duì)順序和入隊(duì)順序保持一致
將1 2 3 4 5依次入隊(duì)
現(xiàn)實(shí)生活中，各種各樣的“排隊(duì)”操作
基于數(shù)組實(shí)現(xiàn)的隊(duì)列 – 順序隊(duì)列
基于鏈表實(shí)現(xiàn)的隊(duì)列 – 鏈?zhǔn)疥?duì)列
出隊(duì)操作只能在隊(duì)列的頭部進(jìn)行，若采用數(shù)組實(shí)現(xiàn)的隊(duì)列，每次出隊(duì)一個(gè)元素就得搬移剩下的所有元素向前移動(dòng)一個(gè)單位，此時(shí)采用鏈表實(shí)現(xiàn)的隊(duì)列更適合隊(duì)列的結(jié)構(gòu)，刪除元素只需要?jiǎng)h除頭結(jié)點(diǎn)，添加元素在鏈表的尾部添加
public interface Queue{ //入隊(duì)操作 void offer(E val); //出隊(duì)操作 E poll(); //查看隊(duì)首元素 E peek(); boolean isEmpty();}
對(duì)于棧來(lái)說(shuō)隊(duì)列的實(shí)現(xiàn)子類是比較多的，比如
FIFO隊(duì)列
雙端隊(duì)列
循環(huán)隊(duì)列
優(yōu)先級(jí)隊(duì)列
不管哪個(gè)隊(duì)列都要實(shí)現(xiàn)
1.定義一個(gè)FIFO隊(duì)列
// An highlighted blockvar foo = 'bar';
2.向隊(duì)列中添加一個(gè)元素
public void offer(E val) {
Node node = new Node<>(val);
if (head == null){
head = tail = node;
}else{
//鏈表的尾插
tail.next = node;
tail = node;
}
size++;
} 3.從當(dāng)前隊(duì)首出隊(duì)一個(gè)元素
public E poll() {
if (isEmpty()){
throw new NoSuchElementException("queue is empty! cannot poll!");
}
//頭刪
E val = head.val;
Node node = head;
head = head.next;
node.next = node = null;
size--;
return val;
} 4.查看當(dāng)前隊(duì)列的隊(duì)首元素
public E peek() {
if (isEmpty()){
throw new NoSuchElementException("queue is empty!cannot peek!");
}
return head.val;
}1.定義：基本上都是使用固定長(zhǎng)度的數(shù)組來(lái)實(shí)現(xiàn)，數(shù)組在實(shí)現(xiàn)隊(duì)時(shí)，若從數(shù)組頭部刪除元素需要頻繁的移動(dòng)后面的元素，效率比較低；出隊(duì)和入隊(duì)操作，使用兩個(gè)引用，一個(gè)head，一個(gè)tail,添加元素在數(shù)組的尾部添加，刪除元素只需要移動(dòng)head引用指向的地址即可（邏輯刪除）
2.應(yīng)用：操作系統(tǒng)的生產(chǎn)消費(fèi)者模型，MySQL數(shù)據(jù)庫(kù)的InnoDB存儲(chǔ)引擎的redo日志
3.循環(huán)隊(duì)列就是使用長(zhǎng)度固定的數(shù)組來(lái)實(shí)現(xiàn)，數(shù)組頭部就是隊(duì)首（head），數(shù)組的尾部就是隊(duì)尾（tail），數(shù)組[head…tail)時(shí)循環(huán)隊(duì)列的有效元素
head永遠(yuǎn)指向循環(huán)隊(duì)列的第一個(gè)元素
tai永遠(yuǎn)指向循環(huán)隊(duì)列有效元素的后一個(gè)位置
此時(shí)循環(huán)隊(duì)列的有效元素就為7 9 1兩個(gè)元素
循環(huán)隊(duì)列出隊(duì)一個(gè)元素，就只用讓head引用向后移動(dòng)一個(gè)位置
此時(shí)循環(huán)隊(duì)列的有效元素就只有9 和 1 兩個(gè)元素了
再出隊(duì)一個(gè)元素，但此時(shí)head引用已經(jīng)走到末尾了，所謂循環(huán)隊(duì)列就是當(dāng)head或者tail引用走到數(shù)組末尾時(shí)，再向后移動(dòng)就是返回?cái)?shù)組頭部的操作，循環(huán)隊(duì)列最大好處就是進(jìn)行元素的刪除的時(shí)候不需要進(jìn)行數(shù)據(jù)的搬移操作，當(dāng)有新的元素添加到隊(duì)列中就會(huì)覆蓋掉原來(lái)的元素，就只需要將tail索引位置覆蓋上新的元素，再讓tail再向后移動(dòng)
當(dāng)隊(duì)列為空時(shí),head == tail
當(dāng)隊(duì)列已“滿”時(shí)，head == tail
循環(huán)隊(duì)列需要注意的關(guān)鍵點(diǎn)
1.因此當(dāng)head 和 tail相等時(shí)，沒(méi)法區(qū)分此時(shí)循環(huán)隊(duì)列已滿，還是為空，因此在循環(huán)隊(duì)列中，若(tail + 1) % n == head就認(rèn)為循環(huán)隊(duì)列已滿
此時(shí)循環(huán)隊(duì)列就已經(jīng)滿了，在循環(huán)隊(duì)列中就會(huì)浪費(fèi)一個(gè)空間，判斷隊(duì)列是否已滿
2.head和tail的移動(dòng)不能簡(jiǎn)單的 + 1，使用取模操作，取數(shù)組長(zhǎng)度
tail = (tail + 1) % n
head = (head + 1) % n
對(duì)數(shù)組長(zhǎng)度取模的本質(zhì)：
當(dāng)head和tai走到數(shù)組最后一個(gè)索引位置時(shí)，下一次要返回?cái)?shù)組頭部，就必須用 + 1對(duì)數(shù)組長(zhǎng)度取模
3.head == tail時(shí)，認(rèn)為隊(duì)列為空
1.定義一個(gè)循環(huán)隊(duì)列
//基于整形的循環(huán)隊(duì)列public class LoopQueue implements Queue{ //定長(zhǎng)數(shù)組 private Integer[] data; //指向隊(duì)首元素 int head; //指向隊(duì)尾元素的下一個(gè)元素 int tail; public LoopQueue(int size){ data = new Integer[size + 1]; }}
2.向循環(huán)隊(duì)列中添加一個(gè)元素
@Override public void offer(Integer val) {
if (isFull()){
throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer");
}
data[tail] = val;
tail = (tail + 1) % data.length;
}3.從循環(huán)隊(duì)列中出隊(duì)一個(gè)元素
@Override public Integer poll() {
if (isEmpty()){
throw new NoSuchElementException("loopQueue is empty!cannot poll!");
}
Integer val = data[head];
head = (head + 1) % data.length;
return val;
}4.查看當(dāng)前循環(huán)隊(duì)列隊(duì)首元素
@Override public Integer peek() {
if (isEmpty()){
throw new NoSuchElementException("loopQueue is empty!cannot peek!");
}
return data[head];
}5.判斷當(dāng)前循環(huán)隊(duì)列是否為空
@Override public boolean isEmpty() {
return head == tail;
}6.判斷當(dāng)前循環(huán)隊(duì)列是否已滿
public boolean isFull(){
return (tail + 1) % data.length == head;
}7.toString方法
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("front [");
//最后一個(gè)有效元素的索引
int lsatIndex = tail == 0 ? data.length - 1 : tail - 1;
for (int i = head; i != tail;) {
sb.append(data[i]);
if (i != lsatIndex){
sb.append(", ");
}
i = (i + 1) % data.length;
}
sb.append("] tail");
return sb.toString();
}雙端隊(duì)列：Deque是Queue的子接口，這個(gè)隊(duì)列既可以尾插，頭出；也可以頭插，尾出
雙端隊(duì)列的一個(gè)常用子類就是LinkedList，不管使用棧還是隊(duì)列，都可以統(tǒng)一使用雙端隊(duì)列接口
1.現(xiàn)在需要一個(gè)棧
2.現(xiàn)在需要一個(gè)隊(duì)列
以上就是關(guān)于“Java棧和隊(duì)列怎么應(yīng)用”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對(duì)大家有幫助，若想了解更多相關(guān)的知識(shí)內(nèi)容，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
