集合中篇—棧與隊列

• 2020 年 3 月 10 日
• 筆記

1. 準備

Java的集合實現了棧與隊列，我們直接調用就可以實現功能，可是平時就見過Queue、Stack、Deque這些字眼，完全不知道怎麼回事，下面就來梳理一下他們的關係，先來看類圖（這裡簡化並只關聯了所需要提到的類或接）

• Stack類（棧），繼承了Vector線程安全類，現在不推薦使用，推薦ArrayDeque
• Queue接口（隊列），有Collection方法，而且也新增了自己的方法
• Deque接口（雙向隊列），繼承了Queue，因為是雙向隊列，所以可以實現隊列和棧的操作
• 我們之前學過的LinkedList以及ArrayDeque實現Deque接口，即可以作為隊列和棧使用

2. Queue

Queue接口不同之處在於同一個功能他有兩套方法，兩套方法區別於一套是實現返回值，另一套是拋出異常

後面講解基於拋出異常的方法

3. Deque

double ended queue，意思是雙向隊列，所以該接口多了操作方法，用於操作頭尾，下面講解部分方法，其餘自行查看

4. LinkedList

• 之前我們就學過LinkedList了，底層是雙向鏈表，想不到還支持棧和隊列，而且有了頭尾操作，實現棧和隊列就簡單了，我們比較熟悉他，所以棧和隊列就基於LinkedList來講解
• 棧和隊列用頭尾操作實現稍微想一下就會理解的，後面列出表格對照

4.1 棧

先進後出的結構，想像成羽毛球筒就行了，先放進去的羽毛球都是最後才能拿出來的

具體實現

public static void main(String[] args) {        LinkedList linkedList = new LinkedList();        linkedList.addFirst(1);      linkedList.addFirst(2);      linkedList.addFirst(3);      linkedList.addFirst(4);        linkedList.removeFirst();        //一定要用foreach方法，上篇有解釋      for(Object i : linkedList){          System.out.println(i);      }  }

3  2  1

4.2 隊列

public static void main(String[] args) {        LinkedList linkedList = new LinkedList();        linkedList.addLast(1);      linkedList.addLast(2);      linkedList.addLast(3);      linkedList.addLast(4);        linkedList.removeFirst();        //一定要用foreach方法，上篇有解釋      for(Object i : linkedList){          System.out.println(i);      }  }

2  3  4

4.3 對照表

棧

隊列