Similar a la cola, es una estructura de datos lineal que sigue un orden particular en el que se realizan las operaciones para almacenar datos. El orden es primero en entrar, primero en salir. (FIFO) . Uno puede imaginar una cola como una fila de personas esperando recibir algo en orden secuencial que comienza desde el principio de la fila. Es una lista ordenada en la que las inserciones se realizan en un extremo que se conoce como posterior y las eliminaciones se realizan desde el otro extremo conocido como frontal. Un buen ejemplo de cola es cualquier cola de consumidores de un recurso en la que el consumidor que llegó primero recibe el servicio primero.
La diferencia entre pilas y colas está en la eliminación. En una pila eliminamos el elemento agregado más recientemente; en una cola, eliminamos el elemento agregado menos recientemente.
Estructura de datos de cola
Operaciones básicas en cola:
- enqueue(): inserta un elemento al final de la cola, es decir, en la parte posterior. dequeue(): esta operación elimina y devuelve un elemento que se encuentra al principio de la cola. front(): esta operación devuelve el elemento en el front-end sin eliminarlo. rear(): esta operación devuelve el elemento en la parte trasera sin eliminarlo. isEmpty(): esta operación indica si la cola está vacía o no. isFull(): Esta operación indica si la cola está llena o no. size(): esta operación devuelve el tamaño de la cola, es decir, el número total de elementos que contiene.
Tipos de colas:
- Cola simple: la cola simple, también conocida como cola lineal, es la versión más básica de una cola. Aquí, la inserción de un elemento, es decir, la operación Enqueue, se lleva a cabo en el extremo posterior y la eliminación de un elemento, es decir, la operación Dequeue, se lleva a cabo en el extremo frontal. Aquí el problema es que si sacamos algún elemento del frente y luego alcanzamos la capacidad de la cola y, aunque hay espacios vacíos antes del frente, significa que la cola no está llena, pero según la condición en la función isFull(), mostrará que el La cola está llena entonces. Para resolver este problema utilizamos cola circular.
- Cola circular : En una cola circular, el elemento de la cola actúa como un anillo circular. El funcionamiento de una cola circular es similar al de una cola lineal excepto por el hecho de que el último elemento está conectado al primer elemento. Su ventaja es que la memoria se utiliza de mejor manera. Esto se debe a que si hay un espacio vacío, es decir, si no hay ningún elemento presente en una determinada posición de la cola, entonces se puede agregar fácilmente un elemento en esa posición usando el módulo de capacidad ( %norte ).
- Cola de prioridad : Esta cola es un tipo especial de cola. Su especialidad es que organiza los elementos en una cola según alguna prioridad. La prioridad puede ser algo en lo que el elemento con el valor más alto tenga prioridad, por lo que crea una cola con orden decreciente de valores. La prioridad también puede ser tal que el elemento con el valor más bajo obtenga la prioridad más alta, por lo que a su vez crea una cola con un orden creciente de valores. En la cola de prioridad predefinida, C++ da prioridad al valor más alto mientras que Java da prioridad al valor más bajo.
- Respectivamente : La retirada de cola también se conoce como cola de doble extremo. Como sugiere el nombre, de doble extremo, significa que un elemento se puede insertar o eliminar de ambos extremos de la cola, a diferencia de otras colas en las que solo se puede hacer desde un extremo. Debido a esta propiedad, es posible que no obedezca la propiedad Primero en entrar, primero en salir.
Aplicaciones de cola:
La cola se utiliza cuando las cosas no tienen que procesarse inmediatamente, pero deben procesarse en F primero I norte F primero oh ut orden como Primera búsqueda en amplitud . Esta propiedad de Queue también la hace útil en los siguientes tipos de escenarios.
- Cuando un recurso se comparte entre varios consumidores. Los ejemplos incluyen programación de CPU, programación de disco. Cuando los datos se transfieren de forma asincrónica (los datos no necesariamente se reciben al mismo ritmo que se envían) entre dos procesos. Los ejemplos incluyen búferes de IO, canalizaciones, IO de archivos, etc. La cola se puede utilizar como un componente esencial en varias otras estructuras de datos.
Implementación de matriz de cola:
Para implementar la cola, debemos realizar un seguimiento de dos índices, el delantero y el trasero. Ponemos en cola un artículo en la parte trasera y retiramos un artículo del frente. Si simplemente incrementamos los índices delantero y trasero, entonces puede haber problemas, el frente puede llegar al final de la matriz. La solución a este problema es aumentar la parte delantera y trasera de forma circular.
Pasos para poner en cola:
- Comprueba que la cola está llena o no.
- Si está lleno, imprima el desbordamiento y salga
- Si la cola no está llena, incremente tail y agregue el elemento
Pasos para quitar la cola:
- La cola de verificación está vacía o no
- si está vacío, imprima el subdesbordamiento y salga
- si no está vacío, imprima el elemento en el encabezado e incremente el encabezado
A continuación se muestra un programa para implementar la operación anterior en la cola.
C++
// CPP program for array> // implementation of queue> #include> using> namespace> std;> // A structure to represent a queue> class> Queue {> public>:> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> Queue* createQueue(unsigned capacity)> {> >Queue* queue =>new> Queue();> >queue->capacidad = capacidad;> >queue->frente = cola->tamaño = 0;> >// This is important, see the enqueue> >queue->trasero = capacidad - 1;> >queue->matriz =>new> int>[queue->capacidad];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->tamaño == cola->capacidad);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->tamaño == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->trasero = (cola->trasero + 1)> >% queue->capacidad;> >queue->matriz[cola->trasera] = elemento;> >queue->tamaño = cola->tamaño + 1;> >cout << item <<>' enqueued to queue
'>;> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->matriz[cola->frente];> >queue->frente = (cola->frente + 1)> >% queue->capacidad;> >queue->tamaño = cola->tamaño - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matriz[cola->frente];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matriz[cola->trasero];> }> // Driver code> int> main()> {> >Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >cout << dequeue(queue)> ><<>' dequeued from queue
'>;> >cout <<>'Front item is '> ><< front(queue) << endl;> >cout <<>'Rear item is '> ><< rear(queue) << endl;> >return> 0;> }> // This code is contributed by rathbhupendra> |
>
>
C
bucle mecanografiado para cada uno
// C program for array implementation of queue> #include> #include> #include> // A structure to represent a queue> struct> Queue {> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> struct> Queue* createQueue(unsigned capacity)> {> >struct> Queue* queue = (>struct> Queue*)>malloc>(> >sizeof>(>struct> Queue));> >queue->capacidad = capacidad;> >queue->frente = cola->tamaño = 0;> >// This is important, see the enqueue> >queue->trasero = capacidad - 1;> >queue->matriz = (>int>*)>malloc>(> >queue->capacidad *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->tamaño == cola->capacidad);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->tamaño == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(>struct> Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->trasero = (cola->trasero + 1)> >% queue->capacidad;> >queue->matriz[cola->trasera] = elemento;> >queue->tamaño = cola->tamaño + 1;> >printf>(>'%d enqueued to queue
'>, item);> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->matriz[cola->frente];> >queue->frente = (cola->frente + 1)> >% queue->capacidad;> >queue->tamaño = cola->tamaño - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matriz[cola->frente];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matriz[cola->trasera];> }> // Driver program to test above functions./> int> main()> {> >struct> Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >printf>(>'%d dequeued from queue
'>,> >dequeue(queue));> >printf>(>'Front item is %d
'>, front(queue));> >printf>(>'Rear item is %d
'>, rear(queue));> >return> 0;> }> |
>
10 de 10
>
Java
// Java program for array> // implementation of queue> // A class to represent a queue> class> Queue {> >int> front, rear, size;> >int> capacity;> >int> array[];> >public> Queue(>int> capacity)> >{> >this>.capacity = capacity;> >front =>this>.size =>0>;> >rear = capacity ->1>;> >array =>new> int>[>this>.capacity];> >}> >// Queue is full when size becomes> >// equal to the capacity> >boolean> isFull(Queue queue)> >{> >return> (queue.size == queue.capacity);> >}> >// Queue is empty when size is 0> >boolean> isEmpty(Queue queue)> >{> >return> (queue.size ==>0>);> >}> >// Method to add an item to the queue.> >// It changes rear and size> >void> enqueue(>int> item)> >{> >if> (isFull(>this>))> >return>;> >this>.rear = (>this>.rear +>1>)> >%>this>.capacity;> >this>.array[>this>.rear] = item;> >this>.size =>this>.size +>1>;> >System.out.println(item> >+>' enqueued to queue'>);> >}> >// Method to remove an item from queue.> >// It changes front and size> >int> dequeue()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >int> item =>this>.array[>this>.front];> >this>.front = (>this>.front +>1>)> >%>this>.capacity;> >this>.size =>this>.size ->1>;> >return> item;> >}> >// Method to get front of queue> >int> front()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.front];> >}> >// Method to get rear of queue> >int> rear()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.rear];> >}> }> // Driver class> public> class> Test {> >public> static> void> main(String[] args)> >{> >Queue queue =>new> Queue(>1000>);> >queue.enqueue(>10>);> >queue.enqueue(>20>);> >queue.enqueue(>30>);> >queue.enqueue(>40>);> >System.out.println(queue.dequeue()> >+>' dequeued from queue
'>);> >System.out.println(>'Front item is '> >+ queue.front());> >System.out.println(>'Rear item is '> >+ queue.rear());> >}> }> // This code is contributed by Gaurav Miglani> |
>
>
Python3
# Python3 program for array implementation of queue> # Class Queue to represent a queue> class> Queue:> ># __init__ function> >def> __init__(>self>, capacity):> >self>.front>=> self>.size>=> 0> >self>.rear>=> capacity>->1> >self>.Q>=> [>None>]>*>capacity> >self>.capacity>=> capacity> > ># Queue is full when size becomes> ># equal to the capacity> >def> isFull(>self>):> >return> self>.size>=>=> self>.capacity> > ># Queue is empty when size is 0> >def> isEmpty(>self>):> >return> self>.size>=>=> 0> ># Function to add an item to the queue.> ># It changes rear and size> >def> EnQueue(>self>, item):> >if> self>.isFull():> >print>(>'Full'>)> >return> >self>.rear>=> (>self>.rear>+> 1>)>%> (>self>.capacity)> >self>.Q[>self>.rear]>=> item> >self>.size>=> self>.size>+> 1> >print>(>'% s enqueued to queue'> %> str>(item))> ># Function to remove an item from queue.> ># It changes front and size> >def> DeQueue(>self>):> >if> self>.isEmpty():> >print>(>'Empty'>)> >return> > >print>(>'% s dequeued from queue'> %> str>(>self>.Q[>self>.front]))> >self>.front>=> (>self>.front>+> 1>)>%> (>self>.capacity)> >self>.size>=> self>.size>->1> > ># Function to get front of queue> >def> que_front(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Front item is'>,>self>.Q[>self>.front])> > ># Function to get rear of queue> >def> que_rear(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Rear item is'>,>self>.Q[>self>.rear])> # Driver Code> if> __name__>=>=> '__main__'>:> >queue>=> Queue(>30>)> >queue.EnQueue(>10>)> >queue.EnQueue(>20>)> >queue.EnQueue(>30>)> >queue.EnQueue(>40>)> >queue.DeQueue()> >queue.que_front()> >queue.que_rear()> |
>
>
C#
// C# program for array implementation of queue> using> System;> namespace> GeeksForGeeks {> // A class to represent a linearqueue> class> Queue {> >private> int>[] ele;> >private> int> front;> >private> int> rear;> >private> int> max;> >public> Queue(>int> size)> >{> >ele =>new> int>[size];> >front = 0;> >rear = -1;> >max = size;> >}> >// Function to add an item to the queue.> >// It changes rear and size> >public> void> enqueue(>int> item)> >{> >if> (rear == max - 1) {> >Console.WriteLine(>'Queue Overflow'>);> >return>;> >}> >else> {> >ele[++rear] = item;> >}> >}> >// Function to remove an item from queue.> >// It changes front and size> >public> int> dequeue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return> -1;> >}> >else> {> >Console.WriteLine(ele[front] +>' dequeued from queue'>);> >int> p = ele[front++];> >Console.WriteLine();> >Console.WriteLine(>'Front item is {0}'>, ele[front]);> >Console.WriteLine(>'Rear item is {0} '>, ele[rear]);> >return> p;> >}> >}> >// Function to print queue.> >public> void> printQueue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return>;> >}> >else> {> >for> (>int> i = front; i <= rear; i++) {> >Console.WriteLine(ele[i] +>' enqueued to queue'>);> >}> >}> >}> }> // Driver code> class> Program {> >static> void> Main()> >{> >Queue Q =>new> Queue(5);> >Q.enqueue(10);> >Q.enqueue(20);> >Q.enqueue(30);> >Q.enqueue(40);> >Q.printQueue();> >Q.dequeue();> >}> }> }> |
>
>
JavaScript
> // Queue class> class Queue> {> >// Array is used to implement a Queue> >constructor()> >{> >this>.items = [];> >}> >isEmpty()> >{> >// return true if the queue is empty.> >return> this>.items.length == 0;> >}> >enqueue(element)> >{> >// adding element to the queue> >this>.items.push(element);> >document.write(element +>' enqueued to queue '>);> >}> >dequeue()> >{> >// removing element from the queue> >// returns underflow when called> >// on empty queue> >if>(>this>.isEmpty())> >return> 'Underflow '>;> >return> this>.items.shift();> >}> >front()> >{> >// returns the Front element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[0];> >}> >rear()> >{> >// returns the Rear element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[>this>.items.length-1];> >}> }> // creating object for queue class> var> queue =>new> Queue();> // Adding elements to the queue> queue.enqueue(10);> queue.enqueue(20);> queue.enqueue(30);> queue.enqueue(40);> // queue contains [10, 20, 30, 40]> // removes 10> document.write(queue.dequeue() +>' dequeued from queue '>);> // queue contains [20, 30, 40]> // Front is now 20> document.write(>'Front item is '> + queue.front() +>' '>);> // printing the rear element> // Rear is 40> document.write(>'Rear item is '> + queue.rear() +>' '>);> // This code is contributed by Susobhan Akhuli> > |
>
>Producción
clase de escáner java
10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40>
Análisis de complejidad:
- Complejidad del tiempo
| Operaciones | Complejidad |
|---|---|
| Poner en cola (inserción) | O(1) |
| Deque(eliminación) | O(1) |
| Frente (Ponte al frente) | O(1) |
| Trasero(Ponte atrás) | O(1) |
| IsFull (comprobar que la cola esté llena o no) | O(1) |
| IsEmpty (Comprobar que la cola está vacía o no) | O(1) |
- Espacio Auxiliar:
O(N) donde N es el tamaño de la matriz para almacenar elementos.
Ventajas de la implementación de matrices:
- Fácil de implementar.
- Se puede gestionar una gran cantidad de datos de forma eficiente y sencilla.
- Operaciones como la inserción y eliminación se pueden realizar con facilidad ya que sigue la regla de primero en entrar, primero en salir.
Desventajas de la implementación de matrices:
- Estructura de datos estática, tamaño fijo.
- Si la cola tiene una gran cantidad de operaciones de poner y quitar la cola, en algún momento (en el caso de un incremento lineal de los índices frontal y posterior) es posible que no podamos insertar elementos en la cola incluso si la cola está vacía (este problema se evita mediante el uso de cola circular).
- El tamaño máximo de una cola debe definirse previamente.