Explorando Estruturas de Dados em Java: Pilhas e Filas

Antes de mais nada, gostaria de dizer que há uma certa controvérsia por parte da comunidade envolvendo a linguagem Java. Alguns programadores acreditam que o Java oferece recursos poderosos e uma vasta biblioteca de estruturas de dados prontas para uso. Outros, porém, argumentam que a implementação dessas estruturas em Java pode ser limitada e menos eficiente em comparação com outras linguagens.

Neste post, vamos mergulhar nessa controvérsia e explorar as estruturas de dados em Java. Vamos analisar as principais estruturas, como pilhas e filas.
Nos seguintes exemplos estarei usando o conceito de vetores usando a classe Integer. Recomendo dar uma olhada antesa

Você não precisa ter medo de Java, é uma linguagem maravilhosa. Organize suas ideias, e no final, tudo vai dar certo.

Pilha

Vou usar o exemplo mais usado por todos: Imagine que você tem uma pilha de pratos em uma cozinha. Você coloca os pratos uns em cima dos outros, formando uma pilha vertical. Agora, se você quiser pegar um prato para usar, você deve pegar o que está no topo da pilha, certo? Você não pode pegar um prato que está no meio ou na base da pilha sem remover todos os pratos que estão acima dele primeiro.

Uma pilha de dados na programação é semelhante a essa pilha de pratos. É uma estrutura de dados em que você pode adicionar elementos ou remover elementos somente no topo da pilha. O elemento que foi adicionado mais recentemente é o primeiro a ser removido. Por causa dessa característica, chamamos essa estrutura de dados de "pilha" ou "stack" em inglês.

Podemos usar uma pilha em situações em que precisamos lembrar a ordem em que os elementos foram adicionados. Por exemplo, se você está escrevendo um editor de texto e deseja fornecer uma função "Desfazer", você pode usar uma pilha para armazenar as ações do usuário à medida que ele as realiza. Quando o usuário seleciona "Desfazer", a pilha permite que você desfaça as ações na ordem inversa em que foram feitas.

Em uma pilha, podemos adicionar um novo elemento no topo usando uma operação chamada "push" e remover o elemento do topo usando uma operação chamada "pop". Além disso, podemos verificar se a pilha está vazia e até mesmo ver o elemento no topo da pilha sem removê-lo.

Aqui está um breve código da implementação de uma Pilha. Explico mais depois do código.

public class Pilha {
    private Integer[] elementos;
    private int topo;

    public Pilha(int capacidade) {
        elementos = new Integer[capacidade];
        topo = -1; // Pilha vazia
    }

    public void push(int elemento) {
        if (isFull()) {
            throw new IllegalStateException("A pilha está cheia");
        }

        topo++;
        elementos[topo] = elemento;
    }

    public Integer pop() {
        if (isEmpty()) {
            throw new IllegalStateException("A pilha está vazia");
        }

        Integer elementoRemovido = elementos[topo];
        elementos[topo] = null; // Libera a referência do elemento removido
        topo--;

        return elementoRemovido;
    }

    public Integer peek() {
        if (isEmpty()) {
            throw new IllegalStateException("A pilha está vazia");
        }

        return elementos[topo];
    }

    public boolean isEmpty() {
        return topo == -1;
    }

    public boolean isFull() {
        return topo == elementos.length - 1;
    }
}

Nessa implementação, a classe Pilha possui um vetor chamado elementos que armazena os elementos da pilha e uma variável topo que indica a posição do elemento no topo da pilha.

A classe Pilha também possui os métodos principais:

• O método push adiciona um elemento no topo da pilha. Ele verifica se a pilha está cheia utilizando o método isFull(), incrementa a variável topo e armazena o elemento no vetor elementos.
• O método pop remove e retorna o elemento do topo da pilha. Ele verifica se a pilha está vazia utilizando o método isEmpty(), armazena o elemento a ser removido na variável elementoRemovido, libera a referência do elemento no vetor, decrementa a variável topo e retorna o elemento removido.
• O método peek retorna o elemento do topo da pilha sem removê-lo. Ele verifica se a pilha está vazia utilizando o método isEmpty() e retorna o elemento no topo.
• O método isEmpty verifica se a pilha está vazia, verificando se o topo é igual a -1¹.
• O método isFull verifica se a pilha está cheia, verificando se o topo é igual ao tamanho máximo do vetor elementos menos 1².

