Filas (Queue) e a Classe ArrayDeque em Java

As filas (queues) são estruturas de dados que seguem o princípio FIFO (first in – first out): o primeiro elemento inserido é o primeiro a ser removido. Esse modelo representa a fila tradicional, onde cada novo item é adicionado ao fim e removido do início.

Além disso, o Java também oferece filas duplamente terminadas (Deque), que permitem adicionar e remover elementos tanto no início quanto no fim.

Interface Queue

A interface Queue<E> estende Collection e define o comportamento de uma fila simples. Seus métodos principais são:

• boolean offer(E e): adiciona um elemento ao final da fila (retorna true se conseguiu, false caso contrário).
• E poll(): retorna e remove o primeiro elemento da fila, ou null se estiver vazia.
• E peek(): retorna o primeiro elemento da fila sem removê-lo, ou null se estiver vazia.
• E element(): retorna o primeiro elemento da fila sem removê-lo, mas lança NoSuchElementException se estiver vazia.
• E remove(): retorna e remove o primeiro elemento da fila, mas lança NoSuchElementException se estiver vazia.

Em resumo:

• offer e poll são versões seguras (não lançam exceções).
• add/remove e element podem lançar exceções quando a fila está vazia.

Interface Deque

A interface Deque<E> estende Queue<E> e representa uma fila de duas pontas. Com ela, podemos manipular elementos tanto na frente quanto no final da fila, além de usá-la como pilha (LIFO).

Principais métodos:

• Inserção:

  • addFirst(E e), offerFirst(E e) : adiciona no início
  • addLast(E e), offerLast(E e) : adiciona no fim

• Leitura sem remoção:

  • getFirst(), peekFirst() : primeiro elemento
  • getLast(), peekLast() : último elemento

• Remoção:

  • removeFirst(), pollFirst() : remove do início
  • removeLast(), pollLast() : remove do fim

• Uso como pilha:

  • push(E e) : insere no início
  • pop() : remove do início

• Remoção condicional:

  • removeFirstOccurrence(Object o) : remove a primeira ocorrência
  • removeLastOccurrence(Object o) : remove a última ocorrência

  A flexibilidade do Deque permite usá-lo tanto como fila tradicional quanto como pilha.

Classe ArrayDeque

O ArrayDeque<E> é uma das principais implementações de Deque em Java. Ele é baseado em arrays redimensionáveis e costuma ser mais rápido que LinkedList para uso como fila ou pilha.

Construtores

• ArrayDeque() : cria uma fila vazia (capacidade inicial = 16).
• ArrayDeque(int capacity) : cria com capacidade inicial definida.
• ArrayDeque(Collection<? extends E> c) : cria a fila com os elementos de uma coleção existente.

Exemplo de Uso

import java.util.ArrayDeque;

public class Program {
    public static void main(String[] args) {
        ArrayDeque<String> states = new ArrayDeque<>();

        // Adicionando elementos
        states.add("Germany");
        states.addFirst("France");
        states.push("Great Britain");
        states.addLast("Spain");
        states.add("Italy");

        // Acessando elementos sem remover
        System.out.println("Primeiro: " + states.getFirst()); // Great Britain
        System.out.println("Último: " + states.getLast());    // Italy

        System.out.println("Tamanho da fila: " + states.size()); // 5

        // Removendo elementos até a fila esvaziar
        while (states.peek() != null) {
            System.out.println("Removendo: " + states.pop());
        }

        // Usando objetos personalizados
        ArrayDeque<Person> people = new ArrayDeque<>();
        people.addFirst(new Person("Tom"));
        people.addLast(new Person("Nick"));

        for (Person p : people) {
            System.out.println("Pessoa: " + p.getName());
        }
    }
}

class Person {
    private String name;
    public Person(String name) {
        this.name = name;
    }
    public String getName() {
        return name;
    }
}

Saída esperada

Primeiro: Great Britain
Último: Italy
Tamanho da fila: 5
Removendo: Great Britain
Removendo: France
Removendo: Germany
Removendo: Spain
Removendo: Italy
Pessoa: Tom
Pessoa: Nick

Resumo

• Queue (Fila):

  • Interface que segue o princípio FIFO (First In, First Out).
  • Métodos principais: add(), offer(), poll(), peek().

• Deque (Double-Ended Queue):

  • Interface que permite inserir e remover elementos tanto no início quanto no fim.
  • Pode ser usada como fila (FIFO) ou como pilha (LIFO).
  • Métodos adicionais: addFirst(), addLast(), removeFirst(), removeLast().

• ArrayDeque:

  • Implementação eficiente de Deque.
  • Não permite valores null.
  • Mais rápido que Stack (para pilhas) e que LinkedList (para filas).

  • Métodos comuns:

    • Fila: offer(), poll(), peek()
    • Pilha: push(), pop(), peek()

