Pilas y colas en Python

Este post fue migrado de un blog hecho con Wordpress. Si se ve mal, dejame un comentario y lo arreglo.

La forma más directa de tener pilas y colas en Python es usando listas, una de las poderosas estructuras de datos que vienen con el lenguaje.

Una pila es una estructura de datos secuencial en la que el último elemento insertado es el primero en retirarse (LIFO) y puede implementarse directamente con los métodos append y pop.

Una operación común en las pilas es top, que devuelve el elemento en el tope de la pila, pero sin quitarlo; esta operación se puede emular indexando por -1.

>>> pila = [6,7,8]

>>> pila.append(9)

>>> pila

[6, 7, 8, 9]

>>> pila.pop()

9

>>> pila.pop()

8

>>> pila[-1]

7

Implementar una cola requiere algo más. En las colas, a diferencia de las pilas, el primer valor insertado es el primero en quitarse (FIFO).

Un primer intento es implementarla con append y pop(0) que obtiene el primer elemento (o con insert insertando al principio y pop). Pero las listas de Python, si bien están optimizadas para insertar al final y quitar del final, no lo están para insertar al principio o quitar del principio. La solución es utilizar collections.deque que si está implementada con estas operaciones optimizadas.

>>> from collections import deque

>>> cola = deque([1,2,3])

>>> cola.append(4)

>>> cola

deque([1, 2, 3, 4])

>>> cola.popleft()

1

>>> cola.popleft()

2

>>> cola

deque([3, 4])

Comentarios

Comments powered by Disqus