En este tutorial, aprenderá qué es una cola. Además, encontrará la implementación de la cola en C, C ++, Java y Python.
Una cola es una estructura de datos útil en programación. Es similar a la cola de boletos fuera de una sala de cine, donde la primera persona que ingresa a la fila es la primera persona que obtiene el boleto.
La cola sigue la regla Primero en entrar, primero en salir (FIFO) : el elemento que entra primero es el elemento que sale primero.
Representación FIFO de cola
En la imagen de arriba, dado que 1 se mantuvo en la cola antes que 2, también es el primero en ser eliminado de la cola. Sigue la regla FIFO .
En términos de programación, poner elementos en la cola se llama poner en cola y eliminar elementos de la cola se llama sacar de cola .
Podemos implementar la cola en cualquier lenguaje de programación como C, C ++, Java, Python o C #, pero la especificación es prácticamente la misma.
Operaciones básicas de cola
Una cola es un objeto (una estructura de datos abstracta - ADT) que permite las siguientes operaciones:
- Enqueue : agrega un elemento al final de la cola
- Dequeue : elimina un elemento del frente de la cola
- IsEmpty : comprueba si la cola está vacía
- IsFull : comprueba si la cola está llena
- Peek : obtenga el valor del frente de la cola sin eliminarlo
Trabajo de cola
Las operaciones de cola funcionan de la siguiente manera:
- dos punteros DELANTERO y TRASERO
- FRENTE rastrea el primer elemento de la cola
- REAR rastrea el último elemento de la cola
- inicialmente, establezca el valor de FRONT y REAR en -1
Operación de puesta en cola
- compruebe si la cola está llena
- para el primer elemento, establezca el valor de FRONT en 0
- aumentar el índice TRASERO en 1
- agregue el nuevo elemento en la posición señalada por REAR
Operación Dequeue
- comprobar si la cola está vacía
- devuelve el valor señalado por FRONT
- aumentar el índice FRONTAL en 1
- para el último elemento, restablezca los valores de FRONT y REAR a -1
Operaciones de poner en cola y sacar de cola
Implementaciones de cola en Python, Java, C y C ++
Por lo general, usamos matrices para implementar colas en Java y C / ++. En el caso de Python, usamos listas.
Python Java C C ++ # Queue implementation in Python class Queue: def __init__(self): self.queue = () # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display()
// Queue implementation in Java public class Queue ( int SIZE = 5; int items() = new int(SIZE); int front, rear; Queue() ( front = -1; rear = -1; ) boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) boolean isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear++; items(rear) = element; System.out.println("Inserted " + element); ) ) int deQueue() ( int element; if (isEmpty()) ( System.out.println("Queue is empty"); return (-1); ) else ( element = items(front); if (front>= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) System.out.println("Deleted -> " + element); return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front index-> " + front); System.out.println("Items -> "); for (i = front; i " + rear); ) ) public static void main(String() args) ( Queue q = new Queue(); // deQueue is not possible on empty queue q.deQueue(); // enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); // deQueue removes element entered first i.e. 1 q.deQueue(); // Now we have just 4 elements q.display(); ) )
// Queue implementation in C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items(SIZE), front = -1, rear = -1; int main() ( //deQueue is not possible on empty queue deQueue(); //enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // 6th element can't be added to because the queue is full enQueue(6); display(); //deQueue removes element entered first i.e. 1 deQueue(); //Now we have just 4 elements display(); return 0; ) void enQueue(int value) ( if (rear == SIZE - 1) printf("Queue is Full!!"); else ( if (front == -1) front = 0; rear++; items(rear) = value; printf("Inserted -> %d", value); ) ) void deQueue() ( if (front == -1) printf("Queue is Empty!!"); else ( printf("Deleted : %d", items(front)); front++; if (front> rear) front = rear = -1; ) ) // Function to print the queue void display() ( if (rear == -1) printf("Queue is Empty!!!"); else ( int i; printf("Queue elements are:"); for (i = front; i <= rear; i++) printf("%d ", items(i)); ) printf(""); )
// Queue implementation in C++ #include #define SIZE 5 using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) bool isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear++; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) int deQueue() ( int element; if (isEmpty()) ( cout << "Queue is empty" <= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) cout << endl < " << element << endl; return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout << endl < " << front; cout << endl < "; for (i = front; i <= rear; i++) cout << items(i) << " "; cout << endl < " << rear << endl; ) ) ); int main() ( Queue q; //deQueue is not possible on empty queue q.deQueue(); //enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); //deQueue removes element entered first i.e. 1 q.deQueue(); //Now we have just 4 elements q.display(); return 0; )
Limitaciones de la cola
Como puede ver en la imagen de abajo, después de poner y quitar la cola un poco, el tamaño de la cola se ha reducido.
Limitación de una cola
Y solo podemos agregar los índices 0 y 1 solo cuando la cola se restablece (cuando todos los elementos se han eliminado de la cola).
Una vez que REAR alcanza el último índice, si podemos almacenar elementos adicionales en los espacios vacíos (0 y 1), podemos hacer uso de los espacios vacíos. Esto se implementa mediante una cola modificada llamada cola circular.
Análisis de complejidad
La complejidad de las operaciones de poner en cola y sacar de cola en una cola usando una matriz es O(1).
Aplicaciones de la cola
- Programación de CPU, Programación de disco
- Cuando los datos se transfieren de forma asíncrona entre dos procesos, la cola se utiliza para la sincronización. Por ejemplo: IO Buffers, pipe, file IO, etc.
- Manejo de interrupciones en sistemas en tiempo real.
- Los sistemas telefónicos del centro de llamadas usan Colas para mantener en orden a las personas que los llaman.
Lecturas recomendadas
- Tipos de cola
- Cola circular
- Estructura de datos Deque
- Cola de prioridad
