Pilas y colas en Python

Las estructuras de datos organizan el almacenamiento en las computadoras para que podamos acceder y cambiar datos de manera eficiente. Las pilas y las colas son algunas de las primeras estructuras de datos definidas...

Introducción

Las estructuras de datos organizan el almacenamiento en las computadoras para que podamos acceder y cambiar datos de manera eficiente. Pilas y Colas son algunas de las primeras estructuras de datos definidas en informática.

Sencillos de aprender y fáciles de implementar, sus usos son comunes y lo más probable es que los incorpore en su software para diversas tareas.

Es común que Stacks y Queues se implementen con un Array o Lista enlazada. Confiaremos en la estructura de datos List para acomodar pilas y colas.

¿Cómo trabajan? {#Cómo trabajan}

Pila

Las pilas, como sugiere su nombre, siguen el principio Último en entrar, primero en salir (LIFO). Como si estuviéramos apilando monedas una encima de otra, la última moneda que ponemos encima es la que se retira primero de la pila más tarde.

Para implementar una pila, por lo tanto, necesitamos dos operaciones simples:

  • push - agrega un elemento a la parte superior de la pila:

Agregando un elemento a una pila

  • pop - elimina el elemento en la parte superior de la pila:

Quitando un elemento de una pila

Cola

Las colas, como sugiere su nombre, siguen el principio primero en entrar, primero en salir (FIFO). Como si esperara en la cola las entradas para el cine, el primero en hacer cola es el primero en comprar una entrada y disfrutar de la película.

Para implementar una cola, por lo tanto, necesitamos dos operaciones simples:

  • enqueue - añade un elemento al final de la cola:

Agregar una cola

  • dequeue - elimina el elemento al principio de la cola:

Quitar un elemento de una cola

Pilas y colas usando listas

La estructura de datos ‘List’ integrada de Python viene con métodos para simular operaciones de pila y cola.

Consideremos una pila de letras:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
letters = []

# Let's push some letters into our list
letters.append('c')
letters.append('a')
letters.append('t')
letters.append('g')

# Now let's pop letters, we should get 'g'
last_item = letters.pop()
print(last_item)

# If we pop again we'll get 't'
last_item = letters.pop()
print(last_item)

# 'c' and 'a' remain
print(letters) # ['c', 'a']

Podemos usar las mismas funciones para implementar una cola. La función pop opcionalmente toma el índice del elemento que queremos recuperar como argumento.

Entonces podemos usar pop con el primer índice de la lista, es decir, 0, para obtener un comportamiento similar al de una cola.

Considere una "cola" de frutas:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
fruits = []

# Let's enqueue some fruits into our list
fruits.append('banana')
fruits.append('grapes')
fruits.append('mango')
fruits.append('orange')

# Now let's dequeue our fruits, we should get 'banana'
first_item = fruits.pop(0)
print(first_item)

# If we dequeue again we'll get 'grapes'
first_item = fruits.pop(0)
print(first_item)

# 'mango' and 'orange' remain
print(fruits) # ['c', 'a']

Nuevamente, aquí usamos las operaciones append y pop de la lista para simular las operaciones principales de una cola.

Pilas y colas con la biblioteca Deque

Python tiene una biblioteca deque (pronunciado 'deck') que proporciona una secuencia con métodos eficientes para trabajar como una pila o una cola.

deque es la abreviatura de Double Ended Queue - una cola generalizada que puede obtener el primer o último elemento almacenado:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque

# you can initialize a deque with a list 
numbers = deque()

# Use append like before to add elements
numbers.append(99)
numbers.append(15)
numbers.append(82)
numbers.append(50)
numbers.append(47)

# You can pop like a stack
last_item = numbers.pop()
print(last_item) # 47
print(numbers) # deque([99, 15, 82, 50])

# You can dequeue like a queue
first_item = numbers.popleft()
print(first_item) # 99
print(numbers) # deque([15, 82, 50])

Si desea obtener más información sobre la biblioteca deque y otros tipos de colecciones que proporciona Python, puede leer nuestra Introducción al módulo de colecciones de Python artículo.

Implementaciones más estrictas en Python

Si su código necesita una pila y proporciona una “Lista”, no hay nada que impida que un programador llame a “insertar”, “eliminar” u otras funciones de lista que afectarán el orden de su pila. Esto arruina fundamentalmente el punto de definir una pila, ya que ya no funciona como debería.

Hay momentos en los que nos gustaría asegurarnos de que solo se puedan realizar operaciones válidas en nuestros datos.

Podemos crear clases que solo exponen los métodos necesarios para cada estructura de datos.

Para hacerlo, creemos un nuevo archivo llamado stack_queue.py y definamos dos clases:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# A simple class stack that only allows pop and push operations
class Stack:

    def __init__(self):
        self.stack = []

    def pop(self):
        if len(self.stack) < 1:
            return None
        return self.stack.pop()

    def push(self, item):
        self.stack.append(item)

    def size(self):
        return len(self.stack)

# And a queue that only has enqueue and dequeue operations
class Queue:

    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

    def size(self):
        return len(self.queue) 

Ahora se anima a los programadores que usan nuestra Stack y Queue a usar los métodos provistos para manipular los datos en su lugar.

Ejemplos

Imagina que eres un desarrollador que trabaja en un nuevo procesador de textos. Tiene la tarea de crear una función de deshacer, lo que permite a los usuarios retroceder en sus acciones hasta el comienzo de la sesión.

Una pila es ideal para este escenario. Podemos registrar cada acción que realiza el usuario empujándola a la pila. Cuando el usuario quiera deshacer una acción, la sacará de la pila. Podemos simular rápidamente la característica de esta manera:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
document_actions = Stack()

# The first enters the title of the document
document_actions.push('action: enter; text_id: 1; text: This is my favourite document')
# Next they center the text
document_actions.push('action: format; text_id: 1; alignment: center')
# As with most writers, the user is unhappy with the first draft and undoes the center alignment
document_actions.pop()
# The title is better on the left with bold font
document_actions.push('action: format; text_id: 1; style: bold')

Las colas también tienen usos generalizados en la programación. Piensa en juegos como Street Fighter o Super Smash Brothers. Los jugadores de esos juegos pueden realizar movimientos especiales presionando una combinación de botones. Estas combinaciones de botones se pueden almacenar en una cola.

Ahora imagina que eres un desarrollador que trabaja en un nuevo juego de lucha. En su juego, cada vez que se presiona un botón, se activa un evento de entrada. ¡Un probador notó que si los botones se presionan demasiado rápido, el juego solo procesa el primero y los movimientos especiales no funcionarán!

Puedes arreglar eso con una cola. Podemos poner en cola todos los eventos de entrada a medida que entran. De esta manera, no importa si los eventos de entrada vienen con poco tiempo entre ellos, todos estarán almacenados y disponibles para su procesamiento. Cuando estamos procesando los movimientos, podemos sacarlos de la cola. Un movimiento especial se puede resolver así:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
input_queue = Queue()

# The player wants to get the upper hand so pressing the right combination of buttons quickly
input_queue.enqueue('DOWN')
input_queue.enqueue('RIGHT')
input_queue.enqueue('B')

# Now we can process each item in the queue by dequeueing them
key_pressed = input_queue.dequeue() # 'DOWN'

# We'll probably change our player position
key_pressed = input_queue.dequeue() # 'RIGHT'

# We'll change the player's position again and keep track of a potential special move to perform
key_pressed = input_queue.dequeue() # 'B'

# This can do the act, but the game's logic will know to do the special move

Conclusión

Las pilas y colas son estructuras de datos simples que nos permiten almacenar y recuperar datos secuencialmente. En una pila, el último elemento que ingresamos es el primero en salir. En una cola, el primer elemento que ingresamos es el primero que sale.

Podemos agregar elementos a una pila usando la operación push y recuperar elementos usando la operación pop. Con las colas, agregamos elementos usando la operación enqueue y recuperamos elementos usando la operación dequeue.

En Python, podemos implementar pilas y colas simplemente usando la estructura de datos Lista incorporada. Python también tiene la biblioteca deque que puede proporcionar de manera eficiente operaciones de pila y cola en un objeto. Finalmente, hemos creado nuestras clases de pila y cola para un control más estricto de nuestros datos.

Hay muchos casos de uso en el mundo real para pilas y colas, comprenderlos nos permite resolver muchos problemas de almacenamiento de datos de una manera fácil y efectiva.