C++ deque vs隊列vs棧

Question

隊列和堆棧是廣泛提及的結構。然而，在C++中，隊列你可以做到這一點有兩種方式：

#include <queue> 
#include <deque> 

但對於棧你只能做這樣的

#include <stack> 

我的問題是，什麼是隊列和雙端隊列之間的區別，爲什麼提出兩種結構？對於堆棧，可以包含任何其他結構？

Answer 1

Moron是正確的，但更多的細節可能會有所幫助。

隊列和堆棧是比雙端隊列，向量或列表更高級別的容器。通過這個，我的意思是你可以建立一個隊列或堆棧從較低級別的容器。

例如：

std::stack<int, std::deque<int> > s; 
    std::queue<double, std::list<double> > q; 

將建成使用雙端隊列作爲底層容器和使用列表作爲底層容器雙打的隊列整數的堆疊。

您可以將s視爲受限制的雙列隊列表，並將q視爲受限列表。

所有必需的是下層容器實現上層容器所需的方法。對於堆棧，這些是back(),push_back()和pop_back()，對於隊列是front(),back(),push_back()和pop_front()。

有關詳細信息，請參見stack和queue。

對於雙端隊列，它遠遠超過了你可以插入兩端的隊列。特別是，它有隨機訪問operator[]。這使得它更像是一個向量，但是它可以在開頭以push_front()和pop_front()插入和刪除。

詳情請參見deque。

Answer 2

德克是雙端的。隊列不是。

Answer 3

隊列：您可以只插入一端，並從另一端刪除。

德克：你可以插入和從兩端刪除。

因此，使用一個Deque，你可以建立一個隊列以及一個堆棧。

Answer 4

deque是一個雙端隊列，允許從任一端輕鬆插入/移除。隊列只允許一端插入並從另一端進行檢索。

Answer 5

雙端隊列支持從背面&前

隊列只支持插入到後面，和從正面彈出插入/彈出。你知道，一個FIFO（先進先出）。

Answer 6

deque是一個容器模板。它滿足隨機訪問迭代器序列的要求，很像vector。

queue根本不是容器，它是一個適配器。它包含一個容器並提供了一個不同的，更具體的接口。當您想要記住（或提醒）以避免除push[_back]和pop[_front],front和back,size和empty之外的操作時使用queue。除了第一個和最後一個，你根本看不到queue裏面的元素！

Answer 7

在C++庫中，std::stack和std::queue均作爲容器適配器實現。這意味着它們分別提供堆棧或隊列的接口，但它們本身都不是一個容器。相反，他們使用一些其他的容器（例如std::deque或std::list實際存儲的數據），和std::stack類只是有代碼一點點到push和pop轉化爲push_back和pop_back（和std::queue做大致相同，但使用push_back和pop_front）。

Answer 8

優先級隊列出隊根據某種排序（優先級）比較而不是排隊順序發生。

例如，您可以將定時事件存儲在想要首先提取最早事件並查詢其計劃時間的事件中，以便您可以在該時間點之前休眠。

優先級隊列通常使用堆實現。