Implementación de colas y deque
Construya una cola con el deque de Python, implemente una cola circular y resuelva el máximo de una ventana deslizante mediante un deque monótono.
Implementación de colas y deque es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 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 cola
Una cola es una estructura de datos de tipo primero en entrar, primero en salir (FIFO). El primer elemento encolado es el primero en desencolarse, como en una fila de espera. Las operaciones principales son enqueue (añadir al final) y dequeue (retirar del frente). Ambas deben ser O(1) para que la cola sea eficiente.
Usar una lista de Python como cola puede parecer tentador, pero es incorrecto: list.pop(0) cuesta O(n) porque desplaza todos los elementos. La herramienta adecuada es collections.deque, que proporciona appendleft, append, popleft y pop en O(1).
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])Clase Queue usando deque
Envuelva deque en una clase Queue con operaciones con nombre para ajustarse a lo que esperan los entrevistadores. Internamente, enqueue llama a append y dequeue llama a popleft. La operación peek lee queue[0] sin retirarlo.
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2BFS con una cola
La aplicación clásica de una cola es la búsqueda en anchura (BFS). Encole la raíz; mientras la cola no esté vacía, desencole un nodo, procéselo y encole sus vecinos no visitados. Como los nodos se procesan nivel por nivel, BFS encuentra de forma natural la ruta más corta en un grafo no ponderado. La cola siempre contiene nodos de como máximo dos niveles adyacentes.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]Cola circular (LeetCode 622)
LeetCode 622 'Diseñar una cola circular': implemente una cola de capacidad fija que vuelva al principio al alcanzar el final. Use un array de tamaño k y dos punteros: head y tail. Encole en tail, desencole en head y calcule las posiciones módulo k. Una variable count distingue entre llena y vacía (en ambos casos se cumple head == tail módulo k si no se utiliza esta variable).
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # TrueMáximo de una ventana deslizante con un deque monótono
LeetCode 239 'Máximo de una ventana deslizante': para cada ventana de tamaño k, encuentre el elemento máximo. La fuerza bruta cuesta O(n*k). El enfoque O(n) utiliza un deque monótono decreciente que almacena índices. Para cada elemento nuevo: elimine del frente los índices que estén fuera de la ventana; elimine del final los índices con valores menores (nunca podrán ser el máximo en ninguna ventana futura). El frente siempre contiene el máximo.
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]¿Por qué usar un deque y no solo una lista para una cola?
list.pop(0) de Python elimina el primer elemento en O(n) porque todos los elementos restantes deben desplazarse una posición a la izquierda. Para n inserciones y n eliminaciones, esto produce un coste total O(n²). collections.deque es una lista doblemente enlazada formada por bloques de tamaño fijo; popleft cuesta O(1) porque solo ajusta un puntero. En un BFS sobre un grafo con 10^5 nodos, la diferencia entre O(n) y O(n²) es la diferencia entre 100 ms y 100 segundos.
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')Recorrido por niveles de un árbol binario (LeetCode 102)
LeetCode 102 'Recorrido por niveles de un árbol binario': devuelva todos los valores de los nodos nivel por nivel. Use una cola; al inicio de cada nivel, registre el tamaño de la cola (es decir, cuántos nodos hay en ese nivel). Desencole exactamente esa cantidad de nodos, recopile sus valores y encole sus hijos. Repita hasta que la cola esté vacía.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]Cola de prioridad con heapq
El módulo heapq de Python proporciona un min-heap (cola de prioridad): el elemento más pequeño siempre se extrae primero. heapq.heappush(h, item) añade un elemento en O(log n) y heapq.heappop(h) elimina el mínimo en O(log n). Para tareas como el algoritmo de Dijkstra y los problemas de top-k, heapq sustituye a la cola simple.
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')Patrón Wallpaper: cola para Word Ladder
LeetCode 127, «Word Ladder»: encuentre el número mínimo de sustituciones de un solo carácter necesarias para transformar una palabra en otra, utilizando únicamente palabras del diccionario. Modele el problema como un grafo cuyos aristas conectan palabras que difieren en un carácter. BFS en este grafo encuentra el camino más corto (el número mínimo de pasos) en O(n * L²), donde n es el tamaño del diccionario y L es la longitud de las palabras.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5deque como cola de doble extremo
collections.deque es una cola de doble extremo (deque): permite añadir y eliminar elementos eficientemente por ambos extremos. Utilice los métodos appendleft y popleft para el frente, y append y pop para el extremo posterior. Esto permite utilizar deque tanto como una cola FIFO (appendright + popleft) como como una pila LIFO (append + pop). El máximo de una ventana deslizante utiliza ambos extremos: elimina los índices antiguos por la izquierda y los valores menores por la derecha.
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]Resumen: cola frente a deque frente a heap
Elija la herramienta adecuada para el problema. Utilice una cola simple (deque) para el procesamiento FIFO y BFS. Utilice una deque monótona cuando necesite el máximo o el mínimo de una ventana deslizante; mantiene un invariante ordenado eliminando los elementos dominados. Utilice una cola de prioridad (heapq) cuando necesite el mínimo o el máximo global, independientemente del orden, como en Dijkstra o en problemas de top-k. Saber cuál utilizar y por qué es una habilidad clave que se evalúa en las entrevistas.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Repaso de la lección
En esta lección ha aprendido: collections.deque proporciona operaciones de encolado y desencolado en O(1), por lo que es la implementación correcta de una cola en Python, BFS utiliza una cola para procesar los nodos nivel por nivel y encontrar los caminos más cortos en grafos no ponderados, y una deque monótona decreciente resuelve el máximo de una ventana deslizante en O(n) eliminando los índices dominados. A continuación exploraremos en profundidad el patrón de la pila monótona.
Preguntas frecuentes
¿La lección «Implementación de colas y deque» es gratis?
Sí — el texto completo de «Implementación de colas y deque» 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 de colas y deque»?
Construya una cola con el deque de Python, implemente una cola circular y resuelva el máximo de una ventana deslizante mediante un deque monótono. 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 2 de 4.
¿Cuánto tiempo toma la lección «Implementación de colas y deque»?
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