🌐 Inicio · 📚 Clases · 🧬 Atlas · 🧭 Rutas · 📝 Autoevaluación · 🔎 Buscar

Clase 096 — Pilas y colas

Parte 6 — Datos y estructuras · ⏱️ Duración estimada: 90 min · Nivel: Intermedio ✅ Clase construida — 10 implementaciones del núcleo verificadas contra casos.json.

🎯 Objetivo

Comprender la pila y la cola no como dos colecciones más, sino como dos disciplinas de acceso: estructuras que deliberadamente restringen dónde se puede insertar y de dónde se puede sacar, y que reciben algo valioso a cambio de esa renuncia. La pila es LIFO —last in, first out, el último que entra es el primero que sale— y la cola es FIFO —first in, first out, el primero que entra es el primero que sale—. Cormen las presenta juntas en §10.1 de Introduction to Algorithms precisamente porque comparten la idea de fondo: son arreglos o listas a los que se les prohíbe el acceso por índice arbitrario para garantizar que sus operaciones cuesten O(1) en los extremos que sí se usan. En la pila, push y pop actúan sobre el mismo extremo; en la cola, se encola por un lado y se desencola por el otro. Esa asimetría es todo el tema. El porqué de la estructura es esa promesa de coste constante: cuando un algoritmo solo necesita «el último» o «el primero», pagar O(n) por buscarlo sería absurdo, y la pila y la cola lo entregan en tiempo fijo.

📚 Resultados de aprendizaje

Al finalizar, podrás:

  1. Simular una pila y una cola.
  2. Explicar LIFO frente a FIFO.
  3. Reconocer sus usos típicos.

🗺️ Temas

# Tema Por qué importa
1 Pila (LIFO) Último en entrar, primero en salir
2 Cola (FIFO) Primero en entrar, primero en salir
3 push/pop, enqueue/dequeue Sus operaciones

📖 Definiciones y características

🧩 Situación

Piensa en el botón «deshacer» de un editor: cada cambio se apila encima del anterior y al pulsar Ctrl+Z se recupera el último —una pila pura, porque solo interesa el movimiento más reciente. Piensa ahora en una cola de impresión o en el planificador de tareas de un servidor: los trabajos se atienden en el orden en que llegaron, sin que el último en pedir se cuele delante —una cola, porque la justicia aquí es temporal. La misma lista de enteros, sometida a una u otra disciplina, sale en orden opuesto, y ese contraste es exactamente lo que el problema de hoy vuelve observable: leemos una secuencia y la emitimos dos veces, una en orden LIFO (pila) y otra en orden FIFO (cola). El ejercicio es mínimo a propósito para que la atención caiga sobre la disciplina de acceso, no sobre un algoritmo complejo.

🧮 Modelo

Especificación y verificación en casos.json:

stdin esperado
1 2 3 pila=3-2-1 cola=1-2-3
5 pila=5 cola=5
1 2 3 4 pila=4-3-2-1 cola=1-2-3-4

📐 Algoritmo (pseudocódigo neutral)

LEER lista ; pila <- sacar en LIFO ; cola <- sacar en FIFO

🌐 Implementaciones idiomáticas — el código a la vista

Mismo algoritmo, forma idiomática en cada lenguaje. Todas producen la salida de casos.json. Cada bloque es el archivo real de implementaciones/: el enlace de cada lenguaje abre su fuente, y el comando de al lado lo ejecuta.

Python · python/main.py · python main.py

import sys

nums = [int(x) for x in sys.stdin.read().split()]
pila = "-".join(str(x) for x in reversed(nums))
cola = "-".join(str(x) for x in nums)
print(f"pila={pila} cola={cola}")

🧬 El mismo programa en la familia Scripting dinámico: Ruby · Perl · Lua · Tcl · R

JavaScript · javascript/main.mjs · node main.mjs

import { readFileSync } from "node:fs";

const nums = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);
const pila = [...nums].reverse().join("-");
const cola = nums.join("-");
console.log(`pila=${pila} cola=${cola}`);

🧬 El mismo programa en la familia JavaScript / web: Dart · ActionScript

TypeScript · typescript/main.ts · pnpm exec tsx main.ts

import { readFileSync } from "node:fs";

const nums: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);
const pila = [...nums].reverse().join("-");
const cola = nums.join("-");
console.log(`pila=${pila} cola=${cola}`);

