c ++ deque vs queue vs stack

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

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 .

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".

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!

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

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.

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

Deque jest dwustronny. Kolejka nie jest.

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

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.