Pilhas: Fundamentos e
implementao da estrutura
em Java
Veja neste artigo os fundamentos da estrutura de
dados pilha (LIFO), bem como a implementao
de uma pilha simples em Java.
5
Gostei (7)
(0)
Uma questo importante no estudo da computao o entendimento
das estruturas de dados, dentre as quais temos filas, pilhas, listas
ligadas, entre outras. Vamos entender aqui o funcionamento das
pilhas e como implementar uma pilha simples em Java.
O que uma estrutura de dados?
A estrutura de dados o corao de diversos programas bem
elaborados, saber qual tipo de estrutura utilizar essencial para
construir um aplicativo de qualidade. A estrutura de dados na
verdade a forma de organizar e armazenar informaes para que
estas possam posteriormente ser utilizadas de modo eficiente.
O que uma pilha?
A pilha uma das estruturas de dados e trabalha com o formato LIFO
(o ltimo a entrar o primeiro a sair, Last In, First Out, em ingls).
Lembre-se da pilha como uma pilha de livros, em que o primeiro livro
que foi inserido na pilha, normalmente o ltimo que sai dela,
enquanto o ltimo adicionado o primeiro a ser retirado.
A estrutura da pilha, segundo Farias so estruturas de dados do tipo
LIFO (last-in first-out), onde o ltimo elemento a ser inserido, ser o
primeiro a ser retirado. Assim, uma pilha permite acesso a apenas um
item de dados - o ltimo inserido. Para processar o penltimo item
inserido, deve-se remover o ltimo.
A pilha considerada uma estrutura de dados simples, sendo fcil de
implementar. Em uma anlise simples, poderia ser utilizada, por
exemplo, em um carregamento de um caminho, pois se o caminho
tiver 4 entregas, a ltima entrega colocada dentro do caminho deve
ser a primeira a sair, caso contrrio, pode dar mais trabalho para
descarregar.
Um outro caso de pilha simples de se entender o caso do entregador
de pizza.
O entregador deve entregar trs pizzas em locais diferentes, se ele
colocar na ordem de entrega, o que vai ocorrer que a primeira pizza
colocada no ba a primeira pizza a ser entregue, de forma que todas
as outras pizzas esto sobre a primeira pizza, ento qual a melhor
lgica?
Mudar a ordem: a primeira pizza no ba deve ser a ltima a ser
entregue e a ltima pizza do ba, a primeira a ser entregue. Neste
caso, ao chegar na casa do cliente, o entregador apenas pega a
primeira pizza que est no ba e entrega ao cliente.
Este exemplo foi proposto inicialmente por Takai, apresentando uma
rota de entrega de quatro pizzas, sendo a seguinte ordem:
1 entrega: Portuguesa
2 entrega: Frango com catupiry
3 entrega: Calabresa
4 entrega: Quatro queijos
Assim, para armazenar no ba, a ordem deve ser invertida, ficando da
seguinte forma:
Portuguesa (topo do ba)
Frango com catupiry
Calabresa
Quatro queijos
Para as tarefas temos: a criao da pilha, o empilhamento - push (ato
de colocar uma caixa de pizza sobre a outra), o ato de desempilhar pop (na hora que o entregador tira a caixa de pilha para entregar ao
cliente), alm de uma verificao se a pilha est cheia ou vazia (ato
que o entregador faz ao verificar o ba).
Implementando nossa pilha em
Java
Primeiramente, vamos criar um array para armazenar nossa pilha.
Imaginando o ba, temos uma capacidade de 10 pizzas, por exemplo,
j um caminho, dependendo do tamanho dele e da quantidade de
produtos a serem entregues, pode armazenar de 1 a centenas de
entregas, e assim por diante. Em nosso caso, primeiro vamos criar o
array, depois vamos definir um tamanho de teste para 10 itens em
nossa pilha.
Listagem 1: Declarando o array
public Object[] pilha;
Foi utilizado o tipo Object para armazenar textos ou nmeros, uma
forma mais genrica, apenas como teste de pilha.
Listagem 2: Varivel para armazenar a posio atual na pilha
public int posicaoPilha;
Aqui foi criado uma varivel que exibe a posio atual na pilha, se a
posio for 10, ento chegamos ao topo da pilha e no podero ser
inseridos mais itens.
Agora no construtor ser definido o tamanho da pilha e inicializado a
posio.
Listagem 3: Inicializando a pilha
public Pilha() {
this. posicaoPilha = -1;
// indica que esta nula, vazia, pois a posio zero
//do array j armazena informao
[Link] = new Object[10]; // criando uma pilha com 10
posies
}
Agora vamos criar uma funo que verifique se a pilha est vazia
(isEmpty).
Listagem 4: Funo para verificar se a pilha est vazia
public boolean pilhaVazia() {
if (this. posicaoPilha == -1) {
return true;
// Verifica que o o atributo posicaoPilha igual a -1,
//se for, a pilha nula, ou seja, ainda esta vazia,
//retornando verdadeiro.
}
return false;
}
Agora necessrio verificarmos qual o tamanho da pilha atual, ou
seja, o entregador olha quantas pizzas ainda tem dentro do ba para
entregar.
Listagem 5: Funo que retorna a quantidade de itens na pilha
public int tamanho() {
if ([Link]()) {
return 0; // aqui indica que no tem nenhum contedo
dentro da pilha
}
return this. posicaoPilha + 1;
// aqui indica quantos itens tem dentro da pilha, somando-se 1,
//pois a pilha inicia no zero. Logo, se tivermos 3 itens na
pilha,
// o atributo posicaoPilha vai exibir 2.
//Para sabermos quantos itens h, precisamos somar um.
}
Agora necessrio um mtodo para empilhar itens dentro da pilha, ou
seja, a forma que o entregador pega a pizza e insere sobre a ltima
pizza que est no ba.
Listagem 6: Funo para empilhar itens
public void empilhar(Object valor) {
// push
if (this. posicaoPilha < [Link] - 1) {
// verifica se a posicaoPilha menor do que o tamanho da
pilha,
//se for, ento inserido o valor na pilha e ao mesmo tempo
feito
//o incremento do atributo posicaoPilha
[Link][++posicaoPilha] = valor;
}
}
Depois de criada uma forma de empilhar, temos de desempilhar, ou
seja, hora do entregador retirar a pizza do ba e entregar ao cliente.
Listagem 7: Funo para remover itens da lista
public Object desempilhar() {
//pop
if (pilhaVazia()) {
return null;
// primeiro verificamos se a pilha esta vazia,
//se estiver, nada ser realizado
}
return [Link][this. posicaoPilha --];
// aqui retorna o que tem na ltima posio da pilha
//e decrementa o atributo posicaoPilha
}
Agora vamos ver o resultado da pilha completa em funcionamento:
Listagem 8: Pilha completa em funcionamento
public class Pilha {
public Object[] pilha;
public int posicaoPilha;
public Pilha() {
[Link] = -1;
// indica que esta nula, vazia, pois posio um indica que contm
informao
[Link] = new Object[1000];
// criando uma pilha com 1000 posies
}
public boolean pilhaVazia() {
//isEmpty
if ([Link] == -1) {
return true;
}
return false;
}
public int tamanho() {
//is
if ([Link]()) {
return 0;
}
return [Link] + 1;
}
public Object exibeUltimoValor() {
//top
if ([Link]()) {
return null;
}
return [Link][[Link]];
}
public Object desempilhar() {
//pop
if (pilhaVazia()) {
return null;
}
return [Link][[Link]--];
}
public void empilhar(Object valor) {
// push
if ([Link] < [Link] - 1) {
[Link][++posicaoPilha] = valor;
}
}
public static void main(String args[]) {
Pilha p = new Pilha();
[Link]("Portuguesa ");
[Link]("Frango com catupiry ");
[Link]("Calabresa ");
[Link]("Quatro queijos ");
[Link](10);
while ([Link]() == false) {
[Link]([Link]());
}
}
}
Pronto, a pilha est funcionando. Nosso entregador pode empilhar e
desempilhar as pilhas sem maiores problemas.
Concluso
A pilha uma estrutura simples de ser implementada. Apesar de
algumas limitaes, pode ser utilizado para diversos fins, como
sistemas de logsticas, por exemplo.
Leia mais em: Pilhas: Fundamentos e implementao da estrutura em
Java [Link]
[Link]
