> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

# Estructuras de datos: pila, cola y árbol binario de búsqueda

> Pila (LIFO), cola (FIFO) y árbol binario de búsqueda explicados: operaciones push, pop, encolar, desencolar, insertar, buscar y eliminar, recorridos inorden, preorden y postorden, y su coste.

<Card title="Abrir el simulador" icon="flask" href="https://simulab.es/programacion/estructuras-datos">
  Pila, cola y árbol binario de búsqueda: inserta, extrae, busca, elimina y recorre paso a paso.
</Card>

Un mismo conjunto de datos se puede guardar de muchas formas, y elegir bien hace que un programa sea rápido o lentísimo. La **pila**, la **cola** y el **árbol binario de búsqueda** son tres estructuras básicas, cada una pensada para un tipo de acceso distinto.

## Lo que vas a aprender

* Las operaciones de una pila y una cola, y dónde se usan.
* Cómo se organiza un árbol binario de búsqueda.
* Insertar, buscar y eliminar en un árbol.
* Los recorridos inorden, preorden y postorden.
* El coste de cada operación.

## Cómo se usa el simulador

* Elige **Pila**, **Cola** o **Árbol binario**.
* **Pila**: escribe un valor y usa **push** (meter), **pop** (sacar) y **peek** (mirar la cima).
* **Cola**: encola y desencola.
* **Árbol**: inserta, busca, elimina y recorre (inorden, preorden, postorden) paso a paso, viendo qué nodos se visitan.
* Cada estructura incluye ejemplos de **dónde se usa**.

## Fundamentos teóricos

### Pila (LIFO)

*Last In, First Out*: el último en entrar es el primero en salir, como una pila de platos. Solo se accede a la **cima**.

| Operación | Qué hace | Coste |
| - | - | - |
| push(x) | Mete x en la cima | $O(1)$ |
| pop() | Saca el de la cima | $O(1)$ |
| peek() | Mira la cima sin sacarla | $O(1)$ |

**Usos**: deshacer (Ctrl+Z), historial del navegador, la pila de llamadas de un programa, comprobar paréntesis equilibrados.

### Cola (FIFO)

*First In, First Out*: el primero en entrar es el primero en salir, como la cola del supermercado. Se mete por el **final** y se saca por el **principio**.

**Usos**: cola de impresión, procesos esperando la CPU, mensajes, la búsqueda en anchura (BFS) en grafos.

### Árbol binario de búsqueda (ABB)

Cada nodo tiene como mucho dos hijos, y se cumple:

* Todo lo del subárbol **izquierdo** es **menor** que el nodo.
* Todo lo del subárbol **derecho** es **mayor**.

**Buscar**: se compara con la raíz y se baja a la izquierda o a la derecha. **Insertar**: se busca hasta llegar a un hueco vacío.

**Eliminar** tiene tres casos:

1. **Hoja**: se quita.
2. **Un hijo**: el hijo ocupa su lugar.
3. **Dos hijos**: se sustituye por su **sucesor** (el menor del subárbol derecho) o su predecesor, y se elimina este.

### Coste en un árbol

Las operaciones recorren un camino desde la raíz: su coste es la **altura** del árbol. Si está equilibrado, $O(\log n)$. Si se insertan los datos ya ordenados, el árbol degenera en una lista y el coste es $O(n)$.

### Recorridos

| Recorrido | Orden | Utilidad |
| - | - | - |
| **Inorden** | izquierdo, raíz, derecho | Da los valores **ordenados** |
| **Preorden** | raíz, izquierdo, derecho | Copiar el árbol |
| **Postorden** | izquierdo, derecho, raíz | Borrar el árbol, evaluar expresiones |

## Ejemplos resueltos

<AccordionGroup>
  <Accordion title="Ejemplo 1 · Recorridos" defaultOpen>
    Se insertan 50, 30, 70, 20 y 40. El árbol queda con 50 en la raíz, 30 y 70 como hijos, y 20 y 40 bajo el 30.

    * Preorden: 50, 30, 20, 40, 70.
    * Inorden: 20, 30, 40, 50, 70 (ordenado).
    * Postorden: 20, 40, 30, 70, 50.
  </Accordion>

  <Accordion title="Ejemplo 2 · Pila">
    push(12), push(7), push(31), pop(), push(42), pop(). ¿Qué queda? 12 y 7 (cima 7). Los pop sacaron 31 y 42.
  </Accordion>

  <Accordion title="Ejemplo 3 · Paréntesis">
    Para comprobar `( [ ] { } )`, se apila cada apertura y, en cada cierre, se desapila y se comprueba que coincide. Si al final la pila está vacía, están equilibrados.
  </Accordion>
</AccordionGroup>

## Experimenta con el simulador

<Steps>
  <Step title="LIFO y FIFO">
    Mete 1, 2, 3 en la pila y en la cola y saca los tres. ¿En qué orden salen?
  </Step>

  <Step title="Árbol degenerado">
    Inserta 10, 20, 30, 40, 50 en un árbol vacío. ¿Qué forma tiene?
  </Step>

  <Step title="Eliminar con dos hijos">
    Elimina la raíz de un árbol con varios nodos. ¿Quién ocupa su lugar?
  </Step>
</Steps>

## Errores frecuentes

* **Hacer pop en una pila vacía** (*underflow*).
* **Confundir pila y cola.**
* **Pensar que un ABB siempre es $O(\log n)$**: solo si está equilibrado.

## Herramientas relacionadas

<CardGroup cols={3}>
  <Card title="Recorridos de grafos" icon="diagram-project" href="/programacion/algoritmos/grafos">
    BFS con cola, DFS con pila.
  </Card>

  <Card title="Árbol binario enhebrado" icon="sitemap" href="/programacion/java/arbol-enhebrado">
    Recorrer sin pila.
  </Card>

  <Card title="ArrayList y lista enlazada" icon="list" href="/programacion/java/listas">
    Otras estructuras lineales.
  </Card>
</CardGroup>


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.