Estructura de datos - cola

La cola es una tabla lineal especial y un tipo de datos común. Lo especial es que solo se puede eliminar en la parte delantera de la mesa e insertar en la parte posterior de la mesa. El extremo que realiza la operación de inserción se denomina cola de la cola y el extremo que realiza la operación de eliminación se denomina cabecera de la cola.

La cola también se denomina tabla lineal primero en entrar, primero en salir (FIFO, primero en entrar, primero en salir).

Las tablas lineales se dividen en almacenamiento secuencial y almacenamiento en cadena. La pila es una tabla lineal, por lo que también existen estos dos métodos de almacenamiento. De manera similar, la cola, como tabla lineal especial, también tiene estos dos métodos de almacenamiento.

Como sugiere el nombre, el almacenamiento secuencial utiliza matrices, mientras que el almacenamiento vinculado utiliza listas vinculadas.

Las colas de almacenamiento secuencial se dividen en colas secuenciales y colas circulares.

En primer lugar, hablemos mal de la cola secuencial. La cola secuencial puede mantener la complejidad temporal de O (1) al ingresar a la cola, pero al quitar la cola, los elementos detrás del encabezado de la cola deben ser necesarios. para avanzar en secuencia, para garantizar que el encabezado de la cola no esté vacío, la complejidad del tiempo se vuelve O (n);

¿Por qué se deben mover todos al quitar la cola? ¿quitar la cola?, claro.

Si no hay restricción de que los elementos de la cola deban almacenarse en las primeras n unidades de la matriz, el rendimiento de la eliminación de la cola mejorará enormemente. Esto también significa que el jefe del equipo no necesariamente se encuentra en el índice = 0.

Supongamos que es una matriz de longitud 5. En el estado inicial, la cola vacía es como se muestra y los punteros delantero y trasero apuntan a la posición con el subíndice 0. Luego, a1, a2, a3, a4 se ponen en cola, el puntero frontal todavía apunta a la posición con índice 0 y el puntero trasero apunta a la posición con índice 4.

Cuando a1 y a2 se retiran de la cola, el puntero frontal apunta a la posición con el subíndice 2 y el puntero posterior permanece sin cambios, como se muestra en la figura siguiente. Cuando se vuelve a ingresar a5, el puntero frontal permanece. sin cambios y el puntero trasero se mueve hacia el exterior de la matriz. ¿Eh? Fuera del conjunto, ¿dónde estaría eso?

Como se muestra en la figura anterior, después de agregar el elemento a5, la parte trasera se ha quedado sin hogar. Al mismo tiempo, el espacio en las posiciones 0 y 1 se ha desperdiciado. Esta situación se denomina desbordamiento falso.

Para solucionar el problema del falso desbordamiento, se introduce la cola circular de la que hablaremos a continuación.

Siguiendo la imagen de arriba, para brindarles a las personas sin hogar un buen lugar donde quedarse, la colocaremos en index=0.

Pero si continúa uniéndose a la cola, por ejemplo, continúa insertando a6 y a7, el puntero trasero coincidirá con el puntero frontal y señalará la posición con el subíndice 2.

En este momento, el problema surge nuevamente. Acabamos de decir que cuando la cola está vacía, es igual a rear. Ahora, cuando la cola está llena, from también es igual a rear. ¿Si la cola está vacía o llena en este momento?

El primer método es establecer una bandera variable. Cuando front == rear y flag = 0, la cola está vacía. Cuando front == rear y flag = 1, la cola está llena.

El segundo método es que cuando la cola está vacía, la condición es from = rear. Cuando la cola está llena, modificamos la condición y reservamos un espacio de elemento. En otras palabras, cuando la cola está llena, todavía queda una unidad libre en la matriz. Como se muestra en la figura siguiente, consideramos que esta cola está llena, es decir, no permitimos que ocurra la situación en la figura anterior.

En el segundo caso, como las traseras pueden ser más grandes o más pequeñas que las delanteras, aunque están llenas cuando sólo se diferencian en una posición, también pueden diferir en un círculo completo. Entonces, si el tamaño máximo de la cola es QueueSize, entonces la condición para que la cola esté llena es (trasero+1) %QueueSize == front (el propósito del módulo “% es integrar los tamaños delantero y trasero en un solo problema).

Por ejemplo, en el ejemplo anterior, QueueSize = 5, cuando front = 0 y rear = 4, (4+1) %5 = 0, por lo que la cola está llena en este momento. Por ejemplo, delante = 2 y detrás = 1. 1) %5 = 2, por lo que la cola también está llena en este momento. Para la imagen siguiente, delante = 2 y detrás = 0, (1) %5 = 1, 1! = 2, por lo que la cola no está llena en este momento

Además, cuando atrás > adelante, la longitud de la cola es atrás-delante, pero cuando atrás < adelante, la longitud de la cola. se divide en dos segmentos, uno es QueueSize-front y el otro es 0. + rear, sumados, la longitud de la cola es rear-front + QueueSize, por lo que la fórmula general para calcular la longitud de la cola es:

(trasero—frontal + QueueSize) % QueueSize

Desde arriba En la imagen, no es difícil ver que existe el problema de que la matriz puede desbordarse en el almacenamiento secuencial, lo que conduce a la estructura de almacenamiento en cadena.

En la cola de cadena, el puntero principal apunta al nodo principal y el puntero de cola apunta al nodo principal. Apuntando al nodo terminal, una cola de cadena común se muestra a continuación:

Cuando la cola está vacía, tanto la parte delantera como la trasera apuntan al nodo principal