# Listas, pilhas e filas

Listas ligadas com nós e apontadores, pilha LIFO, fila FIFO e a fila feita de duas pilhas.

Página: https://resumos.rgo.pt/cadeiras/aed/listas-pilhas-filas/

Um vetor guarda os elementos lado a lado e por isso insere devagar no meio: é preciso deslocar tudo. As estruturas desta página trocam o acesso direto por **nós** ligados por apontadores: inserir e remover no sítio certo passa a $O(1)$, à custa de só conseguir chegar aos elementos caminhando. É a primeira vez que implementas um tipo abstrato de dados do zero, por isso revê [apontadores e `new`/`delete`](https://resumos.rgo.pt/cadeiras/p/apontadores-memoria/) e [classes](https://resumos.rgo.pt/cadeiras/p/classes-objetos/) antes de continuares.

## Listas ligadas

Uma **lista ligada** é uma cadeia de nós, cada um com o valor e o apontador para o seguinte. A lista guarda só a **cabeça** (head); o último nó aponta para `nullptr`. Inserir no início é criar o nó e pendurá-lo à frente ($O(1)$); remover o primeiro é avançar a cabeça e libertar o nó ($O(1)$). Mas chegar à posição $i$ obriga a caminhar $i$ ligações: acesso e pesquisa são $O(n)$.

![Lista ligada com três nós: a cabeça aponta para o primeiro, cada nó aponta para o seguinte e a cauda aponta para vazio.](https://resumos.rgo.pt/cadeiras/aed/listas-pilhas-filas/figura-1.svg)

A **lista duplamente ligada** dá a cada nó também o apontador para o anterior. Gasta mais um apontador por nó, mas permite caminhar para trás e remover um nó conhecido em $O(1)$ (na simples, remover exige encontrar o antecessor). Com um apontador para a **cauda** (tail), inserir no fim também é $O(1)$.

O erro clássico é perder nós: se fizeres `cabeca = cabeca->seguinte` sem `delete` no nó antigo, a memória fica ocupada sem ninguém a apontar para ela. Cada `new` no código da lista precisa do seu `delete` na remoção e no destrutor. Desenha as setas no papel antes de as mexeres no código: mudar a ordem de duas atribuições de apontadores é a diferença entre inserir e partir a lista.

## Pilha e fila

A **pilha** (stack) é LIFO: o último a entrar é o primeiro a sair. Operações `push` (empilha), `pop` (desempilha) e `top` (espreita), todas $O(1)$. Serve onde a ordem é “desfazer”: chamadas de função, avaliação de expressões, voltar atrás numa pesquisa.

A **fila** (queue) é FIFO: o primeiro a entrar é o primeiro a sair. Operações `enqueue` (entra no fim), `dequeue` (sai da frente) e `front`, todas $O(1)$. Serve onde a ordem é “atender por chegada”: impressoras, pacotes de rede, a pesquisa em largura dos grafos.

Ambas se implementam sobre lista ligada (empilhar é inserir na cabeça; desenfileirar é remover da cabeça mantendo cauda para entrar no fim) ou sobre vetor circular. O tipo abstrato diz **o que** (LIFO contra FIFO); a implementação escolhe **como**.

## Uma fila feita de duas pilhas

Duas pilhas LIFO combinam-se numa fila FIFO. Mantém uma pilha de **entrada** e uma de **saída**: `enqueue` empilha na entrada; `dequeue` desempilha da saída, e se a saída estiver vazia, despeja a entrada toda para a saída primeiro (o que inverte a ordem duas vezes e a repõe). Simula `push 1, push 2, pop, push 3, pop, pop`, onde push é enqueue e pop é dequeue:

| Passo | Entrada (topo à direita) | Saída (topo à direita) | Devolve |
| --- | --- | --- | --- |
| push 1 | \[1\] | \[\] |  |
| push 2 | \[1, 2\] | \[\] |  |
| pop | \[\] | \[2, 1\] após despejo | 1 |
| push 3 | \[3\] | \[2\] |  |
| pop | \[3\] | \[\] | 2 |
| pop | \[\] | \[3\] após despejo | 3 |

![Três instantâneos da fila de duas pilhas: após os dois pushes, após o primeiro pop que devolve 1, e no fim com saída 1, 2, 3.](https://resumos.rgo.pt/cadeiras/aed/listas-pilhas-filas/figura-2.svg)

A saída é $1, 2, 3$: ordem de chegada, portanto FIFO. Cada elemento muda de pilha no máximo uma vez, por isso o custo é $O(1)$ **amortizado**: um `pop` isolado pode custar $O(n)$ no despejo, mas $n$ operações custam $O(n)$ no total. A distinção entre “cada operação” e “a média da sequência” é a ideia de amortização, que vais reencontrar nas tabelas de dispersão e nos vetores que crescem.

```cpp
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    vector<int> entrada, saida;
    auto enqueue = [&](int x) { entrada.push_back(x); };
    auto dequeue = [&]() {
        if (saida.empty())
            while (!entrada.empty()) {
                saida.push_back(entrada.back());
                entrada.pop_back();
            }
        int x = saida.back();
        saida.pop_back();
        return x;
    };
    enqueue(1); enqueue(2);
    cout << dequeue() << " ";
    enqueue(3);
    cout << dequeue() << " " << dequeue() << "\n";
}
```

O programa imprime `1 2 3`: segue a tabela linha a linha e confirma que cada `dequeue` devolve por ordem de chegada. Repara que o despejo da entrada para a saída só acontece quando a saída está vazia, que é exatamente o que mantém o custo amortizado.

Como escolher na prova

Vetor quando o acesso por índice domina e o tamanho é estável; lista quando as inserções e remoções no meio dominam; pilha quando precisas de desfazer; fila quando precisas de atender por ordem. Justifica sempre com o custo da operação dominante, não com preferência.

## Ver também

O [Visualgo](https://visualgo.net/en/list) simula inserções e remoções em listas, pilhas e filas com os apontadores à vista: corre a mesma sequência da tabela e vê as setas mexerem-se.