queue data structure c with illustration
Una breve introducción a la cola en C ++ con ilustración.
La cola es una estructura de datos básica como una pila. A diferencia de la pila que usa el enfoque LIFO, la cola usa el enfoque FIFO (primero en entrar, primero en salir). Con este enfoque, el primer elemento que se agrega a la cola es el primer elemento que se elimina de la cola. Al igual que Stack, la cola también es una estructura de datos lineal.
directivas de preprocesador en c ++ con ejemplo
En una analogía del mundo real, podemos imaginar una cola de autobús donde los pasajeros esperan el autobús en una cola o en una fila. El primer pasajero de la fila ingresa primero al autobús, ya que ese pasajero es el que había venido primero.
=> Lea la popular serie de capacitación en C ++ aquí.
Lo que vas a aprender:
Cola en C ++
En términos de software, la cola puede verse como un conjunto o colección de elementos como se muestra a continuación. Los elementos están dispuestos linealmente.
Tenemos dos extremos, es decir, 'frontal' y 'posterior' de la cola. Cuando la cola está vacía, ambos punteros se establecen en -1.
El puntero del extremo 'trasero' es el lugar desde donde se insertan los elementos en la cola. La operación de agregar / insertar elementos en la cola se llama “poner en cola”.
El puntero 'frontal' es el lugar desde donde se eliminan los elementos de la cola. La operación para eliminar / eliminar elementos de la cola se llama “sacar de cola”.
Cuando el valor del puntero trasero es de tamaño 1, decimos que la cola está llena. Cuando el frente es nulo, la cola está vacía.
Operaciones básicas
La estructura de datos de la cola incluye las siguientes operaciones:
- EnQueue: Agrega un elemento a la cola. La adición de un elemento a la cola siempre se realiza al final de la cola.
- DeQueue: Elimina un elemento de la cola. Un elemento se elimina o se retira de la cola siempre al principio de la cola.
- esta vacio: Comprueba si la cola está vacía.
- está lleno: Comprueba si la cola está llena.
- ojeada: Obtiene un elemento al principio de la cola sin eliminarlo.
Enqueue
En este proceso, se realizan los siguientes pasos:
- Comprueba si la cola está llena.
- Si está lleno, produce un error de desbordamiento y sale.
- De lo contrario, incremente 'trasero'.
- Agregue un elemento a la ubicación señalada por 'trasero'.
- Devuelve el éxito.
Dequeue
La operación de sacar de cola consta de los siguientes pasos:
- Comprueba si la cola está vacía.
- Si está vacío, muestra un error de subdesbordamiento y sale.
- De lo contrario, el elemento de acceso se indica con 'frente'.
- Incremente el 'frente' para apuntar a los siguientes datos accesibles.
- Devuelve el éxito.
A continuación, veremos una ilustración detallada de las operaciones de inserción y eliminación en cola.
Ilustración
Esta es una cola vacía y, por lo tanto, tenemos la parte trasera y vacía configuradas en -1.
A continuación, agregamos 1 a la cola y, como resultado, el puntero trasero avanza una ubicación.
En la siguiente figura, agregamos el elemento 2 a la cola moviendo el puntero trasero hacia adelante en otro incremento.
En la siguiente figura, agregamos el elemento 3 y movemos el puntero trasero en 1.
En este punto, el puntero trasero tiene valor 2 mientras que el puntero frontal está en 0thlocalización.
A continuación, eliminamos el elemento señalado por el puntero frontal. Como el puntero frontal está en 0, el elemento que se elimina es 1.
Por lo tanto, el primer elemento ingresado en la cola, es decir, 1 pasa a ser el primer elemento eliminado de la cola. Como resultado, después de la primera salida de la cola, el puntero frontal ahora se moverá hacia adelante a la siguiente ubicación que es 1.
Implementación de matriz para cola
Implementemos la estructura de datos de la cola usando C ++.
|_+_|Producción:
¡La cola está vacía!
Cola creada:
10 20 30 40 50
¡La cola está llena!
Frente = 0
Elementos de la cola: 10 20 30 40 50
Trasera = 4
Eliminado => 10 de myqueue
Frente = 1
Elementos de la cola: 20 30 40 50
Trasera = 4
La implementación anterior muestra la cola representada como una matriz. Especificamos max_size para la matriz. También definimos las operaciones de poner y quitar de la cola, así como las operaciones isFull e isEmpty.
A continuación se muestra la implementación de Java de la estructura de datos de la cola.
|_+_|Producción:
Cola creada como:
10 20 30 40
Elemento 10 retirado de la cola
El frente es 20
El artículo trasero es 40
La implementación anterior es similar a la implementación de C ++.
A continuación, implementemos la cola en C ++ usando una lista vinculada.
Implementación de lista vinculada para cola:
|_+_|Producción:
Cola creada:
10 20 30 40 50
El elemento eliminado de la cola es: 10
Cola después de una eliminación:
20 30 40 50
c ++ flotante aleatoria entre 0 y 1
Pila vs. Cola
Las pilas y las colas son estructuras de datos secundarias que se pueden utilizar para almacenar datos. Se pueden programar utilizando las estructuras de datos primarias como matrices y listas enlazadas. Habiendo discutido ambas estructuras de datos en detalle, es hora de discutir las principales diferencias entre estas dos estructuras de datos.
| Pilas | Colas |
|---|---|
| Utiliza el enfoque LIFO (último en entrar, primero en salir). | Utiliza el enfoque FIFO (primero en entrar, primero en salir). |
| Los elementos se agregan o eliminan de un solo extremo llamado 'Parte superior' de la pila. | Los elementos se agregan desde el extremo 'posterior' de la cola y se eliminan del 'frente' de la cola. |
| Las operaciones básicas para la pila son 'empujar' y 'Pop'. | Las operaciones básicas para una cola son 'poner en cola' y 'sacar de cola'. |
| Podemos hacer todas las operaciones en la pila manteniendo solo un puntero para acceder a la parte superior de la pila. | En las colas, necesitamos mantener dos punteros, uno para acceder al frente de la cola y el segundo para acceder al final de la cola. |
| La pila se usa principalmente para resolver problemas recursivos. | Las colas se utilizan para resolver problemas relacionados con el procesamiento ordenado. |
Aplicaciones de la cola
Analicemos las diversas aplicaciones de la estructura de datos de cola a continuación.
- La estructura de datos de la cola se utiliza en varias programaciones de CPU y disco. Aquí tenemos varias tareas que requieren CPU o disco al mismo tiempo. El tiempo de CPU o disco se programa para cada tarea mediante una cola.
- La cola también se puede utilizar para la cola de impresión en la que el número de trabajos de impresión se coloca en una cola.
- El manejo de interrupciones en sistemas en tiempo real se realiza mediante el uso de una estructura de datos en cola. Las interrupciones se gestionan en el orden en que llegan.
- La búsqueda en amplitud primero en la que se atraviesan los nodos vecinos de un árbol antes de pasar al siguiente nivel utiliza una cola para la implementación.
- Los sistemas telefónicos del centro de llamadas utilizan colas para retener las llamadas hasta que los representantes de servicio las respondan.
En general, podemos decir que la estructura de datos de la cola se utiliza siempre que necesitamos que los recursos o elementos sean atendidos en el orden en que llegan, es decir, primero en entrar, primero en salir.
Conclusión
La cola es una estructura de datos FIFO (primero en entrar, primero en salir) que se usa principalmente en recursos donde se requiere programación. Tiene dos punteros delante y detrás en dos extremos y estos se utilizan para insertar un elemento y quitar un elemento de la cola respectivamente.
En nuestro próximo tutorial, aprenderemos sobre algunas de las extensiones de la cola como la cola de prioridad y la cola circular.
=> Consulte aquí para explorar la lista completa de tutoriales de C ++.
Lectura recomendada
- Estructura de datos de cola de prioridad en C ++ con ilustración
- Cola de prioridad en STL
- Estructura de datos de pila en C ++ con ilustración
- Estructura de datos de lista enlazada circular en C ++ con ilustración
- Estructura de datos de lista vinculada en C ++ con ilustración
- Estructura de datos de lista doblemente enlazada en C ++ con ilustración
- Introducción a las estructuras de datos en C ++
- Parametrización de datos de JMeter usando variables definidas por el usuario