2010-02-11 15 views
52

Queue and Stack sono strutture ampiamente citate. Tuttavia, in C++, per la coda si può fare in due modi:C++ deque vs queue vs stack

#include <queue> 
#include <deque> 

ma per lo stack solo si può fare in questo modo

#include <stack> 

La mia domanda è, qual è la differenza tra la coda e deque , perché due strutture proposte? Per lo stack, potrebbe essere inclusa qualsiasi altra struttura?

risposta

44

Moron è corretto, ma un po 'più di dettaglio può essere utile.

La coda e lo stack sono contenitori di livello superiore rispetto a deque, vector o list. Con ciò intendo che puoi creare una coda o uno stack dai contenitori di livello inferiore.

Ad esempio:

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

costruirà una pila di interi che utilizzano un deque come contenitore sottostante e una coda dei doppi usando una lista come il contenitore sottostante.

Si può pensare a s come deque limitato e q come elenco limitato.

Tutto ciò che è necessario è che il contenitore di livello inferiore implementa i metodi necessari per il contenitore di livello superiore. Questi sono back(), push_back() e pop_back() per stack e front(), back(), push_back() e pop_front() per la coda.

Vedi stack e queue per maggiori dettagli.

Per quanto riguarda il deque, è molto più di una coda in cui è possibile inserire ad entrambe le estremità. In particolare, ha l'accesso casuale operator[]. Ciò lo rende più simile a un vettore, ma a un vettore in cui è possibile inserire ed eliminare all'inizio con push_front() e pop_front().

Vedere deque per dettagli.

+6

'stack' e' queue' ___just restrict___ 'deque' dal suo set completo. – bobobobo

+3

"Moron è corretto". 7 anni dopo quel tipo di linguaggio ti avrebbe messo al bando per tutta la vita. – ytpillai

+1

lol MrGreen Sì, al momento mi riferivo ad un'altra risposta qui. O l'utente ha cambiato il suo nome, o la risposta è stata cancellata da allora. –

28

Coda: è possibile inserire solo in una estremità e rimuoverle dall'altra.

Deque: è possibile inserire e rimuovere da entrambe le estremità.

Quindi, utilizzando un Deque, è possibile modellare una coda e una pila.

+3

non sarà eccessivo se si utilizza un Deque per modellare uno stack? – skydoor

+0

Non è possibile modellare uno stack con una coda. –

+1

Ci sono molte più differenze. 'queue' non soddisfa i requisiti di un contenitore. Non ha iteratori, per l'amor del cielo! – Potatoswatter

4

Un deque è una coda a doppio attacco, che consente un facile inserimento/rimozione da entrambe le estremità. Le code consentono solo l'inserimento in un'estremità e il recupero dall'altra.

3

deque supporta inserto/pop dal retro & davanti coda

supporta solo inserire sul retro, e pop dal fronte. Sai, un FIFO (primo in prima uscita).

21

deque è un modello di contenitore. Soddisfa i requisiti per una sequenza con iteratori ad accesso casuale, molto simile a vector.

queue non è un contenitore, è un adattatore . Contiene un contenitore e fornisce un'interfaccia diversa e più specifica. Utilizzare queue quando si desidera ricordare (o ricordare) per evitare operazioni oltre a push[_back] e pop[_front], front e back, size e empty. Non puoi guardare gli elementi all'interno dello queue oltre al primo e all'ultimo, a tutti!

+0

+1 - bella risposta. –

+4

Adapter - in altre parole _una funzionalità necessaria crippler_, ma l'adattatore va bene – bobobobo

16

Nella libreria C++, entrambi std::stack e std::queue sono implementati come adattatori del contenitore . Ciò significa che forniscono rispettivamente l'interfaccia di uno stack o di una coda, ma nessuno dei due è realmente un contenitore in sé. Invece, usare qualche altro contenitore (ad esempio std::deque o std::list per memorizzare effettivamente i dati), e la classe std::stack ha solo un po 'di codice di tradurre push e pop-push_back e pop_back (e std::queue fa più o meno lo stesso, ma usando push_back e pop_front).

+0

Per un 'queue', VS sembra anche mappare' pop' a 'pop_front', e' push' a 'push_back', quindi immagino che questo sia implementazione dipendente. – chappjc

+0

@chappjc: No - ricontrollare, solo la mia memoria era spenta. 'pop_front' e' push_back' sono ciò che è richiesto. Mie scuse. –

0

La rimozione della coda di priorità avviene in base a un confronto di ordine (priorità) non all'ordine di accodamento.

Ad esempio, è possibile archiviare gli eventi a tempo in uno in cui si desidera estrarre l'evento il più presto possibile e richiedere l'ora pianificata in modo da poter dormire fino a quel momento.

Le code di priorità vengono spesso implementate utilizzando gli heap.