¹. -1 é o valor de quando não tem nada em uma lista/vetor, então se não tem nada no vetor, ele está vazio.
². Imagine que você tem 5 pratos um em cima do outro, então você um vetor de 5 posições:
[0, 1, 2, 3, 4]
Todos os valores estão preenchidos, então o topo é 4 (o seu prato no topo é o último, logo: posição 4), se você quiser saber se a sua pilha está cheia, você calcula:

> topo == tamnhoMáximoVetor - 1
Seguindo a lógica, o topo é 4 (ultimo elemento) e o tamanho máximo do vetor é 5, logo:
> 4 == 5 - 1
> True

Aqui tem um breve diagrama que eu peguei da UFRJ

Que fala sobre pilhas.

Filas

Imagine uma fila de pessoas esperando para entrar em um cinema. Cada pessoa que chega se posiciona no final da fila, e a pessoa que está na frente é a próxima a entrar no cinema. Essa é a ideia básica de uma fila. Em desenvolvimento de software, uma fila é uma estrutura de dados semelhante. Ela segue o mesmo princípio da fila do cinema, onde os elementos são organizados em uma ordem específica. O elemento que chega primeiro é o primeiro a ser atendido ou processado.

Segue um breve código que implementa uma fila:

public class Fila {
    private Integer[] elementos;
    private int capacidade;
    private int inicio;
    private int fim;
    private int tamanho;

    public Fila(int capacidade) {
        this.capacidade = capacidade;
        elementos = new Integer[capacidade];
        inicio = 0;
        fim = -1;
        tamanho = 0;
    }

    public void enqueue(Integer elemento) {
        if (isFull()) {
            throw new IllegalStateException("A fila está cheia");
        }

        fim = (fim + 1) % capacidade;
        elementos[fim] = elemento;
        tamanho++;
    }

    public Integer dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("A fila está vazia");
        }

        int elementoRemovido = elementos[inicio];
        elementos[inicio] = 0; // Valor padrão para inteiros
        inicio = (inicio + 1) % capacidade;
        tamanho--;

        return elementoRemovido;
    }

    public Integer front() {
        if (isEmpty()) {
            throw new IllegalStateException("A fila está vazia");
        }

        return elementos[inicio];
    }

    public boolean isEmpty() {
        return tamanho == 0;
    }

    public boolean isFull() {
        return tamanho == capacidade;
    }
}

Nessa implementação, estamos utilizando o conceito de FIFO(Firt-In, First-Out), que em português signific: "o primeiro a entrar é o primeiro a sair". Esse conceito é usado em diversas situações do dia a dia, como quando estamos em uma fila de espera em um supermercado, banco ou parque de diversões.

A classe Fila possui um vetor chamado elementos para armazenar os elementos da fila, uma variável tamanho para controlar o número de elementos na fila, uma variável inicio para indicar o índice do primeiro elemento na fila, e uma variável fim para indicar o índice do último elemento na fila.

A classe Fila também possui os métodos principais:

• O método enqueue adiciona um elemento no final da fila. Ele verifica se a fila está cheia utilizando o método isFull(), atualiza o valor de fim para apontar para o próximo índice disponível no vetor (levando em consideração a operação módulo), armazena o elemento no vetor elementos e incrementa o tamanho da fila.
• O método dequeue remove e retorna o elemento no início da fila. Ele verifica se a fila está vazia utilizando o método isEmpty(), armazena o elemento a ser removido na variável elementoRemovido, libera a referência do elemento no vetor, atualiza o valor de inicio para apontar para o próximo elemento na fila (levando em consideração a operação módulo) e decrementa o tamanho da fila.
• O método front retorna o elemento no início da fila sem removê-lo. Ele verifica se a fila está vazia utilizando o método isEmpty() e retorna o elemento no índice inicio.
• O método isEmpty verifica se a fila está vazia, verificando se o tamanho é igual a 0.
• O método isFull verifica se a fila está cheia, verificando se o tamanho é igual ao tamanho máximo do vetor elementos.

Segue um breve diagrama que eu peguei do Arquivo de Códigos, para exemplificar: