Data Structure & Algorithms
Stacks, queues y deques con sus invariantes, implementaciones eficientes, buffers circulares y estructuras monotónicas para ventanas y candidatos.
Stack, queue y deque restringen desde qué extremos puedes insertar y retirar elementos. Esa restricción crea un orden de procesamiento útil.
Stack → LIFO → último en entrar, primero en salir
Queue → FIFO → primero en entrar, primero en salir
Deque → operaciones en ambos extremosNo son solo “arrays con métodos”. Son interfaces con invariantes. La implementación elegida determina si una operación realmente cuesta O(1).
Una stack opera desde un único extremo llamado top.
top
↓
[30]
[20]
[10]Operaciones habituales:
push(value): insertar arriba;pop(): retirar el valor superior;peek(): consultar sin retirar;size;isEmpty().En JavaScript, push y pop operan sobre el final del array y tienen costo amortizado O(1).
class Stack<T> {
private readonly values: T[] = [];
get size(): number {
return this.values.length;
}
isEmpty(): boolean {
return this.values.length === 0;
}
push(value: T): void {
this.values.push(value);
}
pop(): T | undefined {
return this.values.pop();
}
peek(): T | undefined {
return this.values.at(-1);
}
}push: O(1) amortizado; una expansión interna puede costar O(n).pop: O(1).peek: O(1).O(n).O(n).function hasBalancedBrackets(text: string): boolean {
const opening = new Set(["(", "[", "{"]);
const expectedOpening = new Map([
[")", "("],
["]", "["],
["}", "{"],
]);
const stack: string[] = [];
for (const character of text) {
if (opening.has(character)) {
stack.push(character);
continue;
}
const expected = expectedOpening.get(character);
if (expected === undefined) continue;
if (stack.pop() !== expected) return false;
}
return stack.length === 0;
}Invariante: la stack contiene los delimitadores abiertos que todavía no han sido cerrados, en el orden necesario para cerrarlos.
Tiempo: O(n). Memoria: O(n) peor caso.
Una queue inserta por back y retira por front.
front back
↓ ↓
[10] ← sale [20] [30] ← entraOperaciones:
enqueue(value);dequeue();front();size;isEmpty().queue.shift();Puede desplazar todos los elementos restantes y costar O(n). Usar push y shift no garantiza una queue eficiente.
Una opción sencilla para algoritmos de una sola ejecución es un array con índice de lectura:
const queue = [start];
let head = 0;
while (head < queue.length) {
const current = queue[head];
head += 1;
// Enqueue with queue.push(...)
}Las posiciones procesadas permanecen en el array hasta terminar. Es eficiente en tiempo, pero no reutiliza memoria durante una queue de larga duración.
class Queue<T> {
private readonly values = new Map<number, T>();
private head = 0;
private tail = 0;
get size(): number {
return this.tail - this.head;
}
isEmpty(): boolean {
return this.size === 0;
}
enqueue(value: T): void {
this.values.set(this.tail, value);
this.tail += 1;
}
dequeue(): T | undefined {
if (this.isEmpty()) return undefined;
const value = this.values.get(this.head);
this.values.delete(this.head);
this.head += 1;
if (this.head === this.tail) {
this.head = 0;
this.tail = 0;
}
return value;
}
front(): T | undefined {
return this.values.get(this.head);
}
}Las operaciones son promedio O(1) por depender de Map. Una implementación de alto rendimiento suele usar un circular buffer para mejor localidad de memoria.
FIFO describe el orden lógico. Un sistema real puede añadir prioridad, reintentos o múltiples consumidores y dejar de ser una queue FIFO estricta.
Una double-ended queue permite insertar y retirar en ambos extremos.
pushFront ← [A, B, C] → pushBack
popFront ← → popBackEs útil para:
Un circular buffer reutiliza un array fijo. Los índices vuelven al inicio mediante módulo.
capacity = 5
[ C ][ D ][ ][ A ][ B ]
tail headclass CircularQueue<T> {
private readonly buffer: Array<T | undefined>;
private head = 0;
private tail = 0;
private count = 0;
constructor(private readonly capacity: number) {
if (!Number.isInteger(capacity) || capacity <= 0) {
throw new RangeError("capacity must be a positive integer");
}
this.buffer = Array(capacity);
}
get size(): number {
return this.count;
}
isEmpty(): boolean {
return this.count === 0;
}
isFull(): boolean {
return this.count === this.capacity;
}
enqueue(value: T): boolean {
if (this.isFull()) return false;
this.buffer[this.tail] = value;
this.tail = (this.tail + 1) % this.capacity;
this.count += 1;
return true;
}
dequeue(): T | undefined {
if (this.isEmpty()) return undefined;
const value = this.buffer[this.head];
this.buffer[this.head] = undefined;
this.head = (this.head + 1) % this.capacity;
this.count -= 1;
return value;
}
front(): T | undefined {
return this.isEmpty() ? undefined : this.buffer[this.head];
}
}count diferencia vacío de lleno cuando head === tail.
O(1);O(capacity);Una deque general puede usar un circular array que duplica capacidad al llenarse. Cada resize cuesta O(n), pero inserciones siguen siendo O(1) amortizadas.
La implementación requiere mantener:
Es más compleja que usar una librería, pero ofrece memoria contigua y operaciones eficientes.
Mantiene elementos en orden creciente o decreciente. Cuando llega un valor que vuelve inútiles a candidatos del tope, los retira.
Ejemplo: siguiente elemento mayor.
function nextGreater(values: readonly number[]): number[] {
const result = Array(values.length).fill(-1);
const stack: number[] = [];
for (let index = 0; index < values.length; index += 1) {
while (
stack.length > 0 &&
values[index] > values[stack.at(-1)!]
) {
result[stack.pop()!] = values[index];
}
stack.push(index);
}
return result;
}La stack guarda índices cuyos siguientes mayores aún no se conocen, y sus valores quedan en orden decreciente.
Aunque hay un while dentro de un for, cada índice entra y sale como máximo una vez:
O(n);O(n).Usos:
Mantiene candidatos para el máximo o mínimo de una ventana.
Para máximo, la deque guarda índices con valores decrecientes:
function slidingWindowMaximum(
values: readonly number[],
windowSize: number,
): number[] {
if (windowSize <= 0 || windowSize > values.length) return [];
const deque: number[] = [];
const result: number[] = [];
let head = 0;
for (let index = 0; index < values.length; index += 1) {
while (head < deque.length && deque[head] <= index - windowSize) {
head += 1;
}
while (
deque.length > head &&
values[deque.at(-1)!] <= values[index]
) {
deque.pop();
}
deque.push(index);
if (index >= windowSize - 1) {
result.push(values[deque[head]]);
}
}
return result;
}Esta versión usa array e índice head; para streams largos conviene compactar o usar una deque real.
Cada índice entra y sale una vez: tiempo O(n), memoria O(windowSize) activa.
Una singly linked list con head permite:
O(1);O(1) si conserva tail.Evita resize y desplazamientos, pero cada nodo añade memoria y peor localidad de caché. Un array dinámico suele ser más rápido para stack; una linked list puede ser útil si se necesitan nodos estables o tamaños impredecibles.
| Estructura | Extremos | Orden | Uso principal |
|---|---|---|---|
| Stack | Un extremo | LIFO | Regreso, nesting, DFS |
| Queue | Entra atrás, sale delante | FIFO | Capas, llegada, BFS |
| Deque | Ambos | Flexible | Ventanas y candidatos |
| Priority queue | Por interfaz | Prioridad | Extremo mínimo/máximo dinámico |
head === tail;undefined válidos;< frente a <= y manejo de iguales.shift() y declarar O(1).O(n²).¿Por qué el algoritmo de next greater es O(n) aunque tenga un while dentro del for?
Porque cada índice se inserta una vez y se retira como máximo una vez. El total de iteraciones del while a lo largo de toda la ejecución es O(n), no O(n) por cada vuelta externa.