Listas, deques, pilhas e filas

Com os valores [4,7,2], uma pilha retira 2 primeiro e uma fila retira 4. Uma lista permite ainda procurar e alterar posições interiores. A escolha depende dessas operações, não apenas de conseguir guardar os três valores. Esta página mostra como manter as ligações sem perder nós e como analisar a fila de duas pilhas que o programa demonstra.

Lista simplesmente ligada

Cada nó guarda um valor e a ligação para o seguinte. Para inserires à frente, cria o novo nó com a ligação antiga e só depois altera primeiro. Para retirares a frente, guarda o nó antigo, avança primeiro e liberta o nó guardado. Estas operações custam $O(1)$.

Para removeres um nó, altera a ligação que chega a ele antes de o libertares. Em [5,3,5,8], remover todos os 5 começa pela cabeça: primeiro passa para o nó 3. A próxima remoção muda 3.seguinte para o nó 8. O resultado é [3,8].

No programa, ligacao é um apontador para essa ligação de entrada, seja primeiro ou o campo seguinte de um nó. Depois de apagar, volta a examinar a mesma ligação. Em [5,5,3], a primeira remoção deixa outro 5 na cabeça; avançar de imediato saltaria esse segundo nó. Só avança quando o nó atual é conservado.

Para remover a posição k, começa em &primeiro e avança k ligações, com 0<=k<tamanho. A posição zero altera a cabeça; a última exige chegar ao penúltimo nó. Ter um apontador para o fim não torna essa procura constante numa lista simples.

#include <iostream>
#include <vector>
class Lista {
    struct No { int valor; No* seguinte; };
    No* primeiro = nullptr;
public:
    Lista() = default;
    Lista(const Lista&) = delete;
    Lista& operator=(const Lista&) = delete;
    ~Lista() { while (primeiro) { No* p = primeiro; primeiro = p->seguinte; delete p; } }
    void inserirFrente(int x) { primeiro = new No{x, primeiro}; }
    void remover(int x) {
        No** ligacao = &primeiro;
        while (*ligacao) {
            No* p = *ligacao;
            if (p->valor == x) { *ligacao = p->seguinte; delete p; }
            else ligacao = &p->seguinte;
        }
    }
    void mostrar() const {
        for (No* p = primeiro; p; p = p->seguinte)
            std::cout << p->valor << (p->seguinte ? " " : "\n");
        if (!primeiro) std::cout << "vazia\n";
    }
};
class Fila {
    std::vector<int> entrada, saida;
public:
    void inserir(int x) { entrada.push_back(x); }
    bool retirar(int& x) {
        if (saida.empty()) {
            while (!entrada.empty()) {
                saida.push_back(entrada.back()); entrada.pop_back();
            }
        }
        if (saida.empty()) return false;
        x = saida.back(); saida.pop_back(); return true;
    }
};
int main() {
    Lista l;
    for (int x : {8, 5, 3, 5}) l.inserirFrente(x);
    l.remover(5); l.mostrar();
    Fila f; f.inserir(3); f.inserir(5);
    int x;
    if (f.retirar(x)) std::cout << x << '\n';
    f.inserir(8);
    while (f.retirar(x)) std::cout << x << '\n';
    std::cout << "vazia: " << !f.retirar(x) << '\n';
}

A cópia está desativada porque os nós têm um único proprietário, e o destrutor liberta-os de forma iterativa. Os apontadores para nós apagados deixam de ser válidos. Pesquisar e percorrer custam $\Theta(n)$ no pior caso. Retirar o último exige chegar ao penúltimo, mesmo que exista um apontador para o último, ou seja, alterar a ligação custa constante mas encontrar a ligação nem sempre custa constante.

Separar e intercalar por ligações

Separar uma lista não exige copiar os valores. Em [4A,1B,4C,2D,4E], conservar os primeiros dois nós deixa [4A,1B] na origem e [4C,2D,4E] noutra lista. As letras identificam ocorrências, mesmo quando a chave é igual.

Fixa o contrato de separar(resto,k): resto é uma lista distinta, inicialmente vazia; k<=0 transfere tudo; k>=tamanho conserva tudo na origem. Com 0<k<tamanho, avança até à posição k-1, guarda o seu sucessor como cabeça de resto e corta a ligação escrevendo nullptr. Atualiza os dois tamanhos. Sem o corte, as listas continuariam a possuir uma cadeia comum, e os seus destrutores poderiam libertar o mesmo nó duas vezes.