📝 Exercícios

Tarefa 1. Inverter uma fila de números

Implemente um método reverseQueue que recebe um ArrayDeque<Integer> e inverte a ordem dos elementos. Exemplo: [1, 2, 3, 4] se torna [4, 3, 2, 1].

import java.util.ArrayDeque;

public class Program {
    public static void main(String[] args) {
        ArrayDeque<Integer> numbers = new ArrayDeque<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);
        numbers.add(4);

        reverseQueue(numbers);
        System.out.println(numbers); // esperado: [4, 3, 2, 1]
    }

    static void reverseQueue(ArrayDeque<Integer> queue) {
        // inverter os elementos da fila
    }
}

import java.util.ArrayDeque;

public class Program {
    public static void main(String[] args) {
        ArrayDeque<Integer> numbers = new ArrayDeque<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);
        numbers.add(4);

        reverseQueue(numbers);
        System.out.println(numbers); // [4, 3, 2, 1]
    }

    static void reverseQueue(ArrayDeque<Integer> queue) {
        ArrayDeque<Integer> temp = new ArrayDeque<>();
        while (!queue.isEmpty()) {
            temp.push(queue.pop()); // remove da frente e coloca como pilha
        }
        queue.addAll(temp); // volta invertido
    }
}

Tarefa 2. Verificar palíndromo com Deque

Use ArrayDeque<Character> para verificar se uma palavra é um palíndromo (igual de frente para trás). Exemplo: "radar" é verdadeiro, "java" é falso.

import java.util.ArrayDeque;

public class Program {
    public static void main(String[] args) {
        String word = "radar";
        boolean result = isPalindrome(word);
        System.out.println(result); // esperado: true
    }

    static boolean isPalindrome(String word) {
        ArrayDeque<Character> deque = new ArrayDeque<>();
        // adicionar caracteres na deque
        // comparar removendo da frente e de trás
    }
}

import java.util.ArrayDeque;

public class Program {
    public static void main(String[] args) {
        String word = "radar";
        boolean result = isPalindrome(word);
        System.out.println(result); // true
    }

    static boolean isPalindrome(String word) {
        ArrayDeque<Character> deque = new ArrayDeque<>();
        for (char c : word.toCharArray()) {
            deque.add(c);
        }

        while (deque.size() > 1) {
            if (!deque.pollFirst().equals(deque.pollLast())) {
                return false;
            }
        }
        return true;
    }
}

Tarefa 3. Sistema de desfazer/refazer (Undo/Redo)

Implemente um mini sistema de Undo/Redo usando ArrayDeque<String>.

• Quando o usuário executa uma ação, ela deve ser registrada no histórico.
• Se o usuário usar "desfazer" (undo), a ação mais recente é removida e enviada para a pilha de redo.
• Se o usuário usar "refazer" (redo), a ação volta para o histórico.

import java.util.ArrayDeque;

public class Program {
    public static void main(String[] args) {
        ArrayDeque<String> history = new ArrayDeque<>();
        ArrayDeque<String> redoStack = new ArrayDeque<>();

        doAction(history, "Escreveu código");
        doAction(history, "Compilou programa");
        doAction(history, "Executou testes");

        undo(history, redoStack); // desfaz última ação
        redo(history, redoStack); // refaz última ação
    }

    static void doAction(ArrayDeque<String> history, String action) {
        //  adicionar ação ao histórico
    }

    static void undo(ArrayDeque<String> history, ArrayDeque<String> redoStack) {
        // mover última ação para redoStack
    }

    static void redo(ArrayDeque<String> history, ArrayDeque<String> redoStack) {
        // mover do redoStack de volta ao histórico
    }
}

import java.util.ArrayDeque;

public class Program {
    public static void main(String[] args) {
        ArrayDeque<String> history = new ArrayDeque<>();
        ArrayDeque<String> redoStack = new ArrayDeque<>();

        doAction(history, "Escreveu código");
        doAction(history, "Compilou programa");
        doAction(history, "Executou testes");

        undo(history, redoStack);
        redo(history, redoStack);
    }

    static void doAction(ArrayDeque<String> history, String action) {
        history.push(action);
        System.out.println("Ação realizada: " + action);
    }

    static void undo(ArrayDeque<String> history, ArrayDeque<String> redoStack) {
        if (!history.isEmpty()) {
            String last = history.pop();
            redoStack.push(last);
            System.out.println("Desfeito: " + last);
        }
    }

    static void redo(ArrayDeque<String> history, ArrayDeque<String> redoStack) {
        if (!redoStack.isEmpty()) {
            String action = redoStack.pop();
            history.push(action);
            System.out.println("Refeito: " + action);
        }
    }
}