¿Qué es una cola circular?
La mejor manera de implementar una cola es usar una lista vinculada, porque para las matrices, la cola puede tener la siguiente situación:
Como se muestra en la figura, no se pueden agregar más elementos. de lo contrario, la matriz se saldrá de los límites y provocará un error en el programa. Sin embargo, la matriz no debe expandirse en este momento porque todavía hay mucho espacio real que no está ocupado.
¿Cómo deberíamos solucionar este problema en este momento? Implementamos esto como una cola circular.
¿Qué es una cola circular? En primer lugar, debemos explicar que la cola circular todavía se implementa en base a matrices. Pero para ilustrar visualmente el problema, se muestra en la siguiente figura
1. Hay dos punteros en la figura (en realidad, dos variables enteras, porque aquí tienen una función de indicación, por lo que se entienden). como punteros aquí) adelante, atrás, uno indica la cabeza del equipo y el otro indica la cola del equipo.
2. La parte trasera y la delantera se persiguen entre sí. Este proceso de persecución es el proceso de agregar y eliminar colas. Si la parte trasera alcanza a la cabeza, significa que la cola está llena. significa que la cola está vacía.
3. Lo doblamos y usamos el resto, para que los dos valores no se salgan del rango máximo y se pueda lograr el efecto de flexión, por lo que para la cola circular debemos dar el valor máximo MAXQSIZE.
Esto en realidad es nuestra imaginación. De todos modos, lo que tenemos que hacer es usar bucles para resolver el problema del espacio desperdiciado.
Al agregar un elemento, (rear+1)%MAXQSIZE; // ¿Entiendes por qué se requiere el resto?
Al eliminar un elemento, (front+1)%MAXQSIZE; // ¿Entiendes por qué se requiere el resto?
Cuando rear=front, la cola puede estar llena o vacía.
Debido a que hay dos situaciones: lleno y vacío, debemos juzgar respectivamente:
Lleno: cuando la cola agrega un elemento al final y el siguiente elemento es el encabezado, es decir, el círculo necesita Cuando nos reunimos, asumimos que la cola está llena. (Q.rear+1)%MAXSIZE=Q.front
Vacío: cuando la cola elimina elementos en head=rear, pensamos que la cola está vacía. Q.trasero==Q.front, no necesariamente 0.
Imagen: