c circular queue data structure
Este tutorial sobre la estructura de datos de la cola circular de C ++ explica qué es la cola circular, cuáles son las operaciones básicas junto con la implementación y las aplicaciones:
Una cola circular es una extensión de la cola básica que hemos discutido anteriormente. También se conoce como 'búfer de anillo'.
¿Qué es la cola circular en C ++?
Una cola circular es una estructura de datos lineal que se utiliza para almacenar elementos de datos. Realiza operaciones siguiendo el enfoque FIFO (primero en entrar, primero en salir) y la última posición en la cola se conecta de nuevo a la primera posición para formar un círculo.
=> Busque toda la serie de formación en C ++ aquí
Lo que vas a aprender:
Cola circular en C ++
El siguiente diagrama muestra una cola circular.
La imagen de arriba muestra una estructura de datos circular de tamaño 10. Los primeros seis elementos ya están en la cola y vemos que la primera posición y la última posición están unidas. Debido a esta disposición, el espacio no se desperdicia como sucede en una cola lineal.
herramienta de reparación y escaneo de pc windows 10
En una cola lineal después de que la cola está llena, eliminamos los elementos de otro extremo, y el estado de la cola todavía se muestra como lleno y no podemos insertar más elementos.
En la cola circular, cuando la cola está llena, y cuando eliminamos elementos del frente ya que la última y la primera posición están conectadas, podemos insertar los elementos en la parte posterior que quedó vacante eliminando el elemento.
En la siguiente sección, aprenderemos sobre las operaciones básicas de la cola circular.
Operaciones básicas
Algunas de las operaciones básicas de la cola circular son las siguientes:
Parte delantera: Devuelve la posición delantera en la cola circular.
Trasero: Devuelve la posición posterior en la cola circular.
Poner en cola: Enqueue (valor) se usa para insertar un elemento en la cola circular. El elemento siempre se inserta al final de la cola.
Seguimos la siguiente secuencia de pasos para insertar un nuevo elemento en la cola circular.
#1) Compruebe si la cola circular está llena: test ((trasero == TAMAÑO-1 && delantero == 0) || (trasero == delantero-1)), donde 'TAMAÑO' es el tamaño de la cola circular.
#2) Si la cola circular está llena, muestra un mensaje como 'La cola está llena'. Si la cola no está llena, verifique si (trasero == TAMAÑO - 1 && delantero! = 0). Si es cierto, configure rear = 0 e inserte el elemento.
Dequeue: La función Dequeue se utiliza para eliminar un elemento de la cola. En la cola circular, el elemento siempre se elimina de la interfaz. A continuación se muestra la secuencia para la operación de desconexión en una cola circular.
VPN gratis Europa
Pasos:
#1) Compruebe si la cola circular está vacía: compruebe si (frente == - 1).
#2) Si está vacío, muestre el mensaje 'La cola está vacía'. Si la cola no está vacía, realice el paso 3.
#3) Compruebe si (delantero == trasero). Si es cierto, configure front = rear = -1; de lo contrario, compruebe si (front == size-1), si es cierto, configure front = 0 y devuelva el elemento.
Ilustración
En esta sección, veremos una ilustración detallada de cómo agregar / eliminar elementos en la cola circular.
Considere la siguiente cola circular de 5 elementos como se muestra a continuación:
A continuación, insertamos el elemento 1 en la cola.
A continuación, insertamos un elemento con valor 3.
Cuando insertamos los elementos para completar una cola, la representación será como se muestra a continuación.
Ahora eliminamos los dos elementos, es decir, el elemento 1 y el elemento 3 de la cola, como se muestra a continuación.
A continuación, insertamos o ponemos en cola el elemento 11 en la cola circular como se representa a continuación.
Nuevamente insertemos el elemento 13 en la cola circular. La cola se verá como se muestra a continuación.
Vemos que en la cola circular movemos o insertamos elementos en un círculo. Por lo tanto, podemos consumir todo el espacio de la cola hasta que se llene.
Implementación
Implementemos la cola circular usando C ++.
|_+_|Producción:
Arriba se muestra el resultado de las operaciones de cola circular. Primero, agregamos los elementos y luego retiramos de la cola o eliminamos dos elementos. A continuación, insertamos o ponemos en cola tres elementos más en la cola circular. Vemos que a diferencia de la cola lineal, los elementos se agregan al final de la cola.
Implementación de listas vinculadas
Analicemos ahora la implementación de la lista enlazada de una cola circular. A continuación se muestra la implementación de la lista vinculada de la cola circular en C ++. Tenga en cuenta que hacemos uso de la estructura para representar cada nodo. Las operaciones son las mismas que las discutidas anteriormente excepto que en este caso, tenemos que realizarlas con respecto a los nodos de la lista enlazada.
La salida muestra la cola circular después de la operación de poner en cola, sacar de la cola y también después de la segunda operación de poner en cola.
|_+_|Producción:
La siguiente implementación es un programa Java para demostrar la cola circular utilizando la lista vinculada.
|_+_|Producción:
La salida del programa anterior es similar al programa anterior.
Aplicaciones
Analicemos algunas de las aplicaciones de la cola circular.
- Programación de CPU: El proceso del sistema operativo que requiere que ocurra algún evento o que se completen otros procesos para su ejecución a menudo se mantiene en una cola circular para que se ejecuten uno tras otro cuando se cumplen todas las condiciones o cuando ocurren todos los eventos.
- Gestión de la memoria: El uso de colas ordinarias desperdicia espacio en la memoria como ya se mencionó en nuestra discusión anterior. El uso de una cola circular para la gestión de la memoria es beneficioso para un uso óptimo de la memoria.
- Sistema de señales de tráfico controlado por computadora: Las señales de tráfico computarizadas a menudo se agregan a una cola circular para que se repitan una vez transcurrido el intervalo de tiempo especificado.
Conclusión
Las colas circulares solucionan la mayor desventaja de una cola normal en la que no podemos insertar elementos cuando el puntero posterior está al final de la cola, incluso cuando eliminamos los elementos y se vacía el espacio. En una cola circular, los elementos se disponen de forma circular, de modo que no se desperdicia espacio en absoluto.
También hemos visto las principales operaciones de la cola circular. Las colas circulares son principalmente útiles para fines de programación y aplicaciones como sistemas de señales de tráfico donde las señales brillan en las curvas.
qa ingeniero entrevista preguntas respuestas pdf
En nuestro próximo tutorial, aprenderemos sobre las colas de dos extremos que simplemente se llaman 'deque'.
=> Visite aquí para aprender C ++ desde cero
Lectura recomendada
- Estructura de datos de cola en C ++ con ilustración
- Estructura de datos de cola de prioridad en C ++ con ilustración
- Estructura de datos de lista enlazada circular en C ++ con ilustración
- Tutorial de Data Mart: tipos, ejemplos e implementación de Data Mart
- Estructura de datos de pila en C ++ con ilustración
- Ejemplos de minería de datos: aplicaciones más comunes de minería de datos 2021
- Estructura de datos de árbol binario en C ++
- Cola de prioridad en STL