c ++ deque vs queue vs stack

82

Kolejka i stos to struktury szeroko wymieniane. Jednak w C ++ dla kolejki możesz to zrobić na dwa sposoby:

#include <queue>
#include <deque>

ale w przypadku stosu możesz to zrobić tylko w ten sposób

#include <stack>

Moje pytanie brzmi: jaka jest różnica między queue a deque, dlaczego zaproponowano dwie struktury? Czy w przypadku stosu można uwzględnić inną strukturę?

skydoor
źródło

Odpowiedzi:

78

Moron / Aryabhatta ma rację, ale trochę więcej szczegółów może być pomocnych.

Kolejka i stos są kontenerami wyższego poziomu niż deque, vector czy lista. Rozumiem przez to, że możesz zbudować kolejkę lub składować z kontenerów niższego poziomu.

Na przykład:

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

Zbuduje stos ints przy użyciu deque jako podstawowego kontenera i kolejki double przy użyciu listy jako podstawowego kontenera.

Możesz myśleć o sograniczonym deque i qjako o ograniczonej liście.

Wszystko, co jest potrzebne, to aby kontener niższego poziomu implementował metody wymagane przez kontener wyższego poziomu. Są back(), push_back()i pop_back()na stosie i front(), back(), push_back(), i pop_front()do kolejki.

Więcej szczegółów znajdziesz w sekcji stos i kolejka .

Jeśli chodzi o deque, jest to znacznie więcej niż kolejka, w której można wstawić na obu końcach. W szczególności ma dostęp losowy operator[]. To sprawia, że ​​bardziej przypomina wektor, ale wektor, w którym można wstawiać i usuwać na początku za pomocą push_front()i pop_front().

Szczegółowe informacje można znaleźć w deque .

Andrew Stein
źródło
16
stacki queue po prostu ogranicz deque jego pełny zestaw funkcji.
bobobobo
59

Queue: można włożyć tylko na jednym końcu i wyjąć na drugim.

Deque: możesz wkładać i wyjmować z obu końców.

Więc używając a Deque, możesz modelować zarówno a, Queuejak i Stack.

Podpowiedź:
Dequeto skrót od " D ouble e wyładowanych que ue".

ahmednabil88
źródło
4
Czy nie przesadzi, jeśli użyjesz Deque do modelowania stosu?
skydoor
Nie możesz modelować stosu z kolejką.
R Samuel Klatchko
1
Różnic jest o wiele więcej. queuenie spełnia wymagań kontenera. Nie ma iteratorów, na litość boską!
Potatoswatter
@skydoor Ze wszystkich standardowych kontenerów bibliotecznych, deque jest prawdopodobnie tym, który ma najniższy narzut.
3
@skydoor: Podobnie jak FYI, STL domyślnie std::stackużywa std::dequejako kontenera zapasowego. Spekuluję na temat powodu tutaj: stackoverflow.com/questions/102459/… (zasadniczo, że rosnące A dequeto niskie obciążenie).
Michael Burr,
33

dequeto szablon kontenera. Spełnia wymagania dla sekwencji z iteratorami o swobodnym dostępie, podobnie jak plik vector.

queuenie jest w ogóle pojemnikiem, jest adapterem . Zawiera kontener i zapewnia inny, bardziej szczegółowy interfejs. Użyj, queuegdy chcesz zapamiętać (lub przypomnieć), aby uniknąć operacji poza push[_back]i pop[_front], fronti back, sizei empty. W ogóle nie możesz patrzeć na elementy wewnątrz queueoprócz pierwszego i ostatniego!

Potatoswatter
źródło
7
Adapter - innymi słowy niepotrzebna funkcjonalność paraliżująca , ale adapter jest w porządku
bobobobo
22

W bibliotece C ++ oba elementy std::stacki std::queuesą zaimplementowane jako adaptery kontenerów . Oznacza to, że zapewniają interfejs odpowiednio stosu lub kolejki, ale żaden z nich nie jest sam w sobie kontenerem. Zamiast tego używają innego kontenera (np. std::dequeLub std::listfaktycznie do przechowywania danych), a std::stackklasa ma tylko niewielki fragment kodu do przetłumaczenia pushi popdo push_backi pop_back(i std::queuerobi mniej więcej to samo, ale używa push_backi pop_front).

Jerry Coffin
źródło
Dla queueVS wydaje się również mapa popdo pop_front, i pushdopush_back , więc myślę, że jest to zależne od implementacji.
chappjc
@chappjc: Nie - sprawdzam ponownie, tylko moja pamięć była wyłączona. pop_fronti push_backsą tym, czego potrzebujesz. Przepraszam.
Jerry Coffin
7

Deque to kolejka dwustronna, która umożliwia łatwe wstawianie / wyjmowanie z każdego końca. Kolejki pozwalają tylko na wstawianie na jednym końcu i pobieranie z drugiego.

Michael Hackner
źródło
5

deque obsługuje insert / pop z tyłu iz przodu

Kolejka obsługuje tylko wkładanie do tyłu i wyskakiwanie od przodu. Wiesz, FIFO (pierwszy wchodzi, pierwszy wychodzi).

rmn
źródło
0

Deque jest dwustronny. Kolejka nie jest.

Skilldrick
źródło
0

Usuwanie kolejki z kolejki priorytetowej odbywa się na podstawie porównania kolejności (priorytetów), a nie kolejności umieszczania w kolejce.

Na przykład możesz przechowywać zdarzenia czasowe w takim, w którym chcesz najpierw wyciągnąć najwcześniejsze zdarzenie i zapytać o jego zaplanowany czas, abyś mógł spać do tego momentu.

Kolejki priorytetowe są często implementowane przy użyciu stert.

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

Ostry ból
źródło
0

In deque (podwójna kolejka) Element można wstawić od tyłu i usunąć z tyłu (tak samo jak stos), ale w kolejce usuwać tylko od przodu.

Nagappa
źródło
Ta odpowiedź nie dodaje nic nowego do tematu (a większość odpowiedzi pochodzi z 2010 roku)
barbsan