亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

Adslv · 更新于 2020-07-30

1. 前言

棧和隊列是 Java 數據結構中比較簡單但又非常重要的類型，我們需要了解棧和隊列的存儲原理以及各自的特點，熟悉他們各自的常用操作。

2. 后進先出

周末陪孩子玩新買的玩具槍，看到彈夾我樂了，這不就是一個棧容器嗎！兒子問我什么是棧，我反問兒子，你裝彈的順序和子彈打出去的順序有沒有關聯或規律呢？兒子想了一會說，最先裝進去的子彈要等到最后才能被發射出去，而第一發子彈是最后一個裝進去的！

（圖片來源于網絡，版權歸原作者所有）

正像槍的彈夾一樣，棧表示的是一個后進先出的對象，也叫堆棧。無需百度，直接打開 java.util.Stack 源碼還能看到 Java 為此定義了一個專屬單詞 LIFO ，其實就是 last-in-first-out 的縮寫。
細心的小伙伴還會從源碼中發現 Stack 其實是繼承自 Vector ，上一節我們介紹了數組， Vector 就是可實現自動增長的對象數組，它支持線程的同步。所以我們可以發現，棧的本質也是數組。數據從棧頂壓入，操作的時候先從棧頂取出。

3. 棧的常用操作

java.util.Stack 中對棧的操作其實只有五個，也非常簡單，我們還是用玩具彈夾為例，結合動圖來看。
圖片描述

創建一個棧只需要 new Stack () 來在內存中開辟一塊連續的默認容量為 10 的空間。添加元素我們稱之為壓入 push () , 取出元素我們使用 pop () , 查看棧頂元素我們可以使用 peek () , 此外我們還可以使用 empty () 來判斷當前棧是否為空棧。

//聲明一個棧對象，并向內壓入三個元素
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

圖片描述
堆棧類非常簡單，但請不要忽視父類 Vector 中有很多方法，感興趣的小伙伴可以去看源碼，后面我們也會介紹 Vector。
圖片描述

4. 隊列的定義和特點

我們還是從源碼中去尋找隊列的官方定義，跟棧一樣簡單的一句話：order elements in a FIFO (first-in-first-out) manner. 翻譯成中文就是 “先來后到”。數據從隊列的一端進入，從另一端取出。先到先得在我們生活中最常見的例子就是排隊了。

5. 隊列的常用操作

隊列的常用操作也非常簡單，我們可以看源碼中對 Queue 類中六個方法的介紹。

  • add () ：增加一個元素，如果隊列已滿，則拋出一個 IIIegaISlabEepeplian 異常；
  • remove () ：移除并返回隊列頭部的元素，如果隊列為空，則拋出一個 NoSuchElementException 異常；
  • element () ：返回隊列頭部的元素，如果隊列為空，則拋出一個 NoSuchElementException 異常；
  • offer () ：添加一個元素并返回 true，如果隊列已滿，則返回 false；
  • poll () ：返問并移除隊列頭部的元素，如果隊列為空，則返回 null；
  • peek () ：返回隊列頭部的元素，如果隊列為空，則返回 null；
//聲明一個隊列
Queue queue = new LinkedList();
//先向隊列中添加五個元素
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
//移除并返回隊列頭部的元素
System.out.println(queue.remove());//輸出：1
//返回隊列頭部的元素
System.out.println(queue.element());//輸出：2
//添加一個元素并返回true，如果隊列已滿則返回false
System.out.println(queue.offer(6));//輸出：true
//返回隊列頭部的元素
System.out.println(queue.peek());//輸出：2
//返問并移除隊列頭部的元素
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

但是我們創建 Queue 的時候會發現直接實例化會報錯，因為它是 interface 接口，實例化的時候可以用 LinkedList，LinkedList 繼承自 Deque，Deque 繼承自 Queue。

6. 棧和隊列的對比

通過這一節的學習我們知道了棧和隊列都是線性表，區別在于棧限定只能在表的一端（棧頂）進行插入和刪除操作，隊列限定只能在表的一端進行插入，在另一端進行刪除。
圖片描述

7. 棧和隊列的應用場景

棧和隊列在我們自己的開發工作中使用是相對比較少的，但是對它們的實際應用卻隨處可見：

  • 我們的開發工具會對括號 “（” 關閉進行匹配校驗，就是在輸入左括號 “（” 時將其壓入棧內，在輸入右括號 “）” 時從棧中取出并進行匹配校驗
  • 我們在進行一系列操作后想要撤回上一步操作，也是從我們的操作記錄棧中取出了之前操作的歷史記錄
  • 關于迷宮的解法也用到了棧，用于在使用 “窮舉解法” 時記錄前面的嘗試記錄
  • 隊列因為可以完美模擬排隊場景，因此在餐廳叫號程序、銀行醫院的排隊系統中都會用到隊列結構。

8. 小結

通過學習我們知道了棧和隊列都是線性數據結構，棧的特點是后進先出，常用的操作有壓入 push ()、查詢 peek () 和取出 pop () 等；隊列的特點是先進先出，常用的操作有添加 add ()、查詢 element () 和 peek ()、從隊列頭部取出 poll () 以及移除 remove () 等。我們要熟練掌握常用的操作和方法，結合實際應用場景，充分利用好它們各自的特點。