Pila y colas en Python – Part 1

Prerrequisitos: list y Deque en Python .

A diferencia de C++ STL y Java Collections, Python tiene clases/interfaces específicas para Stack y Queue . Las siguientes son diferentes formas de implementar en Python

1) El uso de list
Stack funciona según el principio de «Último en entrar, primero en salir». Además, las funciones integradas en Python hacen que el código sea corto y simple. Para agregar un elemento a la parte superior de la lista, es decir, para empujar un elemento, usamos la función append() y para sacar un elemento usamos la función pop() . Estas funciones funcionan de manera silenciosa, eficiente y rápida en las operaciones finales.

Veamos un ejemplo e intentemos comprender el funcionamiento de las funciones push() y pop():
Ejemplo:

# Python code to demonstrate Implementing 
# stack using list
stack = ["Amar", "Akbar", "Anthony"]
stack.append("Ram")
stack.append("Iqbal")
print(stack)
  
# Removes the last item
print(stack.pop())
  
print(stack)
  
# Removes the last item
print(stack.pop())
  
print(stack)

['Amar', 'Akbar', 'Anthony', 'Ram', 'Iqbal']
Iqbal
['Amar', 'Akbar', 'Anthony', 'Ram']
Ram
['Amar', 'Akbar', 'Anthony']

Queue funciona según el principio de «primero en entrar, primero en salir». A continuación se muestra la implementación de la cola. Usamos pop(0) para eliminar el primer elemento de una lista.

# Python code to demonstrate Implementing 
# Queue using list
queue = ["Amar", "Akbar", "Anthony"]
queue.append("Ram")
queue.append("Iqbal")
print(queue)
  
# Removes the first item
print(queue.pop(0))
  
print(queue)
  
# Removes the first item
print(queue.pop(0))
  
print(queue)

['Amar', 'Akbar', 'Anthony', 'Ram', 'Iqbal']
Amar
['Akbar', 'Anthony', 'Ram', 'Iqbal']
Akbar
['Anthony', 'Ram', 'Iqbal']

2) Uso de Deque
En el caso de la pila, la implementación de la lista funciona bien y proporciona tanto append() como pop() en tiempo O(1). Cuando usamos la implementación de deque, obtenemos la misma complejidad de tiempo.

# Python code to demonstrate Implementing 
# Stack using deque
from collections import deque
queue = deque(["Ram", "Tarun", "Asif", "John"])
print(queue)
queue.append("Akbar")
print(queue)
queue.append("Birbal")
print(queue)
print(queue.pop())                 
print(queue.pop())                 
print(queue)

deque(['Ram', 'Tarun', 'Asif', 'John'])
deque(['Ram', 'Tarun', 'Asif', 'John', 'Akbar'])
deque(['Ram', 'Tarun', 'Asif', 'John', 'Akbar', 'Birbal'])
Birbal
Akbar
deque(['Ram', 'Tarun', 'Asif', 'John'])

Pero cuando se trata de la cola, la implementación de la lista anterior no es eficiente. En cola cuando se hace pop() desde el principio de la lista, lo cual es lento. Esto ocurre debido a las propiedades de la lista, que es rápida en las operaciones finales pero lenta en las operaciones iniciales, ya que todos los demás elementos deben cambiarse uno por uno.
Por lo tanto, preferimos el uso de dequeue sobre la lista, que fue especialmente diseñado para tener agregados y elementos emergentes rápidos tanto en la parte delantera como en la trasera.

Veamos un ejemplo e intentemos entender la cola usando collections.deque:

# Python code to demonstrate Implementing 
# Queue using deque
from collections import deque
queue = deque(["Ram", "Tarun", "Asif", "John"])
print(queue)
queue.append("Akbar")
print(queue)
queue.append("Birbal")
print(queue)
print(queue.popleft())                 
print(queue.popleft())                 
print(queue)

deque(['Ram', 'Tarun', 'Asif', 'John'])
deque(['Ram', 'Tarun', 'Asif', 'John', 'Akbar'])
deque(['Ram', 'Tarun', 'Asif', 'John', 'Akbar', 'Birbal'])
Ram
Tarun
deque(['Asif', 'John', 'Akbar', 'Birbal'])

Este artículo es una contribución de Chinmoy Lenka . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.