стек очереди в C++ двухсторонняя очередь против против

очередь и стек являются широко упомянутыми структурами. Однако, в C++, по очереди, вы можете сделать это двумя способами:

#include <queue>
#include <deque>

но для стека вы можете сделать это только так 

#include <stack>

мой вопрос в том, в чем разница между queue и deque, почему предлагаются две структуры? Для стека, любая другая структура может быть включена?

8 62
c++ containers

8 ответов:

Moron / Aryabhatta правильно, но немного больше деталей может быть полезно.

очередь и стек-это контейнеры более высокого уровня, чем deque, vector или list. Под этим я подразумеваю, что вы можете построить очередь или стек из контейнеров более низкого уровня.

например:

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

будет построить стек из целых чисел с помощью двухсторонней очереди в качестве базового контейнера и очереди увеличатся, используя список в качестве базового контейнера.

вы можете думать о s ограниченные deque и q как ограниченный список.

все, что необходимо, это то, что контейнер нижнего уровня реализует методы, необходимые контейнеру более высокого уровня. Это back(),push_back() и pop_back() для стека и front(),back(),push_back() и pop_front() для очереди.

посмотреть стек и очереди подробнее.

что касается дека, это гораздо больше, чем очередь, где вы можете вставить с обоих концов. В частности, он имеет произвольный доступ operator[]. Это делает его более похожим на вектор, но вектор, где вы можете вставить и удалить в начале с push_front() и pop_front().

посмотреть deque для детали.

55

очередь: вы можете вставить только в один конец и удалить из другого.

Дека: вы можете вставить и удалить с обоих концов.

таким образом, используя Deque, вы можете моделировать очередь, а также стек.

31

deque - это шаблон контейнера. Он удовлетворяет требованиям для последовательности с итераторами произвольного доступа, так же как и vector.

queue это вообще не контейнер, это адаптер. Он содержит контейнер и предоставляет другой, более конкретный интерфейс. Используйте queue когда вы хотите вспомнить (или напомнить), чтобы избежать операции, кроме push[_back] и pop[_front],front и back,size и empty. Вы не можете смотреть на элементы внутри queue кроме первого и последнего, на все!

25

в библиотеке C++, как std::stack и std::queue реализуются как контейнер переходник. Это означает, что они обеспечивают интерфейс стека или очереди соответственно, но ни один из них не является контейнером сам по себе. Вместо этого они используют какой-то другой контейнер (например std::deque или std::list на самом деле хранить данные), и std::stack класс просто имеет немного кода для перевода push и pop до push_back и pop_back (и std::queue делает примерно то же самое, но с использованием push_back и pop_front).

18

deque-это двусторонняя очередь, которая позволяет легко вставлять/удалять с любого конца. Очереди позволяют только вставку в одном конце и извлечение из другого.

5

дека поддерживает вставить/поп со спины и спереди

очередь поддерживает только вставку в спину и поп спереди. Вы знаете, FIFO (первый в первый выход).

4

дек является двусторонним. А очереди нет.

0

приоритет очереди dequeue происходит в соответствии с некоторым упорядочением (приоритет) сравнения не порядок очереди.

например, вы можете хранить синхронизированные события в том, где вы хотите сначала вытащить самое раннее событие и запросить его запланированное время, чтобы вы могли спать до этого момента времени.

приоритетные очереди часто реализуются с помощью куч.

0