Contenido del curso
Creación de Colas con Stacks en Python
¿Cómo crear una cola utilizando dos pilas?
Crear una cola usando dos pilas puede parecer un reto, al tratarse de estructuras de datos que funcionan bajo principios diferentes. Mientras que las pilas operan bajo el principio de "último en entrar, primero en salir" (LIFO por sus siglas en inglés), las colas usan "primero en entrar, primero en salir" (FIFO). Pero tranquilo, no es tan complejo como parece, ya que con un entendimiento claro de la lógica, podemos resolverlo de manera eficaz y elegante en Python.
¿Cómo se estructura la clase colas?
Para empezar, crearemos una clase llamada Cue con dos listas vacías que simulan nuestras pilas internas. Vamos a llamar a estas listas InboundStack y OutboundStack.
class Cue: def __init__(self): self.inbound_stack = [] self.outbound_stack = []
¿Cómo se implementa el método para agregar a la cola?
El método nq servirá para añadir datos a nuestra cola. Utilizaremos la lista InboundStack y su función append() para ello, lo cual es bastante sencillo.
def nq(self, data): self.inbound_stack.append(data)
¿Cómo se implementa el método para eliminar de la cola?
El método deck es más complicado, pero vamos a desglosar su lógica. Debemos atender el funcionamiento FIFO al mover elementos de InboundStack a OutboundStack usando el método pop(). Esto nos permitirá revertir el orden.
def deck(self): if not self.outbound_stack: while self.inbound_stack: self.outbound_stack.append(self.inbound_stack.pop()) return self.outbound_stack.pop()
¿Cómo probar y entender la funcionalidad?
Para verificar el funcionamiento, observemos cómo la clase Cue interactúa con números:
nq para añadir números secuenciales: 5, 6, 7.deck para quitar números y los resultados reflejan el orden FIFO: el 5 saldrá antes que el 6 y 7.# Simulación en shell de Python from stack_base_cue import Cue numbers_queue = Cue() numbers_queue.nq(5) numbers_queue.nq(6) numbers_queue.nq(7) print(numbers_queue.deck()) # Imprime: 5
Reflexiones finales
El uso de dos pilas para simular una cola no solo es un buen ejercicio lógico, sino una habilidad útil para entrevistas de trabajo técnicas, donde puedes enfrentar restricciones como "usa dos pilas", las cuales te obligan a pensar fuera de las soluciones habituales. Al practicar esto, comprenderás mejor cómo las estructuras de datos están interconectadas y cómo podrías optimizar su uso en el desarrollo de software avanzado. Sigue aprendiendo y explorando, ¡la experiencia vendrá con la práctica!
José Ricardo Romo Gutiérrez
Estudiante
rusbel bermúdez rivera
Estudiante
Mauricio Gonzalez Falcon
Estudiante
Christian Molina Vázquez
Estudiante
Cristian Blandon
EstudianteMauricio Gonzalez Falcon
EstudianteMauricio Gonzalez Falcon
Estudiante
Leonardo David Alonso Sosa
Estudiante
Manuel Rodrigo Zamorano Jimenez
Estudiante
Luis Eduardo Lerena Pereira
EstudianteMauricio Gonzalez Falcon
Estudiante
José B. Méndez Padín
Estudiante
Elvis Ronald Cruz Chullo
Estudiante
Miguel Angel Reyes Moreno
Estudiante
Héctor Daniel Vega Quiñones
Profesor
Dennys Regalado Díaz
EstudianteManuel Rodrigo Zamorano Jimenez
Estudiante
Alfonso Andres Zapata Guzman
Estudiante
Rubén Cuello
Estudiante
David Rosas
Estudiante
Rigoberto Maldonado
Estudiante
Andrés Cardona
Estudiante
Jhon Freddy Tavera Blandon
Estudiante
Nicolas Alpargatero
Estudiante
Reinaldo Mendoza
Estudiante
reality !
Estudiante
Joel Angel David Barrantes Palacios
Estudianteuna anotacion en este tipo de queues basados en stacks, es que la operacion de pop es supremamente lenta cuando aumenta el numero de elementos drasticamenta
Les dejo un articulo que escribi sobre esto: https://ricardoromo.co/2020/aprende-7-trucos-que-quizas-no-conocias-de-python/
existe la clase deque en el modulo collections de python que permite hacer stacks y queues de forma mas optima. vale la pena mirar.
También pensé en eso, si llega a superar cierta cantidad de datos se vuelve sumamente lento.
Me hubiera hustado que estas clases, de stack y queues se hubieran hecho antes que las de nodos y linked list que por mi parte considero más complicados.
Les compartó el código vistos en la clase.
class Queue: def __init__(self) -> None: self.inboud_stack = [] self.outbound_stack = [] def enqueue(self, data): self.inboud_stack.append(data) def dequeue(self): if not self.outbound_stack: while self.inboud_stack: self.outbound_stack.append(self.inboud_stack.pop()) return self.outbound_stack.pop()
from stack_based_queue import Queue numbers = Queue() numbers.enqueue(5) numbers.enqueue(6) numbers.enqueue(7) print(numbers.inboud_stack) print(numbers.dequeue()) print(numbers.inboud_stack) print(numbers.outbound_stack) print(numbers.dequeue()) print(numbers.outbound_stack) print(numbers.dequeue()) print(numbers.outbound_stack) print(numbers.inboud_stack)
[5, 6, 7] 5 [] [7, 6] 6 [7] 7 [] []
¿Por qué el postre siempre debe ir al final? :sweat_smile:
Yo entiendo que se hizo así porque los stacks y las linked list no funcionan con listas realmente, excepto en python.
Sino que funcionan de manera más compleja.
Este tipo de código no es muy óptimo a largo plazo, por el hecho de que en caso de que nuestra data aumente, simplemente el tiempo que nos topa recorrerlo también lo hará.
Este código tiene una notación de O(n elevado a 2).
Hay un error en el código implementado en esta clase ya que este no permite hacer un enqueue correcto después del dequeue, así es como corregí el problema
def dequeue(self): while self.inbound_stack: self.outbound_stack.append(self.inbound_stack.pop()) return self.outbound_stack.pop(0) if self.outbound_stack else None
Excelente .. Thanks.!
A quien corresponda, buen día. Tengo una duda y es respecto al funcionamiento de que pasa si después de realizar un pop, quiero agregar un nuevo elemento a la cola, porque al estar el objeto inbound sin datos, el único valor que contiene es el dato nuevo. Y al ejecutar pop, solo trabaja con el outbound.
Desde ya muchas gracias,
Esta es la solución de un compañero, es un pequeño error del profe
def dequeue(self): while self.inbound_stack: self.outbound_stack.append(self.inbound_stack.pop()) return self.outbound_stack.pop(0) if self.outbound_stack else None
En el método dequeue(), antes de hacer el pop de self.outbound_stack habría que comprobar si existe algo dentro de ese campo, para que no lance una excepción.
Muy intuitiva la clase profesor.
Mencionaste que esto es usado en entrevistas técnicas... ¿pero qué utilidad tienen en la programación las queues basadas en stacks?
Dependiendo del tipo de constraints o restricciones, utilizar stacks pueden brindarte un mejor tiempo de procesamiento.
En las entrevistas técnicas vas a encontrar problemas que se simplifican enormemente si usas la estructura de datos correcta.
Ejemplo 1
Escribir una funciona para determinar si los paréntesis están balanceados o no.
Input
((5+6)+3) (6+7+3)+(2+(1)
Output Yes No
Hint Usar un stack (pila) simplifica el problema
Ejemplo 2
A partir de la representación de tu red de amigos (grafo) en facebook. Determinar si Fredy es tu amigo directo o es amigo de alguno de tus amigos.
Para solucionarlo puedes implementar un algoritmo de búsqueda por profundidad (DFS) o búsqueda por anchura (BFS). La implementación de ambos es similar, la diferencia es la estructura de datos, para el primero se usa una cola y para el segundo una pila.
Ejemplo 3
Si solucionas una problema de forma recursiva, puedes mejorar el tiempo de ejecución convirtiéndola en iterativa usando una cola (queue).
COLAS CON DOS STACK's (Correccion de outbound_stack Vacio)
class Queue: def init(self): self.inbound_stack = [] self.outbound_stack = []
# Encola def enqueue(self, data): self.inbound_stack.append(data) # Desencola def dequeue(self): if not self.outbound_stack: while self.inbound_stack: self.outbound_stack.append(self.inbound_stack.pop()) return self.outbound_stack.pop() def dequeue(self): while self.inbound_stack: self.outbound_stack.append(self.inbound_stack.pop()) if self.outbound_stack: return self.outbound_stack.pop()
'''stack_base_queue.py''' class Queue: def __init__(self): self.inboud_stack = [] self.outbound_stack = [] def enqueue(self, data): self.inboud_stack.append(data) def dequeue(self): if not self.outbound_stack: # si no esta vacio print(f'Iniciamos while, nuestra lista inboud {self.inboud_stack}') while self.inboud_stack: self.outbound_stack.append(self.inboud_stack.pop()) print(f'Lista inboud {self.inboud_stack}') print(f'Lista outbound {self.outbound_stack}') return self.outbound_stack.pop() if __name__ == '__main__': numbers = Queue() numbers.enqueue(5) numbers.enqueue(6) numbers.enqueue(7) print(numbers.inboud_stack) print(numbers.dequeue()) print(numbers.inboud_stack) print(numbers.outbound_stack)
Que pasaría si agregamos 5 números , quitamos 2 y luego agregamos otro? Tendríamos elementos en inbound stack y en outbound stack. Como mostrarías la Queue en ese caso?
No seria adecuado o necesario que una vez hecho el dequeue se asignara otra vez el inbound = outbound ?
Me enfoqué en entender la simplicidad del codigo aniadiendo dos stack dentro de una clase Queue...
,,,
excelente resultado...
Dejo el código comentado para mejor entendimiento:
class Queue: def __init__(self): self.inbound_stack = [] # Stack utilizado para operaciones enqueue self.outbound_stack = [] # Stack utilizado para operaciones dequeue def enqueue(self, data): self.inbound_stack.append(data) # Agrega el elemento al stack de inbound (entrada) def dequeue(self): if not self.outbound_stack: # Si el stack de outbound (salida) está vacío, se realiza una transferencia print(f'Iniciamos while, nuestra lista inbound {self.inbound_stack}') while self.inbound_stack: self.outbound_stack.append(self.inbound_stack.pop()) # Transfiere elementos de inbound a outbound print(f'Lista inbound {self.inbound_stack}') print(f'Lista outbound {self.outbound_stack}') return self.outbound_stack.pop() # Devuelve y elimina el elemento más antiguo en outbound if __name__ == '__main__': numbers = Queue() numbers.enqueue(5) numbers.enqueue(6) numbers.enqueue(7) print(numbers.inbound_stack) print(numbers.dequeue()) # Imprime y elimina el primer elemento en la cola (5) print(numbers.inbound_stack) print(numbers.outbound_stack) # Imprime el stack outbound (6, 7) ```class Queue:   def \_\_init\_\_(self):   self.inbound\_stack = \[] # Stack utilizado para operaciones enqueue   self.outbound\_stack = \[] # Stack utilizado para operaciones dequeue   def enqueue(self, data):   self.inbound\_stack.append(data) # Agrega el elemento al stack de inbound (entrada)   def dequeue(self):   if not self.outbound\_stack: # Si el stack de outbound (salida) está vacío, se realiza una transferencia   print(f'Iniciamos while, nuestra lista inbound {self.inbound\_stack}')   while self.inbound\_stack:   self.outbound\_stack.append(self.inbound\_stack.pop()) # Transfiere elementos de inbound a outbound   print(f'Lista inbound {self.inbound\_stack}')   print(f'Lista outbound {self.outbound\_stack}')       return self.outbound\_stack.pop() # Devuelve y elimina el elemento más antiguo en outbound if \_\_name\_\_ == '\_\_main\_\_':   numbers = Queue()   numbers.enqueue(5)   numbers.enqueue(6)   numbers.enqueue(7)   print(numbers.inbound\_stack)   print(numbers.dequeue()) # Imprime y elimina el primer elemento en la cola (5)   print(numbers.inbound\_stack)   print(numbers.outbound\_stack) # Imprime el stack outbound (6, 7)
Implementación de una cola basada en dos stacks en Python:
class Queue: def __init__(self): self.inbound_stack = [] self.outbound_stack = [] def is_empty(self): return len(self.inbound_stack) == 0 and len(self.outbound_stack) == 0 def enqueue(self, item): self.inbound_stack.append(item) def dequeue(self): if self.is_empty(): raise IndexError("Queue is empty") if len(self.outbound_stack) == 0: while len(self.inbound_stack) > 0: self.outbound_stack.append(self.inbound_stack.pop()) return self.outbound_stack.pop() def front(self): if self.is_empty(): raise IndexError("Queue is empty") if len(self.outbound_stack) == 0: while len(self.inbound_stack) > 0: self.outbound_stack.append(self.inbound_stack.pop()) return self.outbound_stack[-1] def size(self): return len(self.inbound_stack) + len(self.outbound_stack) ''' En esta implementación, utilizamos dos stacks: inbound_stackpara agregar (agregar elementos) y `outbound_stackoutbound_stackpara desencolar (eliminar elementos). El método is_empty()verifica si ambas pilas están vacías. El metodo enqueue(item)agregainbound_stack. El metodo dequeue()extrae youtbound_stack. Si la pila outbound_stackestá vacía, transferimos los elementos delinbound_stackal outbound_stacken orden inverso antes de realizar la operación de desencolar. El metodo `front()devuelve el elemento del frente del stack outbound_stacksin eliminarlo. Si el stack outbound_stackestá vacío, transferimos los elementos del `ininbound_stack al outbound_stacken orden inverso antes de obtener el elemento del frente. El método size()devuelve el tamaño total de la cola. Puedes utilizar la''' # Crear una instancia de la cola my_queue = Queue() # Verificar si la cola está vacía print(my_queue.is_empty()) # Resultado: True # Agregar elementos a la cola my_queue.enqueue(1) my_queue.enqueue(2) my_queue.enqueue(3) # Obtener el elemento del frente de la cola print(my_queue.front()) # Resultado: 1 # Eliminar y obtener el elemento del frente de la cola print(my_queue.dequeue()) # Resultado: 1 # Obtener el tamaño actual de la cola print(my_queue.size()) # Resultado: 2 # Verificar si la cola está vacía nuevamente print(my_queue.is_empty()) # Resultado: False
No le veo utilidad al codigo pues a la final no esta diciendo lo que dice que en algunas entrevistas pueden pedir algo asi, y es pasar de LIFO a FIFO
Misma estructura, distinto funcionamiento
Me habría gustado que en este curso se nombrara la complejidad de cada operación en las estructuras de datos estudiadas, y también la complejidad de las implementaciones utilizadas. Me parece importante apredener con base en lo aplicable y realmente escalable en la vida real. Gracias por el curso.
es extraño que print(not []) sea igual a False o not None sea igual a True en python