Pilas y colas en Python

Introducción

Las estructuras de datos organizan el almacenamiento en las computadoras para que podamos acceder y modificar los datos de manera eficiente. Las pilas y las 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 las pilas y las colas se implementen con una matriz o una lista vinculada. Confiaremos en el List estructura de datos para acomodar tanto Pilas como Colas.

¿Cómo trabajan?

Apilar

Las pilas, como sugiere el nombre, siguen las Último en entrar primero en salir (LIFO) principio. Como si apilamos monedas una encima de la otra, la última moneda que ponemos en la parte superior es la que es la primera que se saca 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:

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

Cola

Las colas, como sugiere el nombre, siguen las Primero en entrar primero en salir (FIFO) principio. Como si esperara en una cola las entradas del cine, el primero en hacer fila 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 – agrega un elemento al final de la cola:

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

Pilas y colas usando listas

Python incorporado List La estructura de datos viene con métodos para simular operaciones tanto de pila como de cola.

Consideremos una pila de letras:

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. los pop La función 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:

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 el append y pop operaciones de la lista para simular las operaciones centrales de una cola.

Pilas y colas con la biblioteca Deque

Python tiene un deque (pronunciado ‘deck’) biblioteca 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 el último elemento almacenado:

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 deque biblioteca y otros tipos de colecciones que proporciona Python, puede leer nuestro artículo Introducción al módulo de colecciones de Python.

Implementaciones más estrictas en Python

Si su código necesita una pila y proporciona un List, no hay nada que impida que un programador llame insert, remove 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 ocasiones en las que nos gustaría asegurarnos de que solo se puedan realizar operaciones válidas con 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 definir dos clases:

# 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) 

Los programadores que utilizan nuestro Stack y Queue ahora se les anima a utilizar los métodos proporcionados para manipular los datos.

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 función de esta manera:

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 programación. Piense 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 evaluador 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 ingresan. De esta manera, no importa si los eventos de entrada vienen con poco tiempo entre ellos, todos se almacenarán y estarán disponibles para su procesamiento. Cuando procesamos los movimientos, podemos quitarlos de la cola. Se puede realizar un movimiento especial de la siguiente manera:

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 las colas son estructuras de datos simples que nos permiten almacenar y recuperar datos de forma secuencial. En una pila, el último elemento que ingresamos es el primero en salir. En una cola, el primer elemento que ingresamos es el primero en salir.

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

En Python, podemos implementar pilas y colas simplemente usando la función incorporada List estructura de datos. Python también tiene la deque biblioteca que puede proporcionar operaciones de pila y cola de manera eficiente 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 del mundo real para pilas y colas, entenderlos nos permite resolver muchos problemas de almacenamiento de datos de una manera fácil y efectiva.