#1 [tuto][estrutura de dados]pilhas. Qui Out 13, 2011 3:42 pm
#Kamikaze ' ~
Novato
Tuto de pilhas
Difículdade:
Básico
Índice:
1.Conceito
2.Operações sobre pilhas
3.Implementação de pilhas
4. Sources
Conceito
Uma
pilha é tipo especial de lista linear em que todas as operações de
inserção e remoção são realizadas numa mesma extremidade,desominada
topo.
Devido a essa disciplina de acesso os elementos são sempre
removidos numa ordem inversa daquela que foram inseridos , de modo que
último elemento que entra é o primeiro que sai (LIFO - Last In First
Out)
Expandir esta imagemReduzir esta imagem Ver em tamanho real
Obs: Lista em java começaram na pos 0,na figura mostra começando em 1.
Em java o certo seria: pos[0]== B,pos[1]== C, etc. Quanto ao topo continuaria o mesmo,porem apontando pra próxima pos.
Operações sobre pilhas
Além
das operações de instanciar,verificar o estado da pilha ( se está cheia
ou vazia) e mostrar a pilha (toString) são definidas três operações
principais.
1. Empilha (push): Insere um elemento no topo da pilha
2. Desempilha (pop): Remove um elemento do topo da pilha e retorna o seu valor.
3. Topo (top): retorna o valor do elemento no topo da pilha.
Implementação de pilhas
Podemos implementar uma pilha de intereiros usando uma clase Java com os seguintes campos:
/**Topo da pilha */
private int top;
/**Elementos na pilha. */
private int ele[];
Sources
Pilha sequencial
Spoiler:public class Pilha<E extends Object> {
private int topo;
private E pil[];
public Pilha(int elem) {
this.pil = (E[]) new Object [elem];
//pil[elem];
topo = 0;
}
public Pilha()
{
this.pil = (E[]) new Object [10];
topo = 0;
}
public boolean estaVazia()
{
return topo == 0;
}
public boolean estaCheia()
{
return topo == pil.length;
}
public void empilha(E val)
{
if (estaCheia())
return;
pil[topo]= val;
topo++;
}
public E desempilha()
{
if (estaVazia())
return null;
E res = pil[--topo];
return res;
}
public E topo()
{
return pil[topo-1];
}
@Override
public String toString()
{
if(estaVazia()) return "[]";
String res = "[";
for(int i=0; i<topo-1; i++)
res += pil[i]+", ";
return res+pil[topo-1]+"]";
}
Pilha encadeada
Obs:
Não há vantagens em por nodo cabeã em uma pilha encadeada, está minha
pilha encadeada está com nodo cabeça porque no tuto lista encadeada eu
não botei com nodo cabeça,então resolvi por a pilha com nodo cabeça pra
mostrar para o cshp =]
Spoiler:public class PilhaEncad<E extends Object> {
private Nodo<E> pil;
public PilhaEncad() {
this.pil = new Nodo<E>((E) new Integer(0));
}
public boolean estaCheia()
{
return false;
}
public boolean estaVazia()
{
return pil.pro == null;
}
public void empilha(E val)
{
pil.pro = new Nodo<E>(val, pil.pro);
Integer n = (Integer) pil.val;
pil.val = (E) (++n);
}
public E desempilha()
{
if (estaVazia())
return null;
Integer nel = (Integer) pil.val;
E res = pil.pro.val;
pil.pro = pil.pro.pro;
pil.val = (E) (--nel);
return res;
}
public E topo()
{
return pil.pro.val;
}
@Override
public String toString()
{
if(estaVazia())
return "[]";
String res = "[";
Nodo p = pil.pro;
while(p.pro != null)
{
res += p.val + ", ";
p = p.pro;
}
return res + p.val + "]";
}
}
Nodo
Spoiler:public class Nodo<T> {
public T val;
public Nodo<T> pro;
public Nodo(T v)
{
val = v;
pro = null;
}
public Nodo(T v, Nodo p)
{
val = v;
pro = p;
}
}
Fim.
Desculpe ser tiver algum erro de português no tópico
E qualquer dúvida relacionada ao tópico estárei respondendo =]
Créditos: lipinf o/
To
ajudando as pessoas e não críticando esses tutorial que posto eu perdir
permissão ao dono do tópico original e ele deixo então eu tou postando
aqui para vocês
Antes de eu postar qualquer conteúdo eu falo com
o dono do post original para me dar permissão antes de postar para não
ouver problemas no fórum.
Difículdade:
Básico
Índice:
1.Conceito
2.Operações sobre pilhas
3.Implementação de pilhas
4. Sources
Conceito
Uma
pilha é tipo especial de lista linear em que todas as operações de
inserção e remoção são realizadas numa mesma extremidade,desominada
topo.
Devido a essa disciplina de acesso os elementos são sempre
removidos numa ordem inversa daquela que foram inseridos , de modo que
último elemento que entra é o primeiro que sai (LIFO - Last In First
Out)
Expandir esta imagemReduzir esta imagem Ver em tamanho real
Obs: Lista em java começaram na pos 0,na figura mostra começando em 1.
Em java o certo seria: pos[0]== B,pos[1]== C, etc. Quanto ao topo continuaria o mesmo,porem apontando pra próxima pos.
Operações sobre pilhas
Além
das operações de instanciar,verificar o estado da pilha ( se está cheia
ou vazia) e mostrar a pilha (toString) são definidas três operações
principais.
1. Empilha (push): Insere um elemento no topo da pilha
2. Desempilha (pop): Remove um elemento do topo da pilha e retorna o seu valor.
3. Topo (top): retorna o valor do elemento no topo da pilha.
Implementação de pilhas
Podemos implementar uma pilha de intereiros usando uma clase Java com os seguintes campos:
/**Topo da pilha */
private int top;
/**Elementos na pilha. */
private int ele[];
Sources
Pilha sequencial
Spoiler:public class Pilha<E extends Object> {
private int topo;
private E pil[];
public Pilha(int elem) {
this.pil = (E[]) new Object [elem];
//pil[elem];
topo = 0;
}
public Pilha()
{
this.pil = (E[]) new Object [10];
topo = 0;
}
public boolean estaVazia()
{
return topo == 0;
}
public boolean estaCheia()
{
return topo == pil.length;
}
public void empilha(E val)
{
if (estaCheia())
return;
pil[topo]= val;
topo++;
}
public E desempilha()
{
if (estaVazia())
return null;
E res = pil[--topo];
return res;
}
public E topo()
{
return pil[topo-1];
}
@Override
public String toString()
{
if(estaVazia()) return "[]";
String res = "[";
for(int i=0; i<topo-1; i++)
res += pil[i]+", ";
return res+pil[topo-1]+"]";
}
Pilha encadeada
Obs:
Não há vantagens em por nodo cabeã em uma pilha encadeada, está minha
pilha encadeada está com nodo cabeça porque no tuto lista encadeada eu
não botei com nodo cabeça,então resolvi por a pilha com nodo cabeça pra
mostrar para o cshp =]
Spoiler:public class PilhaEncad<E extends Object> {
private Nodo<E> pil;
public PilhaEncad() {
this.pil = new Nodo<E>((E) new Integer(0));
}
public boolean estaCheia()
{
return false;
}
public boolean estaVazia()
{
return pil.pro == null;
}
public void empilha(E val)
{
pil.pro = new Nodo<E>(val, pil.pro);
Integer n = (Integer) pil.val;
pil.val = (E) (++n);
}
public E desempilha()
{
if (estaVazia())
return null;
Integer nel = (Integer) pil.val;
E res = pil.pro.val;
pil.pro = pil.pro.pro;
pil.val = (E) (--nel);
return res;
}
public E topo()
{
return pil.pro.val;
}
@Override
public String toString()
{
if(estaVazia())
return "[]";
String res = "[";
Nodo p = pil.pro;
while(p.pro != null)
{
res += p.val + ", ";
p = p.pro;
}
return res + p.val + "]";
}
}
Nodo
Spoiler:public class Nodo<T> {
public T val;
public Nodo<T> pro;
public Nodo(T v)
{
val = v;
pro = null;
}
public Nodo(T v, Nodo p)
{
val = v;
pro = p;
}
}
Fim.
Desculpe ser tiver algum erro de português no tópico
E qualquer dúvida relacionada ao tópico estárei respondendo =]
Créditos: lipinf o/
To
ajudando as pessoas e não críticando esses tutorial que posto eu perdir
permissão ao dono do tópico original e ele deixo então eu tou postando
aqui para vocês
Antes de eu postar qualquer conteúdo eu falo com
o dono do post original para me dar permissão antes de postar para não
ouver problemas no fórum.