Pilas / Stacks

Invariante de la Pila: LIFO

Todas las primitivas tienen complejidad O(1)

Diferencia entre top() y pop(): el último borra el elemento de arriba

→ es referenciar y acceder al valor

Queue (cola)

Invariante: FIFO

Ejercicio: hacer un validador de paréntesis usando Queue o Stacks

def validate_parenthesis(word):
	stack = []
	for p in word:
		if(p == "("):
			stack.add(p)
		elif (p == ")"):
			stack.pop()
	return len(stack) == 0

Notación inversa polaca

Cómo podría implementar un programa que use notación inversa polaca con stacks o queues, sin programarlo