Introducción

Las estructuras de datos organizan el almacenamiento en los ordenadores para que podamos acceder y cambiar los datos de forma eficiente. Las pilas y las colas son algunas de las primeras estructuras de datos definidas en informática.

Simple de aprender y fácil de implementar, sus usos son comunes y lo más probable es que te encuentres incorporándolas en tu software para diversas tareas.

Es común que las pilas y las colas se implementen con un array o una lista enlazada. Nos basaremos en la estructura de datos List para acomodar tanto las pilas como las colas.

¿Cómo funcionan?

Pila

Las pilas, como su nombre indica, siguen el principio de último en entrar, primero en salir (LIFO). Como si se tratara de apilar monedas una encima de otra, la última moneda que pongamos en la parte superior será la primera en ser retirada de la pila posteriormente.

Para implementar una pila, por tanto, necesitamos dos sencillas operaciones:

• push – añade un elemento a la parte superior de la pila:

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

Cola

Las colas, como su nombre indica, siguen el principio del primero en entrar, primero en salir (FIFO). Como si se tratara de una cola para comprar las entradas del cine, el primero que se pone en la cola es el primero que compra una entrada y disfruta de la película.

Para implementar una cola, por tanto, necesitamos dos operaciones sencillas:

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

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

Pilas y colas usando listas

La estructura de datos Listincorporada en Python viene con métodos para simular operaciones de pila y cola.

Consideremos una pila de letras:

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

Así que 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:

De nuevo, aquí utilizamos las operaciones append y pop de la lista para simular las operaciones centrales de una cola.

Pilas y colas con la biblioteca Deque

Python tiene una biblioteca deque (se pronuncia ‘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 el último elemento almacenado:

Si quieres aprender más sobre la biblioteca deque y otros tipos de colecciones que proporciona Python, puedes leer nuestro artículo Introducción al módulo de colecciones de Python.

Implementaciones de la pila en Python

Si tu código necesitaba una pila y proporcionas una List, ¡no hay nada que impida a un programador llamar a insert, remove u otras funciones de lista que afectarán al orden de tu 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 sólo se pueden realizar operaciones válidas en nuestros datos.

Podemos crear clases que sólo expongan los métodos necesarios para cada estructura de datos.

Para ello, vamos a crear un nuevo archivo llamado stack_queue.py y a definir dos clases:

Los programadores que utilicen nuestros Stack y Queue se verán ahora animados a utilizar los métodos proporcionados para manipular los datos en su lugar.

Ejemplos

Imagina que eres un desarrollador que trabaja en un flamante procesador de textos. Usted tiene la tarea de crear una función de deshacer – permitiendo a los usuarios a retroceder sus acciones hasta el comienzo de la sesión.

Una pila es un ajuste ideal para este escenario. Podemos registrar cada acción que el usuario realiza 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 la siguiente manera:

Las colas tienen usos muy extendidos en la programación también. Piensa en juegos como Street Fighter o Super Smash Brothers. Los jugadores de esos juegos pueden realizar movimientos especiales pulsando 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 pulsa un botón, se dispara un evento de entrada. Un probador se ha dado cuenta de que si los botones se pulsan demasiado rápido, el juego sólo procesa el primero y los movimientos especiales no funcionan.

Puedes arreglar eso con una cola. Podemos poner en cola todos los eventos de entrada a medida que llegan. De esta manera no importa si los eventos de entrada vienen con poco tiempo entre ellos, todos estarán almacenados y disponibles para ser procesados. Cuando estemos procesando las jugadas podemos ponerlas en cola. Un movimiento especial se puede elaborar así:

Conclusión

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

Podemos añadir elementos a una pila utilizando la operación push y recuperar elementos utilizando la operación pop. Con las colas, añadimos elementos utilizando la operación enqueue y recuperamos elementos utilizando la operación dequeue.

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

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