Java - LinkedList push（）pop（）意味着它是一個堆棧，而不是一個隊列？

在我的數據結構類中，我瞭解到LinkedList是一個隊列。就像現實生活中的一條線一樣，進入該線的第一個人將成爲第一個離開的人。說得通。如下所示，ListedList實現了具有FIFO（先進先出）過程的Queue。Java - LinkedList push（）pop（）意味着它是一個堆棧，而不是一個隊列？

但是，如果你看一下描述的方法push(E)和pop()，他們讀如下：

推（E）

將元素推入此列表所表示的堆棧。換句話說，將該元素插入此列表的前面。

彈出（）

從此列表所表示的堆棧彈出一個元素。換句話說，刪除並返回此列表的第一個元素。

這是....不是隊列。這是一個堆棧。通過push進入LinkedList的第一個元素不能被pop訪問，直到每個元素在pop()之後添加爲止。

這是爲什麼？我得到LinkedLists既可以作爲堆棧使用（如果你只使用addFirst(E)和removeFirst()），並可以用作隊列（如果你只使用addFirst(E)和removeLast()或反之亦然），那麼爲什麼它是這樣呢？我覺得pop()應該刪除並返回最後一個元素，或者push(E)應該在LinkedList的末尾添加元素。那麼它會更有意義。

TLDR：爲什麼LinkedList的push和pop意味着它可以作爲一個堆棧時LinkedList實際實現Queue來代替。

來源

2016-09-18 Hatefiend

列表既不是堆棧也不是隊列，但它可以用作任何一個。 – chrylis

Push()和pop()是由與Stacks慣例操作（Deque，更具體地說是在這種情況下），這就是爲什麼你應該期待您的LinkedList到工作方式，當你使用這些方法。如果您希望LinkedList以Queue的方式工作（它實現Queue接口），您要使用的方法（如文檔中所述）爲add()和remove()。

See LinkedList Documentation

來源

2016-09-18 08:45:27 Sith

LinkedList是一個雙端隊列（Deque），因此你可以添加和刪除從兩端元件。它也實現List，它允許你在中間修改零件。

這並不改變它可以通過使用add/offer和poll/remove作爲隊列使用的事實。

來源

2016-09-18 08:34:20 fabian

「流行」和「推」條款是專門用於堆棧嗎？我不想永遠命名我的一個數據結構的方法'pop'，然後突然意識到'convention'應該是一個刪除第一個元素的方法。 – Hatefiend

@Hatefiend AFAIK push/pop僅用於堆棧（或類似堆棧的行爲）。 – fabian

您提到的方法（push()和pop()）來自Deque接口，該接口也由LinkedList執行。 Javadoc爲Deque指出：

線性集合，支持在兩端插入和移除元素。名稱deque是「雙端隊列」的縮寫，通常發音爲「deck」。大多數Deque實現對它們可能包含的元素的數量沒有固定限制，但是此接口支持容量限制的deques以及沒有固定大小限制的deque。

換句話說，它與普通隊列不一樣。

如果你真的想用LinkedList作爲一個隊列，你應該將變量分配給該接口：

Queue<String> queue = new LinkedList<>();

這樣做，你只能夠使用queue的，好了，排隊。除其他方法外，此接口定義了用於從隊列中添加和移除元素的add()和remove()。

來源

2016-09-18 08:36:38 Magnilex

Ohhhh我忘了你可以做'Interf x = new ClassWhoImplementsInterf（）;'。當你做'Apple x = new SuperApple（）;'時會發生什麼？（假設'SuperApple'是'Apple'的子類）在這種情況下，你只能使用'Apple'的方法，或者這種方法只適用於接口？ – Hatefiend

它基本上以類，抽象或具體的方式工作。雖然這將是一個完全不同的討論，如果你想進一步解釋，可能應該作爲一個不同的問題。 – Magnilex

你可以從類圖LinkedList既是List和一個Deque看到。

Deque接口定義了一個「雙端隊列」抽象，它可以同時作爲FIFO（即堆棧）或LIFO（即Queue）......。從javadocs：

Deques也可以用作LIFO（後進先出）堆棧。此接口應優先使用傳統的Stack類。當一個deque用作堆棧時，元素會從deque的開始處被推入並彈出。

的push和pop操作COM從Deque API的FIFO的一面。

LinkedList - push()，pop()意味着這是一個堆棧，而不是一個隊列？

從邏輯上講，這是不正確的。

你是對的，push()和pop()意味着一個堆棧。
然而，add()僅缺席和remove()不會暗示的隊列。

FIFO和LIFO功能並不相互排斥。

來源

2016-09-18 08:48:25

一個單鏈表使得一個優秀的堆棧，但只有一個非常糟糕的隊列。只有雙鏈接，雙重鏈接的列表非常適合作爲隊列。

單鏈表允許僅在頭部插入和移除O（1）（即堆棧操作）。

查找尾部元素需要遍歷O（n）中的所有列表（除非它是雙重根）。刪除尾部需要您修改倒數第二個元素。爲了達到這個效率，你需要一個雙鏈表（雙重鏈表不足以使得O（1））

但是當然任何雙鏈表都繼承了從單一鏈接列表。您仍然可以訪問O（1）中的頭部。所以在隊列和堆棧沒有矛盾。

請注意，在Java的現實中，由於開銷，LinkedList幾乎總是一個壞主意。無論是堆棧還是隊列，都應該使用它，但是您應該更喜歡基於陣列的實現，除非您經常插入或移除大型列表的中間中的對象。（真的，基準LinkedList - 這是非常緩慢和內存昂貴）。

來源

2016-09-18 12:48:27

Java - LinkedList push（）pop（）意味着它是一個堆棧，而不是一個隊列？

回答

相關問題