двухсторонняя очередь C++ по сравнению с очередью по сравнению со стеком
Очередь и Стек являются структурами, широко упомянутыми. Однако в C++, для очереди можно сделать это двумя способами:
#include <queue>
#include <deque>
но для стека можно только сделать это как это
#include <stack>
Мой вопрос, каково различие между очередью и двухсторонней очередью, почему две предложенные структуры? Для стека могла быть включена какая-либо другая структура?
7 ответов
Морон / Арьябхатта прав, но может быть полезно немного подробнее.
Очередь и стек являются контейнерами более высокого уровня, чем deque, vector или list. Под этим я подразумеваю, что вы можете построить очередь или стек из контейнеров нижнего уровня.
Например:
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 () для очереди.
Подробнее см. стек и очередь .
Что касается двухсторонней очереди, то это гораздо больше, чем очередь, в которую можно вставлять с обоих концов. В частности, он имеет оператор произвольного доступа [] . Это делает его больше похожим на вектор, но на вектор, в который вы можете вставлять и удалять в начале с помощью push_front () и pop_front () .
Подробнее см. deque .
Я пытаюсь дать краткий ответ. Однако предполагается, что ввод будет правильным.
int c1, c2, i;
c1 = a[0] == b[0] ? 0
: (a[0] == b[1] ? 1 : 2); // index of a[0] in array 'b'
c2 = a[1] == b[0] ? 0
: (a[1] == b[1] ? 1 : 2); // index of a[1] in array 'b'
for(i=0; i<2; i++)
Console.WriteLine(a[i]);
Console.WriteLine(b[3-c1-c2]); // looks quite hacky but it is actually element of 'b' not in array 'a'
Декэ является двойным концом. Очередь - нет.
-121--891483- Очередь : можно вставить только в один конец и удалить из другого.
Deque : можно вставлять и удалять с обоих концов.
Таким образом, с помощью Deque можно моделировать Очередь , а также Стек .
Подсказка:
Deque - это сокращение от « D double e nded que ue».
Причина этого: Коллекции, которые не реализуют IEnumerable < T > или IQueryable, не могут быть итерируются в LINQ
dict и многие dict-подобные объекты (в том числе Django 's StartRequest вы, кажется, используете) позволяют передавать значение по умолчанию для get () :
subject = request.POST.get('subject', '[some_default_subject]')
Это предпочтительный метод, поскольку он является самым коротким и прозрачным в отношении ваших намерений.
-121--2246948- deque является шаблоном контейнера. Он удовлетворяет требованиям для последовательности с итераторами произвольного доступа, во многом подобно вектору .
очередь не является контейнером, это адаптер . Он содержит контейнер и обеспечивает другой, более конкретный интерфейс. Используйте очередь , если требуется запомнить (или напомнить), чтобы избежать операций, кроме нажать [_ back] и pop [_ front] , front и back , size и empty . Вы не можете смотреть на элементы в очереди , кроме первой и последней, вообще!
В библиотеке C++ и std::stack, и std::queue реализованы как контейнерные адаптеры. Это означает, что они предоставляют интерфейс стека или очереди соответственно, но ни один из них не является контейнером сам по себе. Вместо этого они используют какой-то другой контейнер (например. std::deque или std::list для хранения данных), а класс std:: stack класс просто имеет крошечный кусочек кода для перевода push и pop в push_back и pop_back (а std::queue делает примерно то же самое, но используя push_back и pop_front).
Очередь deque - это двусторонняя очередь, которая позволяет легко вставлять и удалять данные с любого конца. Очереди позволяют только вставлять в один конец и извлекать из другого.
deque поддерживает вставку/извлечение с задней и передней стороны
Очередь поддерживает только вставку с задней стороны и извлечение с передней. Вы знаете, FIFO (первым пришел - первым ушел).