Las colas o queue son similares a las pilas, en que son estructuras de datos lineales que siguen un cierto patrón al organizar y realizar operaciones en elementos, y el orden en las colas es primero en entrar, primero en salir (FIFO para abreviar). El mejor ejemplo de una cola es la cola de los consumidores que se paran en el cajero en las tiendas, la primera persona en entrar en la cola es la primera persona en salir después de pagar la factura. De aquí se puede saber que la diferencia entre la cola y la pila está en la salida de los elementos, ya que el último elemento agregado a la pila es el que saldrá primero, y el último elemento agregado a la cola es el uno que saldrá último.
Tabla de contenidos
- Operaciones básicas de las colas (queue)
- Creando colas usando arreglos
- Crear colas usando listas encadenadas
- Creando una cola usando la pila
- Fuentes del Artículo
Operaciones básicas de las colas (queue)
En general, se pueden realizar cuatro operaciones básicas en las colas:
Enqueue : esta operación agrega un elemento a la cola y, si la cola está llena, la condición se denomina desbordamiento.
Dequeue : esta operación elimina un elemento de la cola y los elementos se eliminan de la cola en el mismo orden en que se agregaron. Si la cola está vacía, el estado se llama undeflow.
Front : este proceso puede obtener el elemento frontal en el marco.
Rear : este proceso puede obtener el elemento trasero en la cola.
Aplicaciones básicas
Las colas se usan cuando no hay necesidad de tratar las cosas directamente, sino que se tratan en orden (primero en entrar, primero en salir) como el algoritmo Breadth First Search, y esta característica hace que las colas sean útiles en los siguientes casos:
- Cuando el recurso es compartido por varios consumidores, como el programa de la CPU, el programa del disco duro.
- Cuando los datos se transfieren de forma asincrónica (es decir, la velocidad de recepción de datos no es necesariamente igual a la velocidad de su transmisión) entre dos procesos, como búfer de E/S de entrada y salida de memoria, conductos, entrada y salida de E/S de archivo, y otros.
Creando colas usando arreglos
Se deben seguir dos de los índices de la matriz al usarlos para crear colas, a saber, el primer y el último índice, ya que los elementos se agregan al final de la matriz y se eliminan del principio de la matriz. Puede sonar simple, pero incrementar el primer y el último índice puede causar el problema de que el primer puntero alcance el final de la matriz. Para resolver este problema, los índices primero y último deben incrementarse en forma circular.
complejidad del tiempo
La complejidad temporal de todas las operaciones de la cola, como enqueue(), dequeue(), isFull(), isEmpty()porque no se utilizan bucles al ejecutar estas operaciones front()rear().
Ejemplos y aplicaciones en código
Los siguientes ejemplos muestran cómo crear colas utilizando matrices en varios lenguajes de programación:
// CPP program for array
// implementation of queue
#include <bits/stdc++.h>
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->capacity = capacity;
queue->front = queue->size = 0;
// This is important, see the enqueue
queue->rear = capacity - 1;
queue->array = new int[queue->capacity];
return queue;
}
// Queue is full when size
// becomes equal to the capacity
int isFull(Queue* queue)
{
return (queue->size == queue->capacity);
}
// Queue is empty when size is 0
int isEmpty(Queue* queue)
{
return (queue->size == 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->rear = (queue->rear + 1)
% queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
cout << item << " enqueued to queue\n";
}
// 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->array[queue->front];
queue->front = (queue->front + 1)
% queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Function to get front of queue
int front(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
// Function to get rear of queue
int rear(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
// 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\n";
cout << "Front item is "
<< front(queue) << endl;
cout << "Rear item is "
<< rear(queue) << endl;
return 0;
}# 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()// 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\n");
System.out.println("Front item is "
+ queue.front());
System.out.println("Rear item is "
+ queue.rear());
}
}El código anterior da el siguiente resultado:
10 en cola en cola 20 en cola en cola 30 en cola en cola 40 en cola en cola 10 eliminados de la cola El artículo delantero es 20 El artículo trasero es 40
Crear colas usando listas encadenadas
Se deben tener en cuenta dos punteros cuando se usan listas encadenadas para crear colas, el cursor hacia adelante fronty hacia atrás rear. El puntero frontal indica el primer elemento del marco y el puntero posterior indica el último elemento del marco.
OperaciónenQueue() : esta operación agrega un nuevo nodo después del cursor de retroceso y lo mueve al siguiente nodo.
OperacióndeQueue() : esta operación elimina el nodo de avance y mueve el cursor de avance a los siguientes nodos.
complejidad del tiempo
La complejidad temporal de las dos enqueue()operaciones dequeue()se O(1)debe a que las dos operaciones modifican una pequeña cantidad de punteros y no se utilizan bucles en ninguna de ellas.
Ejemplos y aplicaciones en código
Los siguientes ejemplos muestran cómo se usan las listas encadenadas para crear colas en varios lenguajes de programación:
#include <bits/stdc++.h>
using namespace std;
struct QNode {
int data;
QNode* next;
QNode(int d)
{
data = d;
next = NULL;
}
};
struct Queue {
QNode *front, *rear;
Queue()
{
front = rear = NULL;
}
void enQueue(int x)
{
// Create a new LL node
QNode* temp = new QNode(x);
// If queue is empty, then
// new node is front and rear both
if (rear == NULL) {
front = rear = temp;
return;
}
// Add the new node at
// the end of queue and change rear
rear->next = temp;
rear = temp;
}
// Function to remove
// a key from given queue q
void deQueue()
{
// If queue is empty, return NULL.
if (front == NULL)
return;
// Store previous front and
// move front one node ahead
QNode* temp = front;
front = front->next;
// If front becomes NULL, then
// change rear also as NULL
if (front == NULL)
rear = NULL;
delete (temp);
}
};
// Driven Program
int main()
{
Queue q;
q.enQueue(10);
q.enQueue(20);
q.deQueue();
q.deQueue();
q.enQueue(30);
q.enQueue(40);
q.enQueue(50);
q.deQueue();
cout << "Queue Front : " << (q.front)->data << endl;
cout << "Queue Rear : " << (q.rear)->data;
}# Python3 program to demonstrate linked list
# based implementation of queue
# A linked list (LL) node
# to store a queue entry
class Node:
def __init__(self, data):
self.data = data
self.next = None
# A class to represent a queue
# The queue, front stores the front node
# of LL and rear stores the last node of LL
class Queue:
def __init__(self):
self.front = self.rear = None
def isEmpty(self):
return self.front == None
# Method to add an item to the queue
def EnQueue(self, item):
temp = Node(item)
if self.rear == None:
self.front = self.rear = temp
return
self.rear.next = temp
self.rear = temp
# Method to remove an item from queue
def DeQueue(self):
if self.isEmpty():
return
temp = self.front
self.front = temp.next
if(self.front == None):
self.rear = None
# Driver Code
if __name__== '__main__':
q = Queue()
q.EnQueue(10)
q.EnQueue(20)
q.DeQueue()
q.DeQueue()
q.EnQueue(30)
q.EnQueue(40)
q.EnQueue(50)
q.DeQueue()
print("Queue Front " + str(q.front.data))
print("Queue Rear " + str(q.rear.data))// Java program for linked-list implementation of queue
// A linked list (LL) node to store a queue entry
class QNode {
int key;
QNode next;
// constructor to create a new linked list node
public QNode(int key){
this.key = key;
this.next = null;
}
}
// A class to represent a queue
// The queue, front stores the front node of LL and rear stores the
// last node of LL
class Queue {
QNode front, rear;
public Queue(){
this.front = this.rear = null;
}
// Method to add an key to the queue.
void enqueue(int key){
// Create a new LL node
QNode temp = new QNode(key);
// If queue is empty, then new node is front and rear both
if (this.rear == null) {
this.front = this.rear = temp;
return;
}
// Add the new node at the end of queue and change rear
this.rear.next = temp;
this.rear = temp;
}
// Method to remove an key from queue.
void dequeue(){
// If queue is empty, return NULL.
if (this.front == null)
return;
// Store previous front and move front one node ahead
QNode temp = this.front;
this.front = this.front.next;
// If front becomes NULL, then change rear also as NULL
if (this.front == null)
this.rear = null;
}
}
// Driver class
public class Test {
public static void main(String[] args){
Queue q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.dequeue();
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
q.dequeue();
System.out.println("Queue Front : " + q.front.key);
System.out.println("Queue Rear : " + q.rear.key);
}
}Creando una cola usando la pila
La cola se puede crear usando dos pilas, si asumimos que la cola que se va a crear es q y que las dos pilas usadas son stack1 y stack2. La cola se puede crear de tres maneras:
El primer método: confiar en el proceso enqueue()
En este método, nos aseguramos de que el último elemento ingresado sea el elemento más alto en la primera pila, por lo que el proceso deQueue()elimina solo los elementos de la primera pila y usa la segunda pila para colocar el elemento en la parte superior de la primera pila.
Este método se puede resumir en los siguientes pasos:
enQueue(q,x):
- Empuje todo, desde la primera pila hasta la segunda pila, siempre que la primera pila no esté vacía.
- Inserte el elemento
xen la primera pila (suponiendo que no se especifican ambos tamaños de pila). - Empuje todo en la primera pila.
La complejidad temporal de este proceso será O(n).
dequeue(q):
- Si la primera pila está vacía, la función arroja un error.
- Quita un elemento de la primera pila y devuélvelo.
La complejidad temporal de este proceso es O(1).
Ejemplos y aplicaciones en código
Los siguientes ejemplos muestran el primer método para crear una cola usando pilas y en varios lenguajes de programación:
// CPP program to implement Queue using
// two stacks with costly enQueue()
#include <bits/stdc++.h>
using namespace std;
struct Queue {
stack<int> s1, s2;
void enQueue(int x)
{
// Move all elements from s1 to s2
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
// Push item into s1
s1.push(x);
// Push everything back to s1
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
}
// Dequeue an item from the queue
int deQueue()
{
// if first stack is empty
if (s1.empty()) {
cout << "Q is Empty";
exit(0);
}
// Return top of s1
int x = s1.top();
s1.pop();
return x;
}
}
// Driver code
int main()
{
Queue q;
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
return 0;
}# Python3 program to implement Queue using
# two stacks with costly enQueue()
class Queue:
def __init__(self):
self.s1 = []
self.s2 = []
def enQueue(self, x):
# Move all elements from s1 to s2
while len(self.s1) != 0:
self.s2.append(self.s1[-1])
self.s1.pop()
# Push item into self.s1
self.s1.append(x)
# Push everything back to s1
while len(self.s2) != 0:
self.s1.append(self.s2[-1])
self.s2.pop()
# Dequeue an item from the queue
def deQueue(self):
# if first stack is empty
if len(self.s1) == 0:
print("Q is Empty")
# Return top of self.s1
x = self.s1[-1]
self.s1.pop()
return x
# Driver code
if __name__ == '__main__':
q = Queue()
q.enQueue(1)
q.enQueue(2)
q.enQueue(3)
print(q.deQueue())
print(q.deQueue())
print(q.deQueue())// Java program to implement Queue using
// two stacks with costly enQueue()
import java.util.*;
class GFG{
static class Queue{
static Stack<Integer> s1 = new Stack<Integer>();
static Stack<Integer> s2 = new Stack<Integer>();
static void enQueue(int x){
// Move all elements from s1 to s2
while (!s1.isEmpty()){
s2.push(s1.pop());
//s1.pop();
}
// Push item into s1
s1.push(x);
// Push everything back to s1
while (!s2.isEmpty()){
s1.push(s2.pop());
//s2.pop();
}
}
// Dequeue an item from the queue
static int deQueue(){
// if first stack is empty
if (s1.isEmpty()){
System.out.println("Q is Empty");
System.exit(0);
}
// Return top of s1
int x = s1.peek();
s1.pop();
return x;
}
}
// Driver code
public static void main(String[] args){
Queue q = new Queue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
System.out.println(q.deQueue());
System.out.println(q.deQueue());
System.out.println(q.deQueue());
}
}El código anterior da el siguiente resultado:
1 2 3
El segundo método: confiar en el proceso deQueue
El nuevo elemento se inserta en la parte superior de la primera pila mediante un proceso enQueue, y un proceso dequeueverifica si la segunda pila está vacía o no. Si es así, todos los elementos se mueven a la segunda pila y el proceso devuelve el elemento más alto en ella.
Este método se puede resumir en los siguientes pasos:
enQueue(q, x)- Agregue el elemento
xa la primera pila (suponiendo que las dos pilas tengan un tamaño ilimitado). La complejidad temporal de este proceso esO(1).
- Agregue el elemento
deQueue(q):- Si las pilas están vacías, el proceso arroja un error.
- Si la segunda pila está vacía y la primera pila no lo está, la función moverá todos los elementos de la primera pila a la segunda pila.
- La función elimina y devuelve la parte superior del segundo elemento de la pila.La complejidad temporal de este proceso es
O(n).
Vale la pena señalar que el segundo método es mucho mejor que el primero, porque el primer método mueve todos los elementos dos veces en una operación enQueue, mientras que el segundo método mueve los elementos una vez y solo cuando la segunda pila está vacía.
Ejemplos y aplicaciones en código
Los siguientes ejemplos muestran cómo se implementa el segundo método en varios lenguajes de programación:
// CPP program to implement Queue using
// two stacks with costly deQueue()
#include <bits/stdc++.h>
using namespace std;
struct Queue {
stack<int> s1, s2;
// Enqueue an item to the queue
void enQueue(int x){
// Push item into the first stack
s1.push(x);
}
// Dequeue an item from the queue
int deQueue(){
// if both stacks are empty
if (s1.empty() && s2.empty()) {
cout << "Q is empty";
exit(0);
}
// if s2 is empty, move
// elements from s1
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
// return the top item from s2
int x = s2.top();
s2.pop();
return x;
}
}
// Driver code
int main(){
Queue q;
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
return 0;
}Observe que el código usa la clase Stackpara crear las pilas:
/* Java Program to implement a queue using two stacks */
// Note that Stack class is used for Stack implementation
import java.util.Stack;
public class GFG {
/* class of queue having two stacks */
static class Queue {
Stack<Integer> stack1;
Stack<Integer> stack2;
}
/* Function to push an item to stack*/
static void push(Stack<Integer> top_ref, int new_data)
{
// Push the data onto the stack
top_ref.push(new_data);
}
/* Function to pop an item from stack*/
static int pop(Stack<Integer> top_ref)
{
/*If stack is empty then error */
if (top_ref.isEmpty()) {
System.out.println("Stack Underflow");
System.exit(0);
}
// pop the data from the stack
return top_ref.pop();
}
// Function to enqueue an item to the queue
static void enQueue(Queue q, int x)
{
push(q.stack1, x);
}
/* Function to deQueue an item from queue */
static int deQueue(Queue q)
{
int x;
/* If both stacks are empty then error */
if (q.stack1.isEmpty() && q.stack2.isEmpty()) {
System.out.println("Q is empty");
System.exit(0);
}
/* Move elements from stack1 to stack 2 only if
stack2 is empty */
if (q.stack2.isEmpty()) {
while (!q.stack1.isEmpty()) {
x = pop(q.stack1);
push(q.stack2, x);
}
}
x = pop(q.stack2);
return x;
}
/* Driver function to test above functions */
public static void main(String args[])
{
/* Create a queue with items 1 2 3*/
Queue q = new Queue();
q.stack1 = new Stack<>();
q.stack2 = new Stack<>();
enQueue(q, 1);
enQueue(q, 2);
enQueue(q, 3);
/* Dequeue items */
System.out.print(deQueue(q) + " ");
System.out.print(deQueue(q) + " ");
System.out.println(deQueue(q) + " ");
}
}El código anterior da el siguiente resultado:
1 2 3
Método 3: usar una sola pila junto con la pila de llamadas a funciones
Se puede crear una cola utilizando una sola pila junto con la pila de funciones de llamadas, y este método se puede resumir en los siguientes pasos:
enQueue(x)- Agregue el elemento
xa la primera pila.
- Agregue el elemento
deQueue:- Lanzamos un error si la primera pila está vacía.
- Si solo hay un elemento en la primera pila, devolvemos ese elemento.
- Eliminamos todo de la primera pila de forma recursiva, luego almacenamos los elementos eliminados en una variable y luego los devolvemos a la primera pila y devolvemos el valor de la variable.
El paso 3 garantiza devolver el último elemento eliminado de la cola, y dado que la recursividad se detendrá cuando el número de elementos en la primera pila llegue a uno (paso 2), obtendremos el último elemento en la primera pila usando la función deQueue()y devolveremos el resto de los elementos a la primera pila en el Paso 3.
Ejemplos y aplicaciones en código
Los siguientes ejemplos muestran cómo se implementa el tercer método en varios lenguajes de programación:
// CPP program to implement Queue using
// one stack and recursive call stack.
#include <bits/stdc++.h>
using namespace std;
struct Queue {
stack<int> s;
// Enqueue an item to the queue
void enQueue(int x)
{
s.push(x);
}
// Dequeue an item from the queue
int deQueue()
{
if (s.empty()) {
cout << "Q is empty";
exit(0);
}
// pop an item from the stack
int x = s.top();
s.pop();
// if stack becomes empty, return
// the popped item
if (s.empty())
return x;
// recursive call
int item = deQueue();
// push popped item back to the stack
s.push(x);
// return the result of deQueue() call
return item;
}
};
// Driver code
int main()
{
Queue q;
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
return 0;
}// Java Program to implement a queue using one stack
import java.util.Stack;
public class QOneStack {
// class of queue having two stacks
static class Queue {
Stack<Integer> stack1;
}
/* Function to push an item to stack*/
static void push(Stack<Integer> top_ref, int new_data)
{
/* put in the data */
top_ref.push(new_data);
}
/* Function to pop an item from stack*/
static int pop(Stack<Integer> top_ref)
{
/*If stack is empty then error */
if (top_ref == null) {
System.out.println("Stack Underflow");
System.exit(0);
}
// return element from stack
return top_ref.pop();
}
/* Function to enqueue an item to queue */
static void enQueue(Queue q, int x)
{
push(q.stack1, x);
}
/* Function to deQueue an item from queue */
static int deQueue(Queue q)
{
int x, res = 0;
/* If the stacks is empty then error */
if (q.stack1.isEmpty()) {
System.out.println("Q is Empty");
System.exit(0);
}
// Check if it is a last element of stack
else if (q.stack1.size() == 1) {
return pop(q.stack1);
}
else {
/* pop an item from the stack1 */
x = pop(q.stack1);
/* store the last deQueued item */
res = deQueue(q);
/* push everything back to stack1 */
push(q.stack1, x);
return res;
}
return 0;
}
/* Driver function to test above functions */
public static void main(String[] args)
{
/* Create a queue with items 1 2 3*/
Queue q = new Queue();
q.stack1 = new Stack<>();
enQueue(q, 1);
enQueue(q, 2);
enQueue(q, 3);
/* Dequeue items */
System.out.print(deQueue(q) + " ");
System.out.print(deQueue(q) + " ");
System.out.print(deQueue(q) + " ");
}
}El código anterior da el siguiente resultado:
1 2 3
Fuentes del Artículo
- Página de documentación de estructuras de datos en GeeksforGeeks Conjunto 1 (Introducción e implementación de matriz).
- Página de documentación de estructuras de datos en GeeksforGeeks Conjunto 2 (Implementación de lista enlazada).
- Página de documentación de estructuras de datos en GeeksforGeeks Cola usando pilas.