🧬 El mismo programa en la familia JavaScript / web: Dart · ActionScript

Java · java/Main.java · java Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] p = br.readLine().trim().split("\\s+");
        List<String> l = new ArrayList<>();
        for (String s : p) l.add(s);
        List<String> rev = new ArrayList<>(l);
        java.util.Collections.reverse(rev);
        System.out.println("pila=" + String.join("-", rev) + " cola=" + String.join("-", l));
    }
}

🧬 El mismo programa en la familia JVM: Kotlin · Scala · Groovy · Clojure

C# · csharp/Program.cs · dotnet run

using System;
using System.Linq;

string[] p = Console.In.ReadToEnd()
    .Split(new[] { ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);
string pila = string.Join("-", p.Reverse());
string cola = string.Join("-", p);
Console.WriteLine($"pila={pila} cola={cola}");

🧬 El mismo programa en la familia .NET: F# · VB.NET

Go · go/main.go · go run main.go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

func main() {
    line, _ := bufio.NewReader(os.Stdin).ReadString('\n')
    f := strings.Fields(line)
    rev := make([]string, len(f))
    for i, x := range f {
        rev[len(f)-1-i] = x
    }
    fmt.Printf("pila=%s cola=%s\n", strings.Join(rev, "-"), strings.Join(f, "-"))
}

🧬 El mismo programa en la familia Sistemas: Zig · Nim · D

Rust · rust/main.rs · rustc main.rs -o main && ./main

use std::io::Read;

fn main() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let nums: Vec<&str> = s.split_whitespace().collect();
    let mut rev = nums.clone();
    rev.reverse();
    println!("pila={} cola={}", rev.join("-"), nums.join("-"));
}

🧬 El mismo programa en la familia Sistemas: Zig · Nim · D

C · c/main.c · cc main.c -o main && ./main

#include <stdio.h>

int main(void) {
    long v[1024];
    int n = 0;
    while (scanf("%ld", &v[n]) == 1) n++;
    printf("pila=");
    for (int i = n - 1; i >= 0; i--) {
        if (i < n - 1) printf("-");
        printf("%ld", v[i]);
    }
    printf(" cola=");
    for (int i = 0; i < n; i++) {
        if (i > 0) printf("-");
        printf("%ld", v[i]);
    }
    printf("\n");
    return 0;
}

🧬 El mismo programa en la familia C / llaves: C++ · Objective-C

SQL · sql/main.sql · sqlite3 :memory: < main.sql

-- SQL: orden descendente (pila) y ascendente (cola) por posición.
WITH nums(pos, x) AS (VALUES (1, 1), (2, 2), (3, 3))
SELECT 'pila=' || (SELECT group_concat(x, '-') FROM (SELECT x FROM nums ORDER BY pos DESC))
     || ' cola=' || (SELECT group_concat(x, '-') FROM (SELECT x FROM nums ORDER BY pos ASC)) AS resultado;

🧬 El mismo programa en la familia Lógica y declarativa: Prolog · Datalog

PHP · php/main.php · php main.php

<?php
$nums = preg_split('/\s+/', trim(fgets(STDIN)));
$pila = implode("-", array_reverse($nums));
$cola = implode("-", $nums);
echo "pila=$pila cola=$cola\n";

🧬 El mismo programa en la familia Scripting dinámico: Ruby · Perl · Lua · Tcl · R

SQL es declarativo: no lee de stdin como los demás; su implementación muestra la misma idea sobre una tabla de casos, y el verificador la marca como ilustrativa.

🧪 Laboratorio guiado: del código a la salida

Sigamos el caso 1 2 3, que debe producir pila=3-2-1 cola=1-2-3. Las diez implementaciones comparten una idea: la cola es la secuencia tal cual (FIFO conserva el orden de llegada) y la pila es esa misma secuencia invertida (LIFO devuelve el último primero). Mirar tres lenguajes revela cómo cada modelo de memoria expresa esa inversión.

En Python, sys.stdin.read().split() produce la lista [1, 2, 3]. La línea reversed(nums) no crea una copia nueva: devuelve un iterador que recorre la lista de atrás hacia adelante, y "-".join(...) lo consume para formar "3-2-1". La cola recorre la lista en su orden natural y produce "1-2-3". Aquí reversed es el sustituto elegante de ir haciendo pop() sobre una pila real: sacar repetidamente de la cima de [1, 2, 3] daría 3, luego 2, luego 1 —exactamente el orden invertido.

