LIFO — Last In, First Out

Pilha: acesso restrito ao topo

A pilha é um tipo abstrato no qual o último elemento inserido é o primeiro que pode ser removido.

push · pop · peek

Contrato da pilha

  • push(valor) insere um elemento no topo.
  • pop() remove e retorna o elemento do topo.
  • peek()/top consulta o topo sem removê-lo.
  • is_empty() informa se não há elementos.

Regra, não formato de memória

LIFO descreve a ordem das operações. A pilha pode usar um array, um array redimensionável ou nós encadeados.

Invariante: push e pop acontecem sempre na mesma extremidade lógica, o topo.

Duas implementações possíveis

ImplementaçãoComo representa o topopush/pop
ArrayÚltimo índice ocupado; não há ponteiro next em cada posição.O(1), amortizado no array redimensionável.
Lista encadeadaUma referência top aponta para o primeiro nó; cada nó aponta para o nó abaixo.O(1).

Laboratório: pilha encadeada

Nesta representação específica, top aponta para a célula superior. O campo next de cada célula aponta para a célula imediatamente abaixo.

Push e pop no topo

Operação
Ordem da base ao topo

    C++: vector como pilha

    Com std::vector, usamos push_back(), back() e pop_back() no final do vetor para obter o comportamento LIFO.

    C++17array redimensionável
    #include <vector>

std::vector<int> pilha;

pilha.push_back(10);       // push
pilha.push_back(20);

int topo = pilha.back();   // top
pilha.pop_back();          // pop

    C++: pilha encadeada

    Aqui o desenho do laboratório aparece diretamente no código: cada nó possui value e next.

    C++17nós encadeados
    #include <memory>
#include <stdexcept>

class PilhaEncadeada {
    struct No {
        int valor;
        std::unique_ptr<No> proximo;

        No(int valor, std::unique_ptr<No> proximo)
            : valor(valor), proximo(std::move(proximo)) {}
    };

    std::unique_ptr<No> topo_;

public:
    void push(int valor) {
        topo_ = std::make_unique<No>(valor, std::move(topo_));
    }

    int pop() {
        if (!topo_) throw std::runtime_error("pilha vazia");
        int valor = topo_->valor;
        topo_ = std::move(topo_->proximo);
        return valor;
    }

    int top() const {
        if (!topo_) throw std::runtime_error("pilha vazia");
        return topo_->valor;
    }
};

    Referências usadas