c++ deque vs queue vs stack

2022-01-24 00:00:00 containers c++

Queue 和 Stack 是一种被广泛提及的结构.但是,在 C++ 中,对于队列,您可以通过两种方式进行:

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

#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?

推荐答案

Moron/Aryabhatta 是正确的,但更多细节可能会有所帮助.

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

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

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.

例如:

  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.

您可以将 s 视为受限双端队列,将 q 视为受限列表.

You can think of s as a restricted deque and q as a restricted list.

所有需要的是低层容器实现高层容器所需的方法.这些是 back()push_back()pop_back() 用于堆栈和 front()back()push_back()pop_front() 用于队列.

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.

参见 stack 和 queue 了解更多详情.

See stack and queue for more detail.

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

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().

详见deque.

相关文章