Pular para conteúdo

Pilhas, Filas e Deques

Essas abstrações restringem os pontos pelos quais elementos entram e saem de uma sequência.

  • Uma pilha segue o princípio último a entrar, primeiro a sair: push, peek e pop.
  • Uma fila segue o princípio primeiro a entrar, primeiro a sair: enqueue, peek e dequeue.
  • Um deque permite inserção e remoção nas duas extremidades.

Coleções Java

ArrayDeque implementa Deque e Queue e é uma boa opção de uso geral para pilhas e filas. Ele não permite elementos null.

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
String top = stack.pop(); // "second"

Queue<String> queue = new ArrayDeque<>();
queue.add("first");
queue.add("second");
String head = queue.remove(); // "first"

As operações em qualquer extremidade têm custo amortizado O(1) em um deque baseado em array. As interfaces também oferecem pares como remove/poll e element/peek: o primeiro de cada par pode lançar uma exceção em um contêiner vazio, enquanto o segundo informa a ausência. Consulte o contrato da API Java para conhecer o comportamento exato.

Aplicações

  • pilhas: parsing de expressões, DFS, backtracking e simulação da pilha de chamadas;
  • filas: BFS, buffering e escalonamento de tarefas;
  • deques: algoritmos de janela deslizante e escalonadores com roubo de trabalho.

Exercícios

  1. Verifique o balanceamento de delimitadores com uma pilha.
  2. Implemente uma fila usando duas pilhas e analise o custo amortizado.
  3. Calcule os máximos de janelas deslizantes usando um deque monotônico.