Neste artigo, exploramos a implementação de três estruturas de dados fundamentais em Java: fila, pilha e lista duplamente encadeada. Cada estrutuar é explicada com um exemplo de código que demonstra como emular ou construir suas funcionalidades usando primitivas da linguagem.
1. Fila
Uma fila é uma estrutura de dados que segue o princípio de primeiro a entrar, primeiro a sair (FIFO), semelhante ao fluxo em um tubo. Em Java, não existem ponteiros diretos como em C, então usamos duas pilhas para simular esse comportamento. Uma pilha recebe as inserções, e quando uma remoção é necessária, os elementos são transferidos para a outra pilha, invertendo sua ordem. Isso permite que a pilha, que opera em modo último a entrar, primeiro a sair (LIFO), imite o FIFO da fila.
import java.util.Stack;
public class Fila<T> {
private Stack<T> pilhaEntrada;
private Stack<T> pilhaSaida;
private int tamanho;
public Fila() {
pilhaEntrada = new Stack<>();
pilhaSaida = new Stack<>();
tamanho = 0;
}
// Adiciona um elemento à fila
public void adicionar(T elemento) {
// Move todos os elementos da pilha de saída para a pilha de entrada
while (!pilhaSaida.isEmpty()) {
pilhaEntrada.push(pilhaSaida.pop());
}
pilhaEntrada.push(elemento);
tamanho++;
}
// Remove e retorna o elemento da frente da fila
public T remover() {
// Move todos os elementos da pilha de entrada para a pilha de saída
while (!pilhaEntrada.isEmpty()) {
pilhaSaida.push(pilhaEntrada.pop());
}
tamanho--;
return pilhaSaida.pop();
}
public int obterTamanho() {
return tamanho;
}
public boolean estaVazia() {
return tamanho == 0;
}
public static void main(String[] args) {
Fila<String> filaTeste = new Fila<>();
filaTeste.adicionar("Primeiro");
filaTeste.adicionar("Segundo");
filaTeste.adicionar("Terceiro");
while (!filaTeste.estaVazia()) {
System.out.print(filaTeste.remover() + " ");
}
System.out.println("\nTamanho da fila: " + filaTeste.obterTamanho());
}
}
2. Pilha
Uma pilha segue o princípio de último a entrar, primeiro a sair (LIFO), como um carregador de munição. Aqui, implementamos uma pilha usando um array em Java, permitindo armazenar elementos de qualquer tipo. O topo da pilha é rastreado por um índice numérico, já que Java não oferece ponteiros de pilha como em C.
import java.lang.reflect.Array;
public class Pilha<T> {
private static final int TAMANHO_PADRAO = 12;
private T[] elementos;
private int topo; // Índice do elemento no topo (-1 se vazia)
public Pilha(Class<T> tipoClasse) {
this(tipoClasse, TAMANHO_PADRAO);
}
public Pilha(Class<T> tipoClasse, int capacidade) {
elementos = (T[]) Array.newInstance(tipoClasse, capacidade);
topo = -1; // Inicia vazio
}
// Empilha um elemento
public void empilhar(T valor) {
if (topo < elementos.length - 1) {
elementos[++topo] = valor;
} else {
throw new IllegalStateException("Pilha cheia");
}
}
// Retorna o elemento do topo sem removê-lo
public T espiar() {
if (topo == -1) {
throw new IllegalStateException("Pilha vazia");
}
return elementos[topo];
}
// Remove e retorna o elemento do topo
public T desempilhar() {
if (topo == -1) {
throw new IllegalStateException("Pilha vazia");
}
return elementos[topo--];
}
public int capacidade() {
return elementos.length;
}
public boolean estaVazia() {
return topo == -1;
}
public void imprimir() {
if (estaVazia()) {
System.out.println("Pilha está vazia.");
} else {
System.out.println("Capacidade da pilha: " + capacidade());
for (int i = topo; i >= 0; i--) {
System.out.println(elementos[i]);
}
}
}
public static void main(String[] args) {
Pilha<String> pilhaTeste = new Pilha<>(String.class);
pilhaTeste.empilhar("A");
pilhaTeste.empilhar("B");
pilhaTeste.empilhar("C");
System.out.println("Topo: " + pilhaTeste.espiar());
System.out.println("Desempilhado: " + pilhaTeste.desempilhar());
System.out.println("Capacidade restante: " + pilhaTeste.capacidade());
System.out.println("Está vazia? " + pilhaTeste.estaVazia());
pilhaTeste.imprimir();
}
}
3. Lista Duplamente Encadeada
Uma lista duplamente encadeada permite navegação em ambas as direções, com cada nó apontando para o anterior e o próximo. Em Java, usamos referências em vez de ponteiros explícitos para gerenciar os nós. Esta implementação inclui operações como inserção, remoção e acesso por índice.
public class ListaDupla<T> {
private No<T> cabeca;
private int tamanho;
private class No<T> {
private No<T> anterior;
private No<T> proximo;
private T dado;
public No(T dado, No<T> anterior, No<T> proximo) {
this.dado = dado;
this.anterior = anterior;
this.proximo = proximo;
}
}
public ListaDupla() {
// Inicializa com um nó sentinela circular
cabeca = new No<>(null, null, null);
cabeca.anterior = cabeca;
cabeca.proximo = cabeca;
tamanho = 0;
}
public int obterTamanho() {
return tamanho;
}
public boolean estaVazia() {
return tamanho == 0;
}
private No<T> encontrarNo(int indice) {
if (indice < 0 || indice >= tamanho) {
throw new IndexOutOfBoundsException("Índice inválido");
}
// Otimiza a busca dependendo da posição
if (indice < tamanho / 2) {
No<T> atual = cabeca.proximo;
for (int i = 0; i < indice; i++) {
atual = atual.proximo;
}
return atual;
} else {
No<T> atual = cabeca.anterior;
int posicao = tamanho - indice - 1;
for (int i = 0; i < posicao; i++) {
atual = atual.anterior;
}
return atual;
}
}
public T obter(int indice) {
return encontrarNo(indice).dado;
}
public T obterPrimeiro() {
return obter(0);
}
public T obterUltimo() {
return obter(tamanho - 1);
}
// Insere um nó antes do índice especificado
public void inserir(int indice, T valor) {
if (indice == 0) {
No<T> novoNo = new No<>(valor, cabeca, cabeca.proximo);
cabeca.proximo.anterior = novoNo;
cabeca.proximo = novoNo;
} else {
No<T> noAtual = encontrarNo(indice);
No<T> novoNo = new No<>(valor, noAtual.anterior, noAtual);
noAtual.anterior.proximo = novoNo;
noAtual.anterior = novoNo;
}
tamanho++;
}
public void inserirNoInicio(T valor) {
inserir(0, valor);
}
public void adicionarNoFinal(T valor) {
No<T> novoNo = new No<>(valor, cabeca.anterior, cabeca);
cabeca.anterior.proximo = novoNo;
cabeca.anterior = novoNo;
tamanho++;
}
// Remove o nó no índice especificado
public void remover(int indice) {
No<T> noParaRemover = encontrarNo(indice);
noParaRemover.anterior.proximo = noParaRemover.proximo;
noParaRemover.proximo.anterior = noParaRemover.anterior;
noParaRemover.dado = null; // Ajuda no garbage collection
tamanho--;
}
public void removerPrimeiro() {
remover(0);
}
public void removerUltimo() {
remover(tamanho - 1);
}
}
Diferenças entre Implementações em C e Java
Na implementação de estruturas de dados, C e Java divergem devido às suas características linguísticas. Em C, ponteiros permitem acesso direto a memória e manipulação de endereços, como em pilhas com ponteiros de topo ou filas com ponteiros de frente e traseira. Java, por outro lado, usa referências e gerenciamento automático de memória, o que elimina a necessidade de ponteiros explícitos. Por exemplo, uma fila em Java pode ser simulada com duas pilhas (como mostrado) para emular o FIFO, enquanto em C seria comum usar ponteiros para manter a ordem. Da mesma forma, listas duplamente encadeadas em Java substituem ponteiros por referências de objetos, simplificando a implementação, mas exigindo atenção à manipulação de referências nulas e coleta de lixo.