Introducción
Las estructuras de datos organizan el almacenamiento en las computadoras para que podamos acceder y cambiar los datos de manera eficiente. Las pilas y colas son algunas de las primeras estructuras de datos definidas en ciencias de la computación.
Simples de aprender y fáciles de implementar, sus usos son comunes y lo más probable es que se encuentre incorporándolos en su software para varias tareas.
Es común que las pilas y Colas se implementen con una Matriz o Lista Vinculada. Dependeremos de la estructura de datos List para acomodar tanto Pilas como colas.
¿Cómo Funcionan?
Pila
Las pilas, como su nombre indica, siguen el principio de Última entrada, Primera salida (LIFO). Como si apiláramos monedas una encima de la otra, la última moneda que ponemos en la parte superior es la primera que se retira 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
Colas, como el nombre lo sugiere, siga las First-in-First-Out (FIFO) principio. Como si esperara en una cola para las entradas de 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– agrega un elemento al final de la cola:
-
dequeue– elimina el elemento al principio de la cola:
Pilas y las Colas mediante Listas
Python integrado en el List estructura de datos viene con métodos para simular la pila y cola de operaciones.
Consideremos una pila de letras:
Podemos usar las mismas funciones para implementar una Cola. La función pop opcionalmente toma como argumento el índice del elemento que queremos recuperar.
Para que podamos usar pop con el primer índice de la lista, es decir, 0, para obtener un comportamiento similar a la cola.
Considere una «cola» de frutas:
De nuevo, aquí usamos las operacionesappend ypop 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 pila o cola.
deque es la abreviatura de Cola de doble extremo, una cola generalizada que puede obtener el primer o el último elemento almacenado:
Si desea obtener más información sobre la biblioteca deque y otros tipos de colecciones que proporciona Python, puede leer nuestro artículo de 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 a insertremove 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 en nuestros datos.
podemos crear clases que sólo expone los métodos necesarios para cada estructura de datos.
Para hacerlo, vamos a crear un nuevo archivo llamado stack_queue.py y definir dos clases:
Los programadores que usan nuestro Stack y Queue ahora se les anima a usar los métodos proporcionados para manipular los datos en su lugar.
Ejemplos
Imagine que es un desarrollador que trabaja en un procesador de textos completamente nuevo. Tienes 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 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 esta manera:
Las colas también tienen un uso generalizado en la programación. Piensa en juegos como Street Fighter o Super Smash Brothers. Los jugadores en 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 el juego, cada vez que se pulsa un botón, se dispara 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.
Puede arreglarlo con una cola. Podemos encolar 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 se almacenarán y estarán disponibles para su procesamiento. Cuando estamos procesando los movimientos que podemos eliminar de la cola de ellos. Se puede realizar un movimiento especial como este:
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 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 mediante la operación enqueue y recuperamos elementos mediante la operación dequeue.
En Python, podemos implementar pilas y colas simplemente usando la estructura de datos incorporada List. Python también tiene la biblioteca deque que puede proporcionar de manera eficiente operaciones de pila y cola en un objeto. Por último, 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.