Implementación de colas en Python

1. Implementación de colas en Python
2. Agregar un elemento a la cola: la operación de poner en cola
3. Eliminar un elemento de la cola: la operación Dequeue
4. Otras operaciones en colas en Python
5. Implementación de colas usando listas en Python
6. Implementación de colas usando listas enlazadas en Python
7. Implementación de colas usando el módulo de colecciones en Python
8. Implementación de cola más eficiente en Python

Usamos colas en Python para realizar operaciones de primero en entrar, primero en salir (FIFO). Este artículo discutirá tres formas diferentes para la implementación de colas en Python.

Implementación de colas en Python

En una cola, podemos realizar diferentes operaciones. Analicemos primero el concepto general detrás de todas las operaciones y, después de eso, implementaremos las operaciones de cola usando varias construcciones.

El primer elemento de la cola se denomina elemento frontal. De manera similar, el último elemento de la cola se denomina elemento trasero.

Por ejemplo, considere la siguiente secuencia de números como una cola. 1 es el elemento delantero, mientras que 6 es el elemento trasero.

1,2,3,4,5,6

Agregar un elemento a la cola: la operación de poner en cola

En la operación de poner en cola, agregamos el elemento a la cola de la misma manera que una persona se une a una cola en un mostrador de boletos. El elemento recién agregado siempre se convierte en el elemento trasero.

Por ejemplo, si agregamos el número 7 a la cola dada arriba, la cola se verá como la siguiente.

1,2,3,4,5,6,7

Es esencial tener en cuenta que podemos agregar elementos solo al final de una cola.

Eliminar un elemento de la cola: la operación Dequeue

En la operación de eliminación de cola, eliminamos el elemento frontal de la cola de la misma manera que una persona sale de la cola después de recibir su boleto en el mostrador de boletos.

Después de una operación de eliminación de cola, el elemento frontal se elimina de la cola y el elemento detrás del elemento frontal se convierte en el nuevo elemento frontal. Por ejemplo, después de la operación de eliminación de cola, la cola utilizada en el ejemplo anterior se verá así.

2,3,4,5,6,7

Solo puede eliminar el elemento frontal en una operación de eliminación de cola. Las colas siempre siguen el orden de primeras entradas, primeras salidas. Por lo tanto, el elemento agregado primero a la cola también se elimina primero.

Otras operaciones en colas en Python

Si una cola no tiene ningún elemento, se dice que está vacía. Podemos usar diferentes enfoques para determinar si una cola está vacía en diferentes implementaciones.

A veces, es posible que también necesitemos encontrar la longitud de la cola. También discutiremos la implementación de esta operación.

Implementación de colas usando listas en Python

Podemos implementar colas en Python usando listas de la manera más simple. Para crear una cola usando listas,

1. Definimos una clase Cola con tres atributos.
2. Definimos una lista vacía data que almacenará los elementos de la lista.
3. Inicializamos dos variables, delantero y trasero.
4. Inicializamos las variables a -1 para mostrar que la cola está vacía.

Código:

class Queue:
    def __init__(self):
        self.data = list()
        self.front = -1
        self.rear = -1

Se crea una lista vacía y se le asigna el atributo datos al crear un objeto Cola. La lista luego almacena los elementos de la cola.

Después de crear la cola vacía, implementaremos diferentes operaciones en la cola.

Comprobar si la cola está vacía en Python

Para comprobar si la cola está vacía, podemos comprobar si los atributos, delantero y trasero, están inicializados a -1. Para ello, definiremos un método isEmpty().

El método isEmpty(), cuando se invoca en una cola, comprobará si los atributos delantero y trasero tienen el valor -1. En caso afirmativo, devolverá True, indicando que la cola está vacía; de lo contrario, devolverá False.

Código:

def isEmpty(self):
    if self.rear == -1 and self.front == -1:
        return True
    else:
        return False

Operación en cola usando listas en Python

Para insertar un elemento en la cola, primero comprobaremos si la cola está vacía. Podemos usar el método isEmpty() definido anteriormente.