O caso interior custa $\Theta(k)$ para encontrar o corte e espaço $O(1)$. Os casos extremos custam $O(1)$ porque o tamanho já está guardado. Se resto tivesse nós, sobrescrever a sua cabeça perderia esses nós; a pré-condição de vazio impede essa fuga. A mesma lista não pode ser origem e destino.

Para intercalar duas listas já ordenadas, guarda uma frente em cada lista e uma ligação para o fim da saída. Escolhe a menor frente, avança apenas essa frente e liga o nó escolhido à saída. No empate, escolhe a lista esquerda para preservar a ordem inicial entre ocorrências. Quando uma lista acaba, liga o sufixo da outra de uma só vez. A origem direita fica vazia, porque os seus nós passaram a pertencer à lista de saída.

O invariante conserva um prefixo ordenado com os menores nós já escolhidos; as duas frentes iniciam as cadeias ainda por consumir. Guardar o sucessor antes de alterar uma ligação permite avançar sem perder os restantes nós. Não se cria nem apaga nenhum nó durante a separação ou a intercalação.

Com comprimentos a e b, a intercalação faz no máximo a+b-1 comparações se ambas forem não vazias. Nesse caso, o pior custo é $\Theta(a+b)$, com auxiliar $O(1)$. Se uma lista estiver vazia, basta ligar a cadeia da outra, em $O(1)$.

Não é limitado por $O(\min(a,b))$: para a=1 e b=m, põe [m+1] à esquerda e [1,…,m] à direita. Consomes os m nós da direita embora o menor comprimento seja sempre 1. Por exemplo, [100] contra [1,…,99] exige 99 comparações. Ligar o sufixo custa constante, mas uma lista curta pode não acabar cedo.

#include <cassert>
#include <iostream>
#include <vector>

template <class T> class Lista {
    struct No { T valor; No* seguinte; };
    No* primeiro = nullptr;
    int tamanho = 0;
public:
    Lista() = default;
    Lista(const Lista&) = delete;
    Lista& operator=(const Lista&) = delete;
    ~Lista() {
        while (primeiro) {
            No* p = primeiro;
            primeiro = p->seguinte;
            delete p;
        }
    }
    void inserirFrente(const T& x) {
        primeiro = new No{x, primeiro};
        ++tamanho;
    }
    int size() const { return tamanho; }
    std::vector<T> valores() const {
        std::vector<T> r;
        for (No* p = primeiro; p; p = p->seguinte) r.push_back(p->valor);
        return r;
    }
    // resto deve ser outra lista, inicialmente vazia.
    void separar(Lista& resto, int k) {
        assert(&resto != this && resto.tamanho == 0);
        if (k >= tamanho) return;
        if (k <= 0) {
            resto.primeiro = primeiro;
            resto.tamanho = tamanho;
            primeiro = nullptr;
            tamanho = 0;
            return;
        }
        No* ultimo = primeiro;
        for (int i = 1; i < k; ++i) ultimo = ultimo->seguinte;
        resto.primeiro = ultimo->seguinte;
        resto.tamanho = tamanho - k;
        ultimo->seguinte = nullptr;
        tamanho = k;
    }
    // As duas listas devem estar ordenadas e ser distintas.
    void intercalar(Lista& outra) {
        assert(&outra != this);
        No* esquerda = primeiro;
        No* direita = outra.primeiro;
        No** fim = &primeiro;
        while (esquerda && direita) {
            // Escolher esquerda no empate conserva a estabilidade.
            No*& escolhido = direita->valor < esquerda->valor ? direita : esquerda;
            *fim = escolhido;
            escolhido = escolhido->seguinte;
            fim = &(*fim)->seguinte;
        }
        *fim = esquerda ? esquerda : direita;
        tamanho += outra.tamanho;
        outra.primeiro = nullptr;
        outra.tamanho = 0;
    }
    void ordenar() {
        if (tamanho <= 1) return;
        Lista resto;
        separar(resto, tamanho / 2);
        ordenar();
        resto.ordenar();
        intercalar(resto);
    }
};

struct Registo {
    int chave;
    char etiqueta;
    bool operator<(const Registo& r) const { return chave < r.chave; }
};
void mostrar(const Lista<Registo>& lista) {
    for (auto r : lista.valores()) std::cout << r.chave << r.etiqueta << ' ';
    std::cout << "(tamanho " << lista.size() << ")\n";
}
int main() {
    Lista<Registo> lista, resto;
    // Inserir pela frente em ordem inversa cria [4A,1B,4C,2D,4E].
    for (Registo r : {Registo{4,'E'}, {2,'D'}, {4,'C'}, {1,'B'}, {4,'A'}})
        lista.inserirFrente(r);
    lista.separar(resto, 2);
    mostrar(lista); mostrar(resto);
    lista.ordenar(); resto.ordenar();
    lista.intercalar(resto);
    mostrar(lista); mostrar(resto);
    return 0;
}