En Go, no hay función reverse sobre slices en la biblioteca clásica, así que el código la escribe a mano: rev := make([]string, len(f)) reserva un slice del mismo tamaño y el bucle rev[len(f)-1-i] = x coloca cada token en su posición espejo —el primero (i=0) va al final, el último al principio. Es la inversión hecha con aritmética de índices, sin azúcar sintáctico. strings.Join(rev, "-") da "3-2-1" y strings.Join(f, "-") da "1-2-3".

En C, la disciplina de pila se ve todavía más desnuda. Los enteros se guardan en long v[1024] y n cuenta cuántos hay. Para la pila, el bucle for (int i = n - 1; i >= 0; i--) recorre el arreglo desde el final: eso es desapilar, ir tomando la cima que baja. Para la cola, for (int i = 0; i < n; i++) recorre desde el frente: eso es desencolar en orden de llegada. El guion se intercala comprobando la posición (if (i < n - 1) y if (i > 0)) para no dejar un - colgando. El resultado impreso es pila=3-2-1 cola=1-2-3.

Los tres coinciden carácter a carácter con lo que dicta casos.json, y el verificador lo comprueba para las diez implementaciones.

🔬 Comparación

Clase de diferencia Observación entre lenguajes
Sintáctica append/pop (Python), push/shift (JS), Deque (Java).
Semántica La pila saca por el final; la cola por el frente.
Paradigmática SQL ordena por la posición ascendente o descendente.

La diferencia más honda entre los diez lenguajes no está en cómo invierten una lista, sino en qué colección nativa ofrecen para una pila o una cola de verdad. Python usa list como pila (append/pop son O(1) por el final) pero desaconseja usarla como cola, porque pop(0) es O(n) al desplazar todo; para eso está collections.deque, con O(1) por ambos extremos (Ramalho lo detalla en Fluent Python). Java separa las dos ideas: ArrayDeque es hoy la pila y la cola recomendadas, mientras la vieja clase Stack sobrevive por compatibilidad (Bloch la desaconseja por heredar de Vector y estar sincronizada sin necesidad). C# ofrece Stack<T> y Queue<T> explícitos; Go resuelve la pila con un slice (append y recorte s[:len(s)-1]) y, para la cola eficiente, obliga a container/list o un buffer circular propio; Rust brinda Vec<T> como pila y VecDeque<T> como cola. El otro eje es valor frente a referencia: en Rust y Go la inversión trabaja sobre datos que se poseen o se copian explícitamente (nums.clone() en Rust deja el original intacto), mientras en Java o Python Collections.reverse y list.reverse() mutarían la lista en sitio —de ahí que el código copie antes de invertir, para no destruir la versión FIFO.

🧬 El concepto en la familia

Casi todos los lenguajes distinguen la pila «barata sobre arreglo» de la cola «que necesita cuidado en ambos extremos». En Go, una pila es un slice con append/recorte y una cola honesta exige una deque o container/list, porque desencolar por el frente de un slice copiando es O(n). En C++, la biblioteca estándar ofrece std::stack y std::queue como adaptadores: no son contenedores propios, sino envoltorios que restringen la interfaz de un deque subyacente para exponer solo push/pop o push/front, que es la esencia misma de estas estructuras —tomar algo general y limitar deliberadamente lo que se puede hacer con ello. Reconocer ese patrón (una deque generalista debajo, una interfaz restringida encima) ayuda a leer la biblioteca de cualquier lenguaje: la pila y la cola casi nunca son tipos primitivos, sino disciplinas impuestas sobre una colección más flexible.

✅ Prueba común

Los mismos casos para todas las implementaciones: casos.json. Verifica la equivalencia:

python scripts/verificar_equivalencia.py 096

🧪 Reto de transferencia

Detalle en reto.md.

⚠️ Errores comunes

❓ Preguntas frecuentes

🔗 Referencias

Libros de la parte:

Libros de los lenguajes del núcleo:

⏮️ Clase 095 · 📂 Parte · 📚 Índice · 🌐 Atlas · Clase 097 ⏭️