多面的LinkedList：可作隊列，棧，雙端隊列

為什麼LinkedList能當做棧，隊列，雙端隊列？

​

筆記：

1. 為什麼LinkedList能當做棧，隊列，雙端隊列？LinkedList是一個繼承于AbstractSequentialList的雙向連結清單。其中的每個對象包含資料的同時還包含指向連結清單中前一個與後一個元素的引用。LinkedList同時實作了List接口和Deque對口，也就是收它既可以看作一個順序容器，又可以看作一個隊列（Queue），同時又可以看作一個棧（stack）

2. 接一：LinkedList 實作 List 接口，能進行隊列操作。

   LinkedList 實作 Deque 接口，即能将LinkedList當作雙端隊列使用。

LinkedList如何作為棧、隊列、雙端隊列使用

1. 具體API看上面的連結
2. LinkedList能當做棧時的API？
3. LinkedList能當做隊列時的API？
4. LinkedList能當做雙端隊列時的API？

List接口長什麼樣？

1. List接口長什麼樣？這得先看Collection 接口。因為Collection接口是 List / Set / Queue 接口的父接口，List / Set / Queue 的實作類中很多的操作方法其實還是調用Collection類定義的方法。
2. 看看Collection在LinkedList繼承體系中的位置

3. 

    Collection 接口其中方法可以分為以下幾類：

   資料操作類方法：add/addAll/remove/removeAll/clear/retainAll/iterator

   判斷類方法：contains/containsAll/equals/hashcode/isEmpty/size

   所有繼承 Collection 接口的集合都可以用 Collection 中的方法進行元素操作，而具體的集合類有根據其特性增加了一些其特有的方法。

4. List接口在Collection接口的基礎上拓展了一些方法，增加了一些自己獨有的方法。具體看上面的連結。

Deque接口什麼樣？

1. Deque接口：

   queue是隊列，隻能一頭進，另一頭出。如果把條件放松一下，允許兩頭都進，兩頭都出，這種隊列叫雙端隊列（Double Ended Queue），學名Deque。Java集合提供了接口Deque來實作一個雙端隊列，它的功能是：

• 既可以添加到隊尾，也可以添加到隊首；
• 既可以從隊首擷取，又可以從隊尾擷取。

1. Queue和Deque出隊入隊的差別？

   

   對于添加元素到隊尾的操作，

   Queue

   提供了

   add()

   /

   offer()

   方法，而

   Deque

   addLast()

   offerLast()

   方法。添

   加元素到對首、取隊尾元素的操作在

   Queue

   中不存在，在

   Deque

   中由

   addFirst()

   removeLast()

   等方法提供。

   注意到

   Deque

   接口實際上擴充自

   Queue

為什麼使用Deque而不使用Stack構造棧

1. Stack和Collection的關系如下圖：

2. 

   為什麼使用Deque而不使用Stack構造棧？可以看出Stack是繼承自Vector，而Vector有效率問題已經被棄用了，是以繼承Vector的Stack也存在效率問題，故不推薦使用。       

為什麼java不推薦使用Vector？

1. Vector有什麼效率問題？為什麼會有效率問題？
2. 以後補充