Introducci贸n
Contenido
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.