爲什麼ArrayList沒有實現隊列？

也許這很愚蠢，但我必須知道答案。我抓着頭看着它的源代碼，並沒有看到爲什麼作者實現QueueLinkedList，但決定不要這樣做與ArrayList相同，而是他們創建了單獨的類ArrayDeque。爲什麼ArrayList沒有實現隊列？

2017-01-15 ieXcept

的interface Queue要求add將項添加到Queue和remove的端部從Queue的開始需要的元件。

（僞碼）

Queue<String> q = ... 
q.add("A") 
q.add("B") 
q.add("C") 
//q is now [A,B,C] 
String a = q.remove() 
// a is A and q is [B, C]

現在;與ArrayList，remove操作將O(n) - 我會想象API設計者認爲這種性能是不可接受的。

remove是O(n)，因爲它需要重新索引整個列表 - 現在B是0和C現在1。 LinkedList沒有這個問題，因爲它使用鏈表數據結構;它只是刪除頭節點並將該節點的子節點設置爲新頭節點。

ArrayDeque是一個不同的設計，以支持O(1) - 因此它不是List。

2017-01-15 19:48:22

最有可能的，因爲它不會是一個Queue非常高性能的，因爲增加了（當然，從在Queue的情況下刪除）開始爲O(N)操作，而不是O(1)。另一方面，ArrayDeque是不同的設計，因爲它不是List，因此不需要提供隨機訪問。

2017-01-15 19:47:08 Kayaman

'ArrayList'早於'Queue'多年和多個版本。一個人不只是因爲一個新的接口存在而簡單地擴展一個類型的契約。特別是當它這樣做有疑問時。 OTID的LinkedList是值得的。 –

@LewBloch這不完全正確。有很多老的類已經被修改，以實現一個更新的界面，這是很有意義的。使用'ArrayList'作爲隊列是可能的，但它不是很聰明。 – Kayaman

是的，就像我剛纔提到的'LinkedList'一樣。 –

回答