0Pricing
Java Academy · Aula

Operações de Deque: Pilha e Fila

Use LinkedList como uma Deque para implementar o comportamento de pilha (push/pop) e fila (offer/poll).

Operações de Deque: Pilha e Fila é uma aula grátis de Java Academy no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Java Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Java Academy inclui 4 aulas no total.

Fila de duas extremidades

Uma Deque (fila de duas extremidades) permite inserções e remoções nas duas extremidades. A interface Deque do Java é implementada por LinkedList e ArrayDeque.

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A"); // front
deque.addLast("B");  // back
deque.addFirst("Z"); // new front

System.out.println(deque); // [Z, A, B]

ArrayDeque versus LinkedList como fila de duas extremidades

ArrayDeque geralmente é preferível a LinkedList como fila de duas extremidades:

  • Não há sobrecarga de nós por elemento
  • Melhor localidade de cache
  • Um pouco mais rápida para operações de pilha e fila

Escolha LinkedList somente quando também precisar da interface List.

Operações de pilha com uma fila de duas extremidades

Use push (addFirst) e pop (removeFirst) para simular uma pilha LIFO. Evite a classe legada Stack — ela é sincronizada e obsoleta.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.pop());  // 3
System.out.println(stack.peek()); // 2 (no removal)
System.out.println(stack.pop());  // 2

Operações de fila com uma fila de duas extremidades

Use offer (addLast) e poll (removeFirst) para simular uma fila FIFO. offer retorna false em caso de falha; add lança uma exceção.

Deque<String> queue = new ArrayDeque<>();
queue.offer("task1");
queue.offer("task2");
queue.offer("task3");

System.out.println(queue.poll());  // task1
System.out.println(queue.poll());  // task2
System.out.println(queue.size());  // 1

Tabela de referência dos métodos de uma fila de duas extremidades

Deque fornece duas famílias de métodos — uma lança exceções e a outra retorna valores especiais:

  • addFirst/addLast versus offerFirst/offerLast
  • removeFirst/removeLast versus pollFirst/pollLast
  • getFirst/getLast versus peekFirst/peekLast

Prefira a família offer/poll/peek para evitar exceções em filas de duas extremidades vazias.

Exemplo real: desfazer/refazer com duas pilhas

Um caso de uso clássico de uma fila de duas extremidades: o histórico de desfazer é uma pilha. Refazer é outra pilha.

Deque<String> undo = new ArrayDeque<>();
Deque<String> redo = new ArrayDeque<>();

undo.push("type 'Hello'");
undo.push("type ' World'");

String action = undo.pop();
System.out.println("Undone: " + action); // type ' World'
redo.push(action);

System.out.println("Redo top: " + redo.peek()); // type ' World'

Verificação de palíndromos com uma fila de duas extremidades

Filas de duas extremidades tornam elegante a verificação de palíndromos — compare simultaneamente os caracteres das duas extremidades.

Deque<Character> deque = new ArrayDeque<>();
for (char c : "racecar".toCharArray()) deque.add(c);

boolean isPalindrome = true;
while (deque.size() > 1) {
    if (!deque.pollFirst().equals(deque.pollLast())) {
        isPalindrome = false;
        break;
    }
}
System.out.println(isPalindrome); // true

BFS com fila

A busca em largura usa uma fila. ArrayDeque é a escolha padrão para BFS em programação competitiva e no percurso de grafos.

import java.util.*;

// BFS on a simple adjacency list
Map<Integer,List<Integer>> graph = Map.of(
    1, List.of(2,3),
    2, List.of(4),
    3, List.of(4),
    4, List.of()
);
Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(1);
while (!queue.isEmpty()) {
    int node = queue.poll();
    if (visited.add(node)) {
        System.out.print(node + " ");
        queue.addAll(graph.get(node));
    }
}

DFS com pilha

A busca em profundidade usa uma pilha. Novamente, prefira ArrayDeque à classe legada Stack.

Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
stack.push(1);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (visited.add(node)) {
        System.out.print(node + " ");
        // push neighbors (will be processed in reverse order)
        List<Integer> neighbors = List.of(2, 3); // simplified
        for (int n : neighbors) if (!visited.contains(n)) stack.push(n);
    }
}

Fila de duas extremidades limitada com verificação de tamanho

ArrayDeque cresce dinamicamente, mas você pode impor manualmente uma capacidade para simular um buffer limitado:

Deque<Integer> buffer = new ArrayDeque<>();
int MAX = 3;

for (int i = 1; i <= 5; i++) {
    if (buffer.size() >= MAX) {
        buffer.pollFirst(); // drop oldest
    }
    buffer.offerLast(i);
}
System.out.println(buffer); // [3, 4, 5]

Observações sobre desempenho

ArrayDeque usa um vetor circular que dobra de tamanho quando fica cheio. O custo amortizado de todas as operações é O(1). Ela supera LinkedList na maioria dos testes de desempenho devido à eficiência do cache. Nunca faça a sincronização manualmente — use ConcurrentLinkedDeque ou uma fila bloqueante para concorrência.

Verificação rápida

Qual classe você deve preferir à Stack legada para operações LIFO?

Recapitulação: operações de fila de duas extremidades

Principais conclusões:

  • Uma fila de duas extremidades permite inserções e remoções O(1) nas duas extremidades
  • ArrayDeque é preferível a LinkedList para uso exclusivo como pilha ou fila
  • push/pop → pilha LIFO; offer/poll → fila FIFO
  • Usos clássicos: desfazer/refazer, BFS/DFS, janela deslizante e verificação de palíndromos
  • Evite as classes Stack e Queue legadas

Perguntas Frequentes

A aula “Operações de Deque: Pilha e Fila” é grátis?

Sim — o texto completo de “Operações de Deque: Pilha e Fila” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Java Academy, atualize para CoddyKit PRO. O curso de Java Academy inclui 4 aulas no total.

O que vou aprender em “Operações de Deque: Pilha e Fila”?

Use LinkedList como uma Deque para implementar o comportamento de pilha (push/pop) e fila (offer/poll). Você pratica Java Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Java Academy?

Nenhuma experiência prévia é necessária. Java Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.

Quanto tempo leva a aula “Operações de Deque: Pilha e Fila”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Java Academy?

Sim. Cada aula de Java Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Estrutura Interna de LinkedList
  2. Operações de Deque: Pilha e Fila
  3. LinkedList versus ArrayList: Compromissos
  4. PriorityQueue para Processamento Ordenado
← Voltar para Java Academy