1. Si la cola está vacía, agregaremos un elemento a la lista contenida en el atributo datos usando el método agregar (). Cuando se invoca en una lista, el método append() toma un elemento como argumento de entrada y lo agrega a la lista.
2. Ahora que solo hay un elemento en la lista, actualizaremos los valores de los atributos frente y trasero a 0. Tanto el elemento delantero como el trasero están presentes en el índice 0 en la lista datos.
3. Si la lista no está vacía, primero agregaremos el elemento a la lista usando el método append().
4. Después de eso, incrementaremos el valor en el atributo trasero mostrando que se ha agregado un elemento adicional a la cola.

En la operación de puesta en cola, el valor del atributo frente no cambiará ya que no estamos eliminando ningún elemento de la cola.

Toda la operación se puede implementar en Python de la siguiente manera.

Código:

def enQueue(self, element):
    if self.isEmpty():
        self.data.append(element)
        self.front = 0
        self.rear = 0
    else:
        self.data.append(element)
        self.rear += 1

Operación Dequeue usando listas en Python

Primero comprobaremos si la cola está vacía para la operación de eliminación de cola. Si es así, no podemos operar; de lo contrario, realizaremos lo siguiente.

1. Verificaremos si solo hay un elemento en la cola. Podemos comprobar si los atributos delantero y trasero tienen el mismo valor, y ninguno de ellos es -1.
2. Si la cola tiene solo un elemento, eliminaremos el elemento en el índice delantero de la cola utilizando el método pop() y se lo devolveremos al usuario. Luego, actualizaremos los atributos frente y trasero a -1, mostrando que la cola se ha quedado vacía.
3. Si ninguna de las condiciones anteriores es Verdadera, la cola tiene dos o más elementos. Almacenaremos el elemento en el índice delantero en una variable temporal en tal caso.
4. Después de eso, incrementaremos el valor en el atributo front, denotando que el siguiente elemento en la lista se ha convertido en el elemento front.
5. Finalmente, devolveremos el valor almacenado en la variable temporal.

Código:

def deQueue(self):
    if self.isEmpty():
        print("Queue is Empty. Cannot remove element")
    elif self.front == self.rear and self.front != -1:
        element = self.data[self.front]
        self.front = -1
        self.rear = -1
        return element
    else:
        element = self.data[self.front]
        self.front = self.front + 1
        return element

Encuentra la longitud de la cola en Python

Para encontrar la longitud de una cola en Python, podemos realizar los siguientes pasos.

1. Si la cola está vacía, la longitud de la cola será 0. Por lo tanto, primero comprobaremos si la cola está vacía utilizando el método isEmpty().
2. Si el método isEmpty() devuelve True, devolveremos 0 como la longitud de la cola.
3. En caso contrario, la longitud de la lista se calculará como trasera-delantera+1.

Como se muestra a continuación, hemos implementado esto en el método longitud().

Código:

def length(self):
    if self.isEmpty():
        return 0
    return self.rear - self.front + 1

Hemos implementado todos los métodos. Ejecutemos ahora todas las operaciones una vez.

Código completo:

class Queue:
    def __init__(self):
        self.data = list()
        self.front = -1
        self.rear = -1

    def isEmpty(self):
        if self.rear == -1 and self.front == -1:
            return True
        else:
            return False

    def enQueue(self, element):
        if self.isEmpty():
            self.data.append(element)
            self.front = 0
            self.rear = 0
        else:
            self.data.append(element)
            self.rear += 1

    def deQueue(self):
        if self.isEmpty():
            print("Queue is Empty. Cannot remove element")
        elif self.front == self.rear and self.front != -1:
            element = self.data[self.front]
            self.front = -1
            self.rear = -1
            return element
        else:
            element = self.data[self.front]
            self.front = self.front + 1
            return element

    def length(self):
        return self.rear - self.front + 1


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

Producción :

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is Empty. Cannot remove element

En el ejemplo, ejecutamos algunos métodos después de la implementación de la cola en Python usando listas. Puede copiar el código, pegarlo en su IDE y experimentar con el código para comprender mejor su funcionamiento.

