En informática, una cola es una estructura de datos lineal en la que los componentes se colocan en un extremo y se retiran del otro extremo según el principio de 'primero en entrar, primero en salir' (FIFO). Esta estructura de datos se puede utilizar para controlar una secuencia de acciones o almacenar datos. C es un lenguaje informático con capacidad de cola incorporada en forma de matrices o listas enlazadas.
Características:
- Una cola es un tipo de estructura de datos lineal que se puede construir con una matriz o una lista vinculada.
- Los elementos se reubican al final de la cola mientras se eliminan del frente.
- Poner en cola (agregar un elemento al final) y sacar de la cola (eliminar un elemento del frente) son dos operaciones de cola.
- Cuando se agregan y eliminan elementos con frecuencia, se puede crear una cola circular para evitar el desperdicio de memoria.
Usando matriz:
Para implementar una cola en C usando una matriz, primero defina el tamaño máximo de la cola y declare una matriz de ese tamaño. Los enteros frontal y posterior se establecieron respectivamente en 1. La variable frontal representa el elemento frontal de la cola y la variable posterior representa el elemento posterior.
algoritmo de clasificación por inserción
Antes de enviar el nuevo elemento a la posición final de la cola, debemos aumentar la variable de retroceso en 1. La cola ahora está llena y no se pueden agregar otros elementos adicionales cuando la posición de retroceso alcanza la capacidad máxima de la cola. Agregamos un elemento al frente de la cola y aumentamos la variable frontal en uno solo para eliminar un elemento de la cola. Si las posiciones delantera y trasera son iguales y no se pueden eliminar más componentes, podemos decir que la cola está vacía.
A continuación se muestra una instancia de una cola escrita en C que utiliza una matriz:
Lenguaje de programación C:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } La salida del código será:
Producción:
cola en java
10 20 30 Queue is empty-1
Explicación:
- Primero, ponemos en cola tres elementos 10, 20 y 30.
- Luego, retiramos la cola e imprimimos el elemento frontal de la cola, que es 10.
- A continuación, retiramos la cola e imprimimos nuevamente el elemento frontal de la cola, que es 20.
- Luego, retiramos la cola e imprimimos nuevamente el elemento frontal de la cola, que es 30.
- Finalmente, sacamos de la cola una cola vacía que genera 'La cola está vacía' y devuelve -1.
Usando la lista enlazada:
Otro enfoque alternativo para construir una cola en el lenguaje de programación C es utilizar una lista enlazada. Cada uno de los nodos de la cola se expresa utilizando este método mediante un nodo que contiene el valor del elemento y un puntero al siguiente nodo de la cola. Para realizar un seguimiento del primer y último nodo de la cola, respectivamente, se utilizan punteros frontal y posterior.
Establecemos un nuevo nodo con el valor del elemento y configuramos su siguiente puntero en NULL para agregar un elemento a la cola. Para el nuevo nodo, configuramos los punteros frontal y posterior si la cola está vacía. De lo contrario, actualizamos el puntero posterior y configuramos el siguiente puntero del nodo posterior anterior para que apunte al nuevo nodo.
Al eliminar un nodo de una cola, el nodo anterior se elimina primero, luego el puntero frontal se actualiza al nodo siguiente en la cola y, finalmente, se libera la memoria que ocupaba el nodo eliminado. Si el puntero frontal es NULL después de la eliminación, la cola está vacía.
A continuación se muestra un ejemplo de una cola implementada en C usando una lista vinculada:
puntero en c
Lenguaje de programación C:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } La salida del código será:
Producción:
comparación de cadenas en java
10 20 30 Queue is empty-1
Explicación:
- Primero, ponemos en cola tres elementos 10, 20 y 30.
- Luego, retiramos la cola e imprimimos el elemento frontal de la cola, que es 10.
- A continuación, retiramos la cola e imprimimos nuevamente el elemento frontal de la cola, que es 20.
- Luego, retiramos la cola e imprimimos nuevamente el elemento frontal de la cola, que es 30.
- Finalmente, intentamos salir de la cola vacía, lo que imprime el mensaje 'La cola está vacía' y devuelve -1.
Ventajas:
- Las colas son particularmente útiles para implementar algoritmos que requieren que los elementos se procesen en una secuencia precisa, como la búsqueda en amplitud y la programación de tareas.
- Debido a que las operaciones en cola tienen una complejidad temporal de O(1), se pueden ejecutar rápidamente incluso en colas enormes.
- Las colas son particularmente flexibles ya que pueden implementarse simplemente usando una matriz o una lista vinculada.
Desventajas:
- Una cola, a diferencia de una pila, no se puede construir con un solo puntero, lo que hace que la implementación de la cola sea un poco más complicada.
- Si la cola se construye como una matriz, es posible que pronto se llene si se agregan demasiados elementos, lo que provocará problemas de rendimiento o posiblemente un bloqueo.
- Cuando se utiliza una lista vinculada para implementar la cola, la sobrecarga de memoria de cada nodo puede ser significativa, especialmente para elementos pequeños.
Conclusión:
Las aplicaciones que utilizan colas, una estructura de datos crucial, incluyen sistemas operativos, redes y juegos, por nombrar sólo algunas. Son ideales para algoritmos que deben manejar elementos en un orden particular, ya que son fáciles de crear utilizando una matriz o una lista vinculada. Sin embargo, las colas tienen desventajas que deben considerarse al seleccionar una estructura de datos para una aplicación en particular, como el consumo de memoria y la complejidad de la implementación.