Pilha (Stack)

Conceito de Pilha

A pilha é uma lista linear especial que permite operações de inserção e remoção apenas em uma extremidade, denominada topo. A outra extremdiade é chamada de base. Os dados seguem o princípio LIFO (Last In First Out), ou seja, o último elemento inserido é o primeiro a ser removido.

Empilhamento: refere-se à operação de inserção, onde novos elementos são adicionados no topo da pilha.

Desempilhamento: corresponde à operação de remoção, onde o elemento no topo é retirado.

Métodos Comuns

// Empilhar um valor
public void empilhar(int valor)
    
// Desempilhar e retornar o elemento do topo
public int desempilhar()
    
// Consultar o elemento do topo sem removê-lo
public int espiar()
    
// Verificar se a pilha está vazia
public boolean estaVazio()

Implementação da Pilha

Criação de uma pilha vazia:

public class Pilha {
    private int[] dados;
    private int contador;
    private static final int CAPACIDADE_INICIAL = 10;

    public Pilha() {
        this.dados = new int[CAPACIDADE_INICIAL];
    }
}

Implementação do método empilhar:

public void empilhar(int valor) {
    if (this.dados.length == contador) {
        this.dados = Arrays.copyOf(this.dados, this.dados.length * 2);
    }
    this.dados[contador] = valor;
    contador++;
}

Implementação do método desempilhar:

Em caso de pilha vazia, uma exceção personalizada é lançada.

public class PilhaVaziaException extends RuntimeException {
    public PilhaVaziaException() {
    }

    public PilhaVaziaException(String mensagem) {
        super(mensagem);
    }
}

public int desempilhar() {
    if (contador == 0) {
        throw new PilhaVaziaException();
    }
    int valorRemovido = this.dados[contador - 1];
    contador--;
    return valorRemovido;
}

Implementação do método espiar:

public int espiar() {
    if (contador == 0) {
        throw new PilhaVaziaException();
    }
    return this.dados[contador - 1];
}

Implemnetação do método estaVazio:

public boolean estaVazio() {
    return contador == 0;
}

Fila (Queue)

Conceito de Fila

A fila é uma lista linear especial que permite inserção em uma extremidade (cauda) e remoção na outra extremidade (cabeça), seguindo o princípio FIFO (First In First Out). Em Java, a interface Queue é frequentemente implementada usando listas ligadas.

Enfileiramento: a operação de inserção ocorre na cauda da fila.

Desenfileiramento: a operação de remoção ocorre na cabeça da fila.

Métodos Comuns

// Enfileirar um elemento
public void enfileirar(int x)
    
// Desenfileirar e retornar o elemento da cabeça
public int desenfileirar()

// Obter o elemento da cabeça sem removê-lo
public int espiar()

// Retornar o número de elementos na fila
public int tamanho()
    
// Verificar se a fila está vazia
public boolean estaVazio()

Implementação da Fila com Lista Duplamente Ligada

public class Fila {
    static class No {
        public int valor;
        public No proximo;
        public No anterior;

        public No(int valor) {
            this.valor = valor;
        }
    }

    public No cabeca;
    public No cauda;
    public int quantidade = 0;
    
}

Implementação do método enfileirar:

public void enfileirar(int x) {
    No novoNo = new No(x);
    if (cabeca == null) {
        cabeca = cauda = novoNo;
    } else {
        novoNo.proximo = cabeca;
        cabeca.anterior = novoNo;
        cabeca = novoNo;
    }
    quantidade++;
}

Implementação do método desenfileirar:

public int desenfileirar() {
    if (cabeca == null) {
        return -1;
    }
    int valorRetorno = cauda.valor;
    if (cabeca == cauda) {
        cabeca = null;
        cauda = null;
        quantidade--;
        return valorRetorno;
    }
    cauda = cauda.anterior;
    cauda.proximo = null;
    quantidade--;
}

Implementação do método espiar:

public int espiar() {
    if (cabeca == null) {
        return -1;
    }
    return cabeca.valor;
}

Implementação do método tamanho:

public int tamanho() {
    return quantidade;
}

Implementação do método estaVazio:

public boolean estaVazio() {
    return cabeca == null;
}

Implementação de Fila Circular

public class FilaCircular {
    public int[] elementos;
    public int cabeca;
    public int cauda;

    public FilaCircular(int capacidade) {
        this.elementos = new int[capacidade + 1];
    }

    public boolean enfileirar(int valor) {
        if (estaCheia()) {
            return false;
        }
        elementos[cauda] = valor;
        cauda = (cauda + 1) % elementos.length;
        return true;
    }

    private boolean estaCheia() {
        return (cauda + 1) % elementos.length == cabeca;
    }

    public boolean desenfileirar() {
        if (estaVazia()) {
            return false;
        }
        cabeca = (cabeca + 1) % elementos.length;
        return true;
    }

    public int obterCabeca() {
        if (estaVazia()) {
            return -1;
        }
        return elementos[cabeca];
    }

    public boolean estaVazia() {
        return cabeca == cauda;
    }
}