Implementación de colas usando listas enlazadas en Python

Ya hemos discutido diferentes operaciones en listas enlazadas en Python. También podemos usar operaciones de lista enlazada para la implementación de colas en python.

Primero definiremos un nodo con dos atributos, a saber, datos y siguiente.

Código:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Dónde:

• El atributo datos se utilizará para almacenar elementos de la cola.
• El atributo siguiente se utilizará para apuntar al elemento anterior al elemento actual en la cola.

Luego de definir el Nodo, definiremos la clase Queue, donde tendremos los atributos front y rear.

El atributo front apuntará al nodo que contiene el elemento front en la lista enlazada de la cola. De manera similar, el atributo rear apuntará al nodo que contiene el elemento rear en la lista enlazada que contiene la cola.

Los atributos delantero y trasero se inicializarán en Ninguno ya que la cola estará vacía.

Código:

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

Cuando se inicializa la clase Queue, solo contiene los atributos front y rear, con el valor Ninguno.

Comprobar si la cola está vacía en Python

Para comprobar si la cola está vacía, podemos comprobar si los atributos frente y trasero son Ninguno. Si es así, podemos decir que la cola está vacía.

Definiremos el método isEmpty() para esta operación. Cuando se invoca en una cola, el método isEmpty() devolverá True si la cola está vacía; de lo contrario, devolverá False.

Código:

def isEmpty(self):
    if self.front is None:
        return True
    return False

Operación en cola usando listas enlazadas en Python

Para realizar la operación de poner en cola, primero comprobaremos si la cola está vacía. En caso afirmativo, asignaremos el nodo con el nuevo elemento a los atributos frontal y trasero.

De lo contrario, añadiremos el nuevo elemento al siguiente nodo del nodo trasero. Después de eso, haremos que el nuevo nodo sea el nodo trasero.

De esta forma, el nuevo elemento se añadirá a la cola.

Código:

def enQueue(self, data):
    newNode = Node(data)
    if self.isEmpty():
        self.front = newNode
        self.rear = newNode
    else:
        self.rear.next = newNode

Operación Dequeue usando listas enlazadas en Python

Primero comprobaremos si la cola está vacía para la operación de eliminación de cola. En caso afirmativo, diremos que se ha producido un desbordamiento y no podemos eliminar ningún elemento.

De lo contrario, primero almacenaremos los datos en una variable temporal en el nodo frontal.

Después de eso, haremos que el nodo siguiente del nodo frontal sea el nuevo nodo frontal. Luego, eliminaremos el nodo frontal almacenado en la variable temporal usando la instrucción del.

De esta forma, el nodo frontal anterior se eliminará de la cola. Finalmente, devolveremos el valor almacenado en el nodo temporal.

Código:

def deQueue(self):
    if self.isEmpty():
        print("Queue is empty. Cannot remove element.")
    else:
        element = self.front
        nextFront = self.front.next
        self.front = nextFront
        value = element.data
        del element
        return value

Encuentra la longitud de la cola en Python

1. Para encontrar la longitud de la cola, primero inicializaremos una variable cuenta a 0.
2. Después de eso, comenzaremos a recorrer la cola desde el nodo “delantero” usando un ciclo “mientras”. Incrementaremos el recuento en 1 al pasar al siguiente nodo.
3. Una vez lleguemos al final de la cola, es decir, Ninguno, saldremos del bucle while.
4. Finalmente, devolveremos el valor de count, mostrando la longitud de la cola.

Código:

def length(self):
    count = 0
    if self.front is None:
        return count
    else:
        temp = self.front
        while temp is not None:
            count += 1
            temp = temp.next
        return count

Hemos implementado todos los métodos de cola usando listas enlazadas. Ejecutemos ahora las operaciones para comprender mejor el funcionamiento.

Código completo:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def isEmpty(self):
        if self.front is None:
            return True
        return False

    def enQueue(self, data):
        newNode = Node(data)
        if self.isEmpty():
            self.front = newNode
            self.rear = newNode
        else:
            self.rear.next = newNode

    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            element = self.front
            nextFront = self.front.next
            self.front = nextFront
            value = element.data
            del element
            return value

    def length(self):
        count = 0
        if self.front is None:
            return count
        else:
            temp = self.front
            while temp is not None:
                count += 1
                temp = temp.next
            return count


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