O programa primeiro mostra [4A,1B] e [4C,2D,4E], depois ordena cada parte e intercala. A saída final é 1B 2D 4A 4C 4E, tamanho 5; a outra lista tem tamanho 0. No*& escolhido é uma referência ao apontador da frente escolhida, permitindo avançar essa frente. No** fim refere a cabeça de saída ou o campo seguinte do último nó escrito. O método ordenar compõe estas operações no mergesort de listas. As comparações do tipo T têm de definir uma ordem válida e não lançar exceções neste exemplo.

Lista dupla e circular

Numa lista duplamente ligada, cada nó guarda anterior e seguinte. Para inserires x entre a e b, ajusta as quatro ligações: a.seguinte=x, x.anterior=a, x.seguinte=b, b.anterior=x. Uma sentinela simplifica as extremidades, mas não representa um valor da lista.

Numa lista circular com sentinela, o vazio tem as duas ligações da sentinela para ela própria. O percurso termina quando regressa à sentinela, não quando encontra um apontador nulo. Para cada ligação entre nós vizinhos, seguir seguinte e depois anterior deve regressar ao nó de partida. Retirar um nó conhecido é constante; obter o nó por índice continua linear.

Deque, pilha e fila

Um deque permite inserir e retirar em ambas as extremidades. Não implica permitir inserções interiores eficientes. Um deque de array circular guarda um índice de início, um tamanho e uma capacidade. A posição lógica i corresponde a (inicio+i)%capacidade. Com capacidade 5, inicio=3 e [a,b,c] nas posições físicas 3,4,0, retirar a frente avança inicio para 4 e inserir d escreve na física 1. O percurso lógico 0,1,2 visita as físicas 4,0,1 após as operações. Reserva capacidade positiva antes de calcular o resto.

Uma pilha é LIFO: o último a entrar é o primeiro a sair. Num vetor, push_back, back e pop_back servem para a pilha. Uma fila é FIFO: entra no fim e sai pela frente. Num deque, push_back, front e pop_front evitam deslocar todos os elementos. top, front e pop exigem não vazio na biblioteca.

A pilha modela tarefas suspensas, desfazer operações e percursos em profundidade. A fila modela pedidos por ordem de chegada e percursos por camadas. Uma fila de prioridade escolhe uma prioridade, sem garantir FIFO nos empates.

Fila com duas pilhas

A pilha entrada recebe as inserções. A pilha saida tem no topo o elemento mais antigo. A classe Fila do programa implementa estas duas pilhas com vetores. Se saida estiver vazia, transfere todos os elementos de entrada para ela: a inversão põe o mais antigo no topo. Se ainda estiver vazia, a fila está vazia.

Uma retirada isolada pode mover n elementos e custar $\Theta(n)$. Ao longo de m operações, cada elemento entra em entrada, sai dela, entra em saida e sai dela no máximo uma vez por cada etapa. Assim, o número total de operações nas pilhas é $O(m)$, e o custo amortizado por operação da fila é $O(1)$. Se as pilhas são vetores dinâmicos, inclui também o seu custo amortizado de crescimento.

Aplicações de pilhas

Para verificares parênteses de vários tipos, empilha cada abertura. Ao leres um fecho, a pilha deve estar não vazia e o topo deve ser a abertura correspondente; depois retira-o. No fim, a pilha tem de estar vazia. ([)] tem o mesmo número de aberturas e fechos, mas é inválido porque ) não corresponde ao topo [. O invariante identifica a pilha com as aberturas ainda não fechadas, pela sua ordem de encaixe. Tempo $O(n)$ e espaço $O(n)$ no pior caso.

Uma pilha monótona resolve o próximo valor estritamente maior. Percorre da esquerda para a direita, guardando índices cujos valores ainda não encontraram resposta e estão por ordem não crescente. Quando chega um valor maior, retira todos os índices com valor menor e responde com a posição atual. Cada índice é inserido e retirado no máximo uma vez, logo o total é linear. Para [3,1,4,4,2], as posições seguintes maiores são [2,2,ausente,ausente,ausente]. Um valor igual não responde a «estritamente maior».

A mesma contagem de entradas e saídas explica por que um ciclo while dentro de um ciclo linear não implica, por si só, tempo quadrático.