Adslv ·1. 前言
棧和隊(duì)列是 Java 數(shù)據(jù)結(jié)構(gòu)中比較簡(jiǎn)單但又非常重要的類型，我們需要了解棧和隊(duì)列的存儲(chǔ)原理以及各自的特點(diǎn)，熟悉他們各自的常用操作。
2. 后進(jìn)先出
周末陪孩子玩新買的玩具槍，看到彈夾我樂(lè)了，這不就是一個(gè)棧容器嗎！兒子問(wèn)我什么是棧，我反問(wèn)兒子，你裝彈的順序和子彈打出去的順序有沒(méi)有關(guān)聯(lián)或規(guī)律呢？?jī)鹤酉肓艘粫?huì)說(shuō)，最先裝進(jìn)去的子彈要等到最后才能被發(fā)射出去，而第一發(fā)子彈是最后一個(gè)裝進(jìn)去的！
正像槍的彈夾一樣，棧表示的是一個(gè)后進(jìn)先出的對(duì)象，也叫堆棧。無(wú)需百度，直接打開(kāi) java.util.Stack 源碼還能看到 Java 為此定義了一個(gè)專屬單詞 LIFO ，其實(shí)就是 last-in-first-out 的縮寫。
細(xì)心的小伙伴還會(huì)從源碼中發(fā)現(xiàn) Stack 其實(shí)是繼承自 Vector ，上一節(jié)我們介紹了數(shù)組， Vector 就是可實(shí)現(xiàn)自動(dòng)增長(zhǎng)的對(duì)象數(shù)組，它支持線程的同步。所以我們可以發(fā)現(xiàn)，棧的本質(zhì)也是數(shù)組。數(shù)據(jù)從棧頂壓入，操作的時(shí)候先從棧頂取出。
3. 棧的常用操作
java.util.Stack 中對(duì)棧的操作其實(shí)只有五個(gè)，也非常簡(jiǎn)單，我們還是用玩具彈夾為例，結(jié)合動(dòng)圖來(lái)看。
創(chuàng)建一個(gè)棧只需要 new Stack () 來(lái)在內(nèi)存中開(kāi)辟一塊連續(xù)的默認(rèn)容量為 10 的空間。添加元素我們稱之為壓入 push () , 取出元素我們使用 pop () , 查看棧頂元素我們可以使用 peek () , 此外我們還可以使用 empty () 來(lái)判斷當(dāng)前棧是否為空棧。
//聲明一個(gè)棧對(duì)象，并向內(nèi)壓入三個(gè)元素
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
//判斷是否為空棧
System.out.println(stack.isEmpty());//輸出：false
//使用peek()方法查詢棧頂元素，使用pop()方法取出棧頂元素
System.out.println(stack.peek());//輸出：3
System.out.println(stack.pop());//輸出：3
System.out.println(stack.peek());//輸出：2
System.out.println(stack.pop());//輸出：2
System.out.println(stack.peek());//輸出：1
System.out.println(stack.pop());//輸出：1
System.out.println(stack.isEmpty());//輸出：true
堆棧類非常簡(jiǎn)單，但請(qǐng)不要忽視父類 Vector 中有很多方法，感興趣的小伙伴可以去看源碼，后面我們也會(huì)介紹 Vector。
4. 隊(duì)列的定義和特點(diǎn)
我們還是從源碼中去尋找隊(duì)列的官方定義，跟棧一樣簡(jiǎn)單的一句話：order elements in a FIFO (first-in-first-out) manner. 翻譯成中文就是 “先來(lái)后到”。數(shù)據(jù)從隊(duì)列的一端進(jìn)入，從另一端取出。先到先得在我們生活中最常見(jiàn)的例子就是排隊(duì)了。
5. 隊(duì)列的常用操作
隊(duì)列的常用操作也非常簡(jiǎn)單，我們可以看源碼中對(duì) Queue 類中六個(gè)方法的介紹。
- add () ：增加一個(gè)元素，如果隊(duì)列已滿，則拋出一個(gè) IIIegaISlabEepeplian 異常；
- remove () ：移除并返回隊(duì)列頭部的元素，如果隊(duì)列為空，則拋出一個(gè) NoSuchElementException 異常；
- element () ：返回隊(duì)列頭部的元素，如果隊(duì)列為空，則拋出一個(gè) NoSuchElementException 異常；
- offer () ：添加一個(gè)元素并返回 true，如果隊(duì)列已滿，則返回 false；
- poll () ：返問(wèn)并移除隊(duì)列頭部的元素，如果隊(duì)列為空，則返回 null；
- peek () ：返回隊(duì)列頭部的元素，如果隊(duì)列為空，則返回 null；
//聲明一個(gè)隊(duì)列
Queue queue = new LinkedList();
//先向隊(duì)列中添加五個(gè)元素
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
//移除并返回隊(duì)列頭部的元素
System.out.println(queue.remove());//輸出：1
//返回隊(duì)列頭部的元素
System.out.println(queue.element());//輸出：2
//添加一個(gè)元素并返回true，如果隊(duì)列已滿則返回false
System.out.println(queue.offer(6));//輸出：true
//返回隊(duì)列頭部的元素
System.out.println(queue.peek());//輸出：2
//返問(wèn)并移除隊(duì)列頭部的元素
System.out.println(queue.poll());//輸出：2
System.out.println(queue.poll());//輸出：3
System.out.println(queue.poll());//輸出：4
System.out.println(queue.poll());//輸出：5
System.out.println(queue.poll());//輸出：6
但是我們創(chuàng)建 Queue 的時(shí)候會(huì)發(fā)現(xiàn)直接實(shí)例化會(huì)報(bào)錯(cuò)，因?yàn)樗?interface 接口，實(shí)例化的時(shí)候可以用 LinkedList，LinkedList 繼承自 Deque，Deque 繼承自 Queue。
6. 棧和隊(duì)列的對(duì)比
通過(guò)這一節(jié)的學(xué)習(xí)我們知道了棧和隊(duì)列都是線性表，區(qū)別在于棧限定只能在表的一端（棧頂）進(jìn)行插入和刪除操作，隊(duì)列限定只能在表的一端進(jìn)行插入，在另一端進(jìn)行刪除。
7. 棧和隊(duì)列的應(yīng)用場(chǎng)景
棧和隊(duì)列在我們自己的開(kāi)發(fā)工作中使用是相對(duì)比較少的，但是對(duì)它們的實(shí)際應(yīng)用卻隨處可見(jiàn)：
- 我們的開(kāi)發(fā)工具會(huì)對(duì)括號(hào) “（” 關(guān)閉進(jìn)行匹配校驗(yàn)，就是在輸入左括號(hào) “（” 時(shí)將其壓入棧內(nèi)，在輸入右括號(hào) “）” 時(shí)從棧中取出并進(jìn)行匹配校驗(yàn)
- 我們?cè)谶M(jìn)行一系列操作后想要撤回上一步操作，也是從我們的操作記錄棧中取出了之前操作的歷史記錄
- 關(guān)于迷宮的解法也用到了棧，用于在使用 “窮舉解法” 時(shí)記錄前面的嘗試記錄
- 隊(duì)列因?yàn)榭梢酝昝滥M排隊(duì)場(chǎng)景，因此在餐廳叫號(hào)程序、銀行醫(yī)院的排隊(duì)系統(tǒng)中都會(huì)用到隊(duì)列結(jié)構(gòu)。
8. 小結(jié)
通過(guò)學(xué)習(xí)我們知道了棧和隊(duì)列都是線性數(shù)據(jù)結(jié)構(gòu)，棧的特點(diǎn)是后進(jìn)先出，常用的操作有壓入 push ()、查詢 peek () 和取出 pop () 等；隊(duì)列的特點(diǎn)是先進(jìn)先出，常用的操作有添加 add ()、查詢 element () 和 peek ()、從隊(duì)列頭部取出 poll () 以及移除 remove () 等。我們要熟練掌握常用的操作和方法，結(jié)合實(shí)際應(yīng)用場(chǎng)景，充分利用好它們各自的特點(diǎn)。
2025 imooc.com All Rights Reserved |