Producción :

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.

Implementación de colas usando el módulo de colecciones en Python

También podemos usar el módulo de colecciones para la implementación de colas en Python.

El módulo Colecciones proporciona la clase deque (cola de dos extremos) para implementar colas y pilas en Python. Puede importar la clase deque en su programa usando la instrucción importar a continuación.

from collections import deque

Crearemos una clase, Queue, para implementar la cola. Como se muestra a continuación, crearemos un objeto deque dentro de la clase.

Código:

class Queue:
    def __init__(self):
        self.data = deque()

Cuando se instancia la clase Queue, se crea un objeto deque vacío para almacenar los elementos de la cola.

Comprobar la longitud de la cola en Python

Para comprobar la longitud de la cola, definiremos un método longitud(). Dentro del método longitud(), calcularemos la longitud del objeto deque utilizando la función len().

La función len() tomará el objeto deque como entrada y devolverá la longitud de deque. Devolveremos el valor de la función len() como la longitud de la cola, como se muestra a continuación.

Código:

def length(self):
    return len(self.data)

Comprobar si la cola está vacía en Python

Si la longitud de la cola es 0, diremos que la cola está vacía. Podemos definir el método isEmpty() como se muestra a continuación.

Código:

def isEmpty(self):
    if self.length() == 0:
        return True
    return False

Poner en cola un elemento en Python

Definiremos el método enQueue() para poner en cola un elemento. El método enQueue() tomará el nuevo elemento como argumento de entrada.

Dentro del método enQueue(), utilizaremos el método append() para añadir el elemento al objeto deque. El método append(), cuando se invoca en el objeto deque, toma el nuevo elemento como su argumento de entrada y lo agrega al objeto deque.

Código:

def enQueue(self, x):
    self.data.append(x)

Operación Dequeue en Python

Definiremos el método deQueue() para eliminar un elemento de la cola. Dentro del método deQueue(), invocaremos el método popleft() sobre el objeto deque de la cola.

El método popleft(), cuando se invoca en un objeto deque, elimina el elemento frontal del deque. También devuelve el elemento que se elimina de la cola.

También devolveremos el valor devuelto por el método popleft() del método deQueue() usando una instrucción return.

Código:

def deQueue(self):
    if self.isEmpty():
        print("Queue is empty. Cannot remove element.")
    else:
        return self.data.popleft()

Ahora hemos implementado todos los métodos para la implementación de colas en Python utilizando el módulo de colecciones. Observemos toda la ejecución.

Código completo:

from collections import deque


class Queue:
    def __init__(self):
        self.data = deque()

    def length(self):
        return len(self.data)

    def isEmpty(self):
        if self.length() == 0:
            return True
        return False

    def enQueue(self, x):
        self.data.append(x)

    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            return self.data.popleft()


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

Producción :

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.

Implementación de cola más eficiente en Python

Este artículo ha discutido tres enfoques para la implementación de colas en Python.

Entre todos los enfoques discutidos aquí, usar listas para almacenar los elementos de la cola es el peor. En este enfoque, los elementos nunca se eliminan de la lista.

Por lo tanto, le sugerimos que nunca lo use en sus programas. Úselo solo si es un principiante en Python y no sabe nada sobre listas enlazadas.

Si no tiene permitido usar módulos externos, puede usar la implementación de la cola de Python que usa listas vinculadas, ya que es eficiente en tiempo y memoria. Sin embargo, es más lento que el enfoque usando deque.

Debe usar el enfoque del módulo deque para la implementación de cola más eficiente de Python. Tiene la mejor eficiencia en términos de tiempo y memoria porque el código fuente del módulo está escrito en C, y la implementación usa listas enlazadas de doble extremo para implementar el objeto deque.

Esperamos que este artículo lo haya ayudado a comprender la implementación de colas en Python. Estén atentos para más artículos informativos.