container - stl c++ español
c++ deque vs queue vs stack (8)
Queue y Stack son estructuras ampliamente mencionadas. Sin embargo, en C ++, para cola, puede hacerlo de dos maneras:
#include <queue>
#include <deque>
pero para stack solo puedes hacerlo así
#include <stack>
Mi pregunta es, ¿cuál es la diferencia entre cola y deque, por qué se proponen dos estructuras? Para la pila, ¿se podría incluir cualquier otra estructura?
Cola: puede insertar solo en un extremo y eliminarlo del otro.
Deque: puede insertar y quitar de ambos extremos.
Entonces, usando un Deque, puedes modelar una cola y una pila.
En la biblioteca de C ++, tanto std::stack como std::queue se implementan como adaptadores de contenedor. Eso significa que proporcionan la interfaz de una pila o cola, respectivamente, pero ninguno es realmente un contenedor en sí mismo. En su lugar, utilizan algún otro contenedor (por ejemplo, std::deque o std::list para almacenar realmente los datos), y la clase std::stack solo tiene un pequeño código para traducir push y pop a push_back y pop_back (y std::queue hace más o menos lo mismo, pero usa push_back y pop_front ).
La cola de prioridad dequeue sucede de acuerdo con alguna comparación de ordenamiento (prioridad) no la orden de puesta en cola.
Por ejemplo, puede almacenar eventos temporizados en uno en el que desee sacar primero el evento más cercano y consultar su hora programada para que pueda dormir hasta ese momento.
Las colas de prioridad a menudo se implementan usando montones.
Moron / Aryabhatta es correcto, pero un poco más de detalle puede ser útil.
Queue y stack son contenedores de nivel superior a deque, vector o list. Con esto, quiero decir que puedes construir una cola o apilar de los contenedores de nivel inferior.
Por ejemplo:
std::stack<int, std::deque<int> > s;
std::queue<double, std::list<double> > q;
Construirá una pila de ints utilizando un deque como contenedor subyacente y una cola de dobles usando una lista como el contenedor subyacente.
Puede pensar s como un deque restringido q como una lista restringida.
Todo lo que es necesario es que el contenedor de nivel inferior implemente los métodos necesarios para el contenedor de nivel superior. Estos son back() , push_back() y pop_back() para stack y front() , back() , push_back() y pop_front() para la cola.
Ver stack y queue para más detalles.
Con respecto al deque, es mucho más que una cola donde puedes insertar en ambos extremos. En particular, tiene el operator[] acceso aleatorio operator[] . Esto lo hace más como un vector, pero un vector donde puede insertar y eliminar al principio con push_front() y pop_front() .
Ver deque para más detalles.
Una deque es una cola de doble extremo, que permite una fácil inserción / eliminación desde cualquier extremo. Las colas solo permiten la inserción en un extremo y la recuperación del otro.
Una deque tiene dos extremos. Una cola no es.
deque admite inserción / pop desde atrás y adelante
la cola solo admite inserción en la parte posterior y emerge desde el frente. Ya sabes, un FIFO (primero en entrar primero en salir).
deque es una plantilla de contenedor. Satisface los requisitos para una secuencia con iteradores de acceso aleatorio, muy parecido a un vector .
queue no es un contenedor en absoluto, es un adaptador . Contiene un contenedor y proporciona una interfaz diferente y más específica. Use la queue cuando desee recordar (o recordar) para evitar operaciones además de push[_back] y pop[_front] , front y back , size y empty . ¡No puedes mirar los elementos dentro de la queue además del primero y el último, en absoluto!