Queue es un tipo de datos abstracto con la disciplina de acceso al elemento primero en entrar, primero en salir ( FIFO , inglés first in, first out ). Agregar un elemento (generalmente indicado por la palabra poner en cola - poner en una cola) solo es posible al final de la cola, muestrear - solo desde el comienzo de la cola (que comúnmente se llama la palabra dequeue - eliminar de la cola), mientras que el elemento seleccionado se elimina de la cola.
Hay varias formas de implementar una cola en los lenguajes de programación.
La primera forma representa la cola como una matriz y dos variables enteras comienzan y terminan.
Por lo general start, apunta a la cabeza de la cola, end el elemento que se llenará cuando entre un nuevo elemento en la cola. Cuando se agrega un elemento a la cola, el q[end]nuevo elemento de la cola se escribe y se endreduce en uno. Si el valor de end se vuelve menor que 1, entonces hacemos un bucle alrededor de la matriz y el valor de la variable se vuelve igual a n. La extracción de un elemento de la cola se realiza de manera similar: después de extraer un elemento q[start]de la cola, la variable startse reduce en 1. Con tales algoritmos, una celda de la cola nsiempre estará desocupada (ya nque no se puede distinguir una cola con elementos ). de uno vacío), lo que se compensa con la sencillez de los algoritmos.
Ventajas de este método: es posible un ligero ahorro de memoria en comparación con el segundo método; más fácil de desarrollar.
Desventajas: el número máximo de elementos en la cola está limitado por el tamaño de la matriz. Cuando se desborda, requiere la reasignación de memoria y la copia de todos los elementos en una nueva matriz.
El segundo método se basa en trabajar con memoria dinámica. La cola se representa como una lista lineal , en la que la adición/eliminación de elementos proviene estrictamente de sus respectivos extremos.
Ventajas de este método: el tamaño de la cola está limitado únicamente por la cantidad de memoria.
Desventajas: más difícil de desarrollar; se requiere más memoria; cuando se trabaja con una cola de este tipo, la memoria está más fragmentada; la cola es algo más lenta.
Los métodos de cola se pueden implementar en función de dos pilas S1 y S2como se muestra a continuación:
procedimiento en cola ( x ): S1.empujar( x ) función dequeue(): si S2 está vacío: si S1 está vacío: informe de error: la cola está vacía hasta que S1 esté vacío: S2.push(S1.pop()) devolver S2.pop()Este método de implementación es el más conveniente como base para construir una cola persistente . .
Las colas se implementan en casi todos los lenguajes de programación desarrollados. La CLI proporciona la clase System.Collections.Queue para esto, con los métodos Enqueue y Dequeue. El STL también tiene la clase queue<>, definida en la cola del archivo de encabezado. Utiliza la misma terminología (push and pop) que stacks .
La cola en programación se utiliza, como en la vida real, cuando se necesita realizar algunas acciones en el orden en que se reciben, realizándolas secuencialmente. Un ejemplo es la organización de eventos en Windows. Cuando el usuario realiza alguna acción en la aplicación, el procedimiento correspondiente no se llama en la aplicación (después de todo, en este momento la aplicación puede realizar otras acciones), pero se le envía un mensaje que contiene información sobre la acción realizada, este mensaje está en cola, y solo cuando se procesan los mensajes que llegaron antes, la aplicación realizará la acción necesaria.
El búfer del teclado del BIOS está organizado como una matriz en anillo, generalmente de 16 palabras de máquina y dos punteros: al siguiente elemento en él y al primer elemento desocupado.
| Estructuras de datos | |
|---|---|
| Liza | |
| Árboles | |
| cuenta | |
| Otro | |