Implementación y aplicaciones de pilas
Implemente una pila con push/pop/peek y resuelva valid-parentheses, min-stack y la evaluación de notación polaca inversa.
Implementación y aplicaciones de pilas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
La estructura de datos pila
Una pila es una estructura de datos de tipo último en entrar, primero en salir (LIFO). El último elemento añadido es el primero que se extrae. Piense en una pila de platos: solo se pueden añadir o retirar elementos por la parte superior. Las operaciones principales son push (añadir en la parte superior), pop (retirar de la parte superior) y peek (leer el elemento superior sin retirarlo). Las tres operaciones son O(1) en una pila bien implementada.
En Python, una lista funciona perfectamente como pila: append es push, pop() es pop y [-1] es peek.
stack = []
# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack) # [10, 20, 30]
# Peek
print('Top:', stack[-1]) # 30
# Pop
print('Popped:', stack.pop()) # 30
print('After pop:', stack) # [10, 20]Clase Stack con Push, Pop, Peek e isEmpty
Envolver la lista en una clase proporciona una interfaz más clara y evita el uso accidental de operaciones que no pertenecen a una pila, como insert o el acceso mediante índices distintos de la parte superior. Esta es la implementación que esperan los entrevistadores cuando solicitan 'implementar una pila desde cero'.
class Stack:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
def pop(self):
if self.is_empty():
raise IndexError('pop from empty stack')
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty stack')
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek()) # 3
print(s.pop()) # 3
print(len(s)) # 2Paréntesis válidos (LeetCode 20)
LeetCode 20 'Paréntesis válidos': determine si una cadena de corchetes está equilibrada. Por cada corchete de apertura, haga push. Por cada corchete de cierre, compruebe que el elemento superior de la pila sea el abridor correspondiente; si no lo es, o si la pila está vacía, devuelva False. Si la pila está vacía al final, la cadena es válida. Esta es la primera aplicación canónica de una pila en las entrevistas de programación.
def isValid(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack[-1] != matching[ch]:
return False
stack.pop()
return len(stack) == 0
print(isValid('()[]{}')) # True
print(isValid('([)]')) # False
print(isValid('{[]}')) # True
print(isValid(']')) # FalsePila mínima (LeetCode 155)
LeetCode 155 'Pila mínima': diseñe una pila que admita push, pop, peek y getMin, todos en O(1). El truco consiste en mantener una segunda pila que registre el mínimo en cada momento. Al hacer push, añada también el valor a la pila de mínimos si el nuevo valor es <= que el mínimo actual (o si la pila de mínimos está vacía). Al hacer pop, extraiga también un elemento de la pila de mínimos si el valor extraído es igual al mínimo actual.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin()) # -3
ms.pop()
print(ms.top()) # 0
print(ms.getMin()) # -2Evaluar la notación polaca inversa
LeetCode 150 'Evaluar la notación polaca inversa' (postfija): los operandos se apilan; al encontrar un operador, extraiga dos operandos, aplique el operador y apile el resultado. El orden es importante en la resta y la división: el primer operando extraído es el operando derecho y el segundo es el izquierdo.
def evalRPN(tokens):
stack = []
ops = set(['+', '-', '*', '/'])
for tok in tokens:
if tok not in ops:
stack.append(int(tok))
else:
b = stack.pop() # right operand
a = stack.pop() # left operand
if tok == '+':
stack.append(a + b)
elif tok == '-':
stack.append(a - b)
elif tok == '*':
stack.append(a * b)
else: # division truncated toward zero
stack.append(int(a / b))
return stack[0]
print(evalRPN(['2','1','+','3','*'])) # 9
print(evalRPN(['4','13','5','/','+'])) # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+'])) # 22Decodificar una cadena (LeetCode 394)
LeetCode 394 'Decodificar una cadena': dada una cadena codificada como 3[a2[c]], expándala a accaccacc. Use dos pilas: una para los contadores de repeticiones y otra para las cadenas acumuladas. Al encontrar un dígito, forme el número completo. Al encontrar [, haga push de la cadena y el contador actuales. Al encontrar ], haga pop y repita el segmento actual. Cuando encuentre una letra, añádala a la cadena actual.
def decodeString(s):
count_stack = []
str_stack = []
current_str = ''
current_num = 0
for ch in s:
if ch.isdigit():
current_num = current_num * 10 + int(ch)
elif ch == '[':
count_stack.append(current_num)
str_stack.append(current_str)
current_str = ''
current_num = 0
elif ch == ']':
repeats = count_stack.pop()
current_str = str_stack.pop() + current_str * repeats
else:
current_str += ch
return current_str
print(decodeString('3[a]2[bc]')) # 'aaabcbc'
print(decodeString('3[a2[c]]')) # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'Temperaturas diarias (introducción a la pila monótona)
LeetCode 739 'Temperaturas diarias': para cada día, encuentre cuántos días faltan hasta una temperatura más alta. Una solución por fuerza bruta cuesta O(n²). Con una pila, recorra las temperaturas; para cada día, extraiga todas las entradas de la pila (índices de días) cuya temperatura sea menor que la de hoy. La respuesta para esos días extraídos es (hoy - día_extraído). Haga push del día actual. Las entradas restantes nunca encontraron un día más cálido; su respuesta es 0.
def dailyTemperatures(temps):
result = [0] * len(temps)
stack = [] # stores indices
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]Pila para el recorrido DFS
La pila de llamadas del DFS recursivo se puede sustituir por una pila explícita, lo que convierte el algoritmo en iterativo. Haga push de la raíz; mientras la pila no esté vacía, extraiga un nodo, procéselo y haga push de sus hijos (primero el derecho y después el izquierdo para procesarlos de izquierda a derecha). Este DFS iterativo se comporta igual que el DFS recursivo, pero evita el límite de recursión de Python en árboles profundos.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_iterative(root):
if not root:
return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right) # push right first
if node.left:
stack.append(node.left) # so left is processed first
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Complejidad temporal y espacial
Todas las operaciones de una pila (push, pop, peek e isEmpty) son O(1) amortizadas. Construir una pila de n elementos cuesta O(n). El espacio es O(n) en el peor caso, cuando se almacenan todos los elementos. En los problemas que utilizan una pila monótona, cada elemento se añade y se extrae como máximo una vez, lo que proporciona un tiempo total de O(n) en todas las iteraciones; no O(n²), como podría sugerir una lectura ingenua del bucle externo.
# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total
def count_ops(n):
pushes = pops = 0
stack = []
for i in range(n):
while stack and stack[-1] < i: # simulated decreasing condition
stack.pop()
pops += 1
stack.append(i)
pushes += 1
return pushes, pops
p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}') # <= 2000Rectángulo más grande en un histograma (introducción)
LeetCode 84 'Rectángulo más grande en un histograma' es el problema clásico de pilas más difícil. Para cada barra, el rectángulo que puede formar se extiende hacia la izquierda hasta encontrar una barra más baja y hacia la derecha hasta encontrar otra barra más baja. Una pila monótona registra los índices de las barras en orden creciente de altura. Cuando aparece una barra más baja, extraiga elementos y calcule el rectángulo usando la altura de la barra extraída. La pila proporciona los límites izquierdo y derecho en O(1) por extracción.
def largestRectangleArea(heights):
stack = [] # indices, increasing heights
result = 0
heights = heights + [0] # sentinel forces all pops
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2,1,5,6,2,3])) # 10
print(largestRectangleArea([2,4])) # 4Estrategia para entrevistas sobre problemas de pilas
Los problemas de pilas suelen presentarse como 'procesar desde dentro hacia fuera' o 'encontrar el siguiente elemento mayor/menor'. Algunas señales de que una pila puede ser útil son: necesita el elemento visto más recientemente, está emparejando elementos (corchetes, etiquetas) o busca un tiempo O(n) en un problema que, de forma ingenua, requiere bucles anidados O(n²). En particular, las pilas monótonas convierten la tarea de 'encontrar el elemento mayor/menor más cercano para cada elemento' de O(n²) a O(n).
En una entrevista, indique claramente el invariante de la pila: 'Mantendré una pila de índices en orden decreciente de altura'.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que las listas de Python implementan push, pop y peek en O(1), por lo que son pilas ideales, que los paréntesis válidos y la pila mínima son los dos problemas canónicos de pilas en entrevistas, y que las pilas monótonas resuelven problemas del siguiente elemento mayor en O(n), haciendo push y pop de cada elemento como máximo una vez. A continuación, crearemos colas con el deque de Python y resolveremos el máximo de una ventana deslizante.
Preguntas frecuentes
¿La lección «Implementación y aplicaciones de pilas» es gratis?
Sí — el texto completo de «Implementación y aplicaciones de pilas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Implementación y aplicaciones de pilas»?
Implemente una pila con push/pop/peek y resuelva valid-parentheses, min-stack y la evaluación de notación polaca inversa. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Implementación y aplicaciones de pilas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Implementación y aplicaciones de pilas
- Implementación de colas y deque
- Patrón de pila monótona
- Simulación mutua de pilas y colas