Como implementar uma pilha usando lista duplamente encadeada
Não há necessidade alguma de implementar uma pilha com encadeamento duplo, pois encadeamento simples é suficiente para alcançar tempos ótimos nas operações de empilhar (push), desempilhar (pop) e consultar o topo (peek), a não ser que a implementação for ser base para outras estruturas lineares.
O que você já fez? Isso é o mais importante. Poste e eu vou te auxiliando.
public class Lista {
private Elemento inicio = null, atual, aux;
public void inserir(Object objeto) {
if (inicio == null) {
inicio = new Elemento(objeto, null, null);
aux = inicio;
} else {
atual = new Elemento(objeto, null, aux);
aux.setProx(atual);
aux = atual;
}
}
}
Fiz a estrutura para lista, mas como relaciono com a pilha
Eu implemento a pilha e uso os métodos da lista ?
Fiz um exemplo completo para vc. A classe No (nó) que cria o encadeamento. Se você quer um encadeamento duplo, a classe No vai ter que ter uma referência para o próximo No além do anterior. Como eu já disse, isso é totalmente desnecessário.
O que eu falei sobre listas é que se você implementar uma lista apropriadamente, você consegue usá-la para simular o funcionamento de pilhas, filas e deques.
/**
* Implementação de uma pilha com encadeamento simples e exemplos de algoritmos
* que usam pilhas.
*
* @author Prof. Dr. David Buzatto
*/
public class Pilha<T> {
// um nó da pilha
private class No {
T valor; // o valor armazenado no nó
No anterior; // uma referência ao nó anterior no encadeamento
}
// topo da pilha, inicialmente null
private No topo;
// o tamanho da pilha, inicialmente 0
private int tamanho;
/**
* Constrói uma pilha vazia.
*/
public Pilha() {
topo = null; // não precisa, só pra deixar claro
tamanho = 0; // idem
}
/**
* Empilha um elemento to tipo T na pilha.
*
* @param valor O valor do elemento a ser empilhado.
*/
public void empilhar( T valor ) {
No novoNo = new No(); // cria um novo nó
novoNo.valor = valor; // configura o valor dele usando o
// argumento passado no parâmetro valor
novoNo.anterior = topo; // liga o novo nó no topo, indicando que o
// nó anterior ao novo nó é o topo
topo = novoNo; // move o topo para o novo nó
tamanho++; // incrementa o tamanho da pilha
}
/**
* Desempilha um elemento da pilha.
*
* @return O valor do elemento do topo da pilha, removendo-o.
* @throws RuntimeException Caso a pilha esteja vazia e se tente
* desempilhar.
*/
public T desempilhar() throws RuntimeException {
// se a pilha não está vazia
if ( !estaVazia() ) {
T valor = topo.valor; // salva o valor para retornar
No temp = topo; // marca o topo com uma referência
// temporária
topo = topo.anterior; // move o topo para o nó anterior à ele
temp.anterior = null; // desliga o nó que previamente era o topo,
// aquele que foi marcado com o temporário,
// do seu nó anterior
tamanho--; // um elemento vai sair, então decrementa
// o tamanho
return valor; // retorna o valor
// se a pilha está vazia, não é possível desempilhar, sendo assim
// lança uma exceção. isso é uma decisão de como vc quer que a pilha
// funcione. vc simplesmente poderia não fazer nada ou retornar
// um valor nulo (caso sua pilha não aceite valores nulos).
} else {
throw new RuntimeException( "pilha vazia!" );
}
}
/**
* Consulta o valor do elemento que está no topo da pilha.
*
* @return O valor do elemento do topo da pilha, sem removê-lo.
* @throws RuntimeException Caso a pilha esteja vazia e se tente
* consultar.
*/
public T consultarTopo() {
if ( !estaVazia() ) {
return topo.valor;
} else {
throw new RuntimeException( "pilha vazia!" );
}
}
/**
* Limpa a pilha, removendo todos os elementos.
*/
public void limpar() {
// enquanto a pilha não está vazia
while ( !estaVazia() ) {
// desempilha
desempilhar();
}
}
/**
* Verifica se a pilha está vazia.
*
* @return Verdadeiro caso a pilha esta vazia, falso caso contrário.
*/
public boolean estaVazia() {
return tamanho == 0; // também poderia ser topo == null
}
/**
* Retorna o tamanho (quantidade de elementos) da pilha.
*
* @return A quantidade de elementos contidos da pilha.
*/
public int getTamanho() {
return tamanho;
}
/*****************************************************************
* EXEMPLO DE USO! *
*****************************************************************/
/**
* Calcula o valor de uma expressão pós-fixa.
*
* Algoritmo:
* - Processe a expressão pós-fixa da esquerda para a direita;
* - Se o token for um operando, empilhe-o;
* - Se o token for um operador, desempilhe dois operandos da pilha
* e calcule o resultado dependendo do operador (token). Cuidado,
* o segundo operando é o primeiro a sair:
* r = op1 + op2;
* ou
* r = op1 - op2;
* ou
* r = op1 * op2;
* ou
* r = op1 / op2;
* e empilhe o resultado.
* - Repita até o fim da expressão pós-fixa.
* - O resultado da expressão aritmética pós-fixa estará no topo da
* pilha.
*
* @param postfix A expressão pós-fixa.
* @return O resultado do cálculo da expressão aritmética representada
* na forma pós-fixa.
* @throws IllegalArgumentException Caso a expressão seja inválida, ou seja,
* quando no processo de análise alguma operação desempilhar lançar uma
* RuntimeException.
*/
public static int calcularPosfixa( String posfixa )
throws IllegalArgumentException {
// cria uma nova pilha que armazena inteiros
Pilha<Integer> pilha = new Pilha<>();
Integer op1;
Integer op2;
Integer resultado;
try {
for ( String token : posfixa.split( "\\s+" ) ) {
switch ( token ) {
case "+":
op2 = pilha.desempilhar();
op1 = pilha.desempilhar();
resultado = op1 + op2;
pilha.empilhar( resultado );
break;
case "-":
op2 = pilha.desempilhar();
op1 = pilha.desempilhar();
resultado = op1 - op2;
pilha.empilhar( resultado );
break;
case "*":
op2 = pilha.desempilhar();
op1 = pilha.desempilhar();
resultado = op1 * op2;
pilha.empilhar( resultado );
break;
case "/":
op2 = pilha.desempilhar();
op1 = pilha.desempilhar();
resultado = op1 / op2;
pilha.empilhar( resultado );
break;
default:
pilha.empilhar( Integer.valueOf( token ) );
break;
}
}
return pilha.desempilhar();
} catch ( RuntimeException exc ) {
throw new IllegalArgumentException( "expressão inválida!" );
}
}
/**
* Converte uma expressão aritmética pós-fixa para infixa.
*
* Algoritmo:
* - Processe a expressão pós-fixa da esquerda para a direita;
* - Se o token for um operando, empilhe-o;
* - Se o token for um operador, desempilhe dois operandos da pilha
* e crie uma string concatenando-os na forma:
* infix = "( " + operando2 + operador + operando1 + " )"
* e empilhe essa string.
* - Repita até o fim da expressão pós-fixa.
* - A expressão infixa estará no topo da pilha ao fim do processo.
*
* @param posfixa A expressão pós-fixa.
* @return A expressão infixa correspondente.
* @throws IllegalArgumentException Caso a expressão seja inválida, ou seja,
* quando no processo de análise alguma operação desempilhar lançar uma
* RuntimeException.
*/
public static String posfixaParaInfixa( String posfixa )
throws IllegalArgumentException {
Pilha<String> pilha = new Pilha<>();
try {
for ( String token : posfixa.split( "\\s+" ) ) {
switch ( token ) {
case "+":
case "-":
case "*":
case "/":
String op1 = pilha.desempilhar();
String op2 = pilha.desempilhar();
String infix = String.format( "( %s %s %s )", op2, token, op1 );
pilha.empilhar( infix );
break;
default:
pilha.empilhar( token );
break;
}
}
return pilha.desempilhar().trim();
} catch ( RuntimeException exc ) {
throw new IllegalArgumentException( "expressão inválida!" );
}
}
public static void main( String[] args ) {
String[] expressoesPosfixadas = {
"9 10 +", // o mesmo que 9 + 10
"5 9 -", // o mesmo que 5 - 9
"9 5 -", // o mesmo que 9 - 5
"4 6 *", // o mesmo que 4 * 6
"15 3 /", // o mesmo que 15 / 3
"97 52 + 84 -", // o mesmo que 9 + 54 - 84
"97 52 84 + -", // o mesmo que 97 - ( 52 + 84 )
"97 52 + 84 - 7 *" // o mesmo que ( 97 + 52 - 84 ) * 7
};
System.out.println( "pós-fixa = infixa = valor" );
for ( String expressao : expressoesPosfixadas ) {
System.out.printf("%s = %s = %d\n",
expressao,
posfixaParaInfixa( expressao ),
calcularPosfixa( expressao ) );
}
}
}
1 curtida