Pilha e Fila
Nota Conceitual:
Pilha e fila são estruturas lineares que restringem onde você pode inserir e remover elementos, ao contrário de um array ou lista comum onde você acessa qualquer posição livremente. Isso não é uma limitação boba: restringir a API é o que torna essas estruturas previsíveis e baratas de usar (inserção e remoção em O(1)).
Uma pilha segue a lógica LIFO (last-in, first-out): você só insere e remove pelo topo. Pensa numa pilha de pratos, o último que você colocou é o primeiro que sai. As operações básicas são push (empilhar), pop (desempilhar) e peek/top (ver o topo sem remover). Uma fila segue FIFO (first-in, first-out): insere num extremo (final) e remove no outro (início), como fila de banco. As operações equivalentes são push/enqueue, pop/dequeue e peek/front.
Ambas podem ser implementadas com array ou com lista encadeada. Com array, pilha é trivial (empilha e desempilha no final do vetor), mas fila com array puro tem o problema de deslocar todos os elementos ao remover do início, a menos que você use um array circular. Com lista encadeada (principalmente duplamente encadeada), tanto pilha quanto fila ficam em O(1) sem esse problema, ao custo de memória extra para os ponteiros.
Vale destacar um uso clássico de pilha em programação competitiva: verificar balanceamento de símbolos (parênteses, colchetes, chaves) e simular estruturas com comportamento de aninhamento, como recursão, DFS iterativo ou parsing de expressões. Fila aparece bastante em BFS e em simulações de processos sequenciais (fila de atendimento, buffer de mensagens). Também existe a variante fila de prioridade (heap), que foge do escopo direto desta semana mas vale mencionar como próximo passo natural.
stack<int> pilha;
pilha.push(1);
pilha.push(2);
pilha.pop(); // remove o 2
cout << pilha.top(); // imprime 1
queue<int> fila;
fila.push(1);
fila.push(2);
fila.pop(); // remove o 1
cout << fila.front(); // imprime 2