c++ deque vs queue vs stack

c++ deque vs queue vs stack

提问by skydoor

Queue and Stack are a structures widely mentioned. However, in C++, for queue you can do it in two ways:

队列和堆栈是一种被广泛提及的结构。但是，在 C++ 中，对于队列，您可以通过两种方式实现：

#include <queue>
#include <deque>

but for stack you can only do it like this

但是对于堆栈，您只能这样做

#include <stack>

My question is, what's the difference between queue and deque, why two structures proposed? For stack, any other structure could be included?

我的问题是，队列和双端队列有什么区别，为什么要提出两种结构？对于堆栈，可以包括任何其他结构吗？

采纳答案by Andrew Stein

Moron/Aryabhatta is correct, but a little more detail may be helpful.

Moron/Aryabhatta 是正确的，但多一点细节可能会有所帮助。

Queue and stack are higher level containers than deque, vector, or list. By this, I mean that you can build a queue or stack out of the lower level containers.

队列和堆栈是比双端队列、向量或列表更高级的容器。我的意思是，您可以从较低级别的容器中构建队列或堆栈。

For example:

例如：

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

Will build a stack of ints using a deque as the underlying container and a queue of doubles using a list as the underlying container.

将使用双端队列作为底层容器构建一个整数堆栈，并使用列表作为底层容器构建一个双精度队列。

You can think of sas a restricted deque and qas a restricted list.

您可以将其s视为受限双端队列和q受限列表。

All that is necessary is that the lower level container implements the methods needed by the higher level container. These are back(), push_back(), and pop_back()for stack and front(), back(), push_back(), and pop_front()for queue.

所需要的只是较低级别的容器实现较高级别容器所需的方法。它们分别是back()、push_back()、 和pop_back()用于堆栈front()，back()、push_back()、 和pop_front()用于队列。

See stackand queuefor more detail.

有关更多详细信息，请参阅堆栈和队列。

With respect to the deque, it is much more than a queue where you can insert at both ends. In particular, it has the random access operator[]. This makes it more like a vector, but a vector where you can insert and delete at the beginning with push_front()and pop_front().

关于双端队列，它不仅仅是一个可以在两端插入的队列。特别是，它具有随机访问operator[]。这使它更像一个向量，但它是一个向量，您可以在其中以push_front()和开头插入和删除pop_front()。

See dequefor detail.

有关详细信息，请参阅deque。

回答by Andrew Stein

Queue: you can insert only in one end and remove from the other.

Queue：您只能在一端插入并从另一端移除。

Deque: you can insert and remove from both ends.

Deque: 可以从两端插入和移除。

So using a Deque, you can model a Queueas well as a Stack.

因此，使用 a Deque，您可以对 aQueue和 a建模Stack。

Hint:
Dequeis short for "Double ended queue".

提示：
Deque是短期的“ double ênded阙UE”。

回答by Potatoswatter

dequeis a container template. It satisfies the requirements for a sequence with random-access iterators, much like a vector.

deque是一个容器模板。它满足具有随机访问迭代器的序列的要求，很像vector.

queueis not a container at all, it is an adaptor. It contains a container and provides a different, more specific interface. Use queuewhen you want to remember (or remind) to avoid operations besides push[_back]and pop[_front], frontand back, sizeand empty. You can't look at elements inside the queuebesides the first and last, at all!

queue根本不是一个容器，它是一个适配器。它包含一个容器并提供不同的、更具体的界面。使用queue时，你要记住（或提醒），以避免操作之外push[_back]和pop[_front]，front和back，size和empty。queue除了 first 和 last 之外，你根本看不到里面的元素！

回答by Jerry Coffin

In the C++ library, both std::stackand std::queueare implemented as container adapters. That means they provide the interface of a stack or a queue respectively, but neither is really a container in itself. Instead, they use some other container (e.g. std::dequeor std::listto actually store the data), and the std::stackclass just has a tiny bit of code to translate pushand popto push_backand pop_back(and std::queuedoes roughly the same, but using push_backand pop_front).

在 C++ 库中，std::stack和std::queue都作为容器适配器实现。这意味着它们分别提供了堆栈或队列的接口，但它们本身都不是真正的容器。相反，他们使用其他一些容器（例如std::deque或std::list实际存储数据），并且std::stack该类只有一小部分代码可以将pushand转换pop为push_backand pop_back（并且std::queue大致相同，但使用push_backand pop_front）。

回答by Michael Hackner

A deque is a double-ended queue, which allows easy insertion/removal from either end. Queues only allow insertion in one end and retrieval from the other.

双端队列是双端队列，它允许从任一端轻松插入/删除。队列只允许在一端插入并从另一端检索。

回答by rmn

deque supports insert/pop from back & front

deque 支持前后插入/弹出

queue only supports insert to the back, and pop from the front. You know, a FIFO (first in first out).

queue 只支持插入到后面，从前面弹出。您知道，FIFO（先进先出）。

回答by rmn

Priority queue dequeue happens according to some ordering (priority) comparison not the enqueue order.

For instance you might store timed events in one where you want to pull out the soonest event first and query for its scheduled time so you can sleep until that point in time.

Priority queues are often implemented using heaps.

优先队列出队是根据一些排序（优先级）比较而不是入队顺序发生的。

例如，您可能将定时事件存储在一个您想首先提取最快的事件并查询其预定时间的位置，以便您可以在该时间点之前睡觉。

优先级队列通常使用堆来实现。

by Mike Anderson here:
https://www.quora.com/What-is-the-difference-between-a-priority-queue-and-a-queue

迈克·安德森在这里：https:
//www.quora.com/What-is-the-difference-between-a-priority-queue-and-a-queue

回答by Nagappa

In deque(double ended queue) The element can be inserted from back and remove form back(Same as stack), But in queue only remove from front.

在双端队列中（双端队列）元素可以从后面插入并从后面移除（与堆栈相同），但在队列中只能从前面移除。

回答by Skilldrick

A deque is double-ended. A queue isn't.

双端队列是双端的。队列不是。