Estrutura de dados Pilhas
854 palavras
4 páginas
12/3/2012Pilhas
Estrutura de Dados
São listas onde a inserção de um novo item ou a remoção de um item já existente se dá em uma única extremidade, no topo.
Os itens são colocados um sobre o outro.
O item inserido mais recentemente está no topo e o inserido menos recentemente no fundo.
Pilhas
Propriedade: o último item inserido é o primeiro item que pode ser retirado da lista.
São chamadas listas lifo (“last-in, first-out”).
Exemplo de Pilha
Operações sobre uma Pilha empilha 3
...
topo
3
desempilha
3
...
25
25
12
3
12
retornaTopo
LIFO: “last-in; first-out”
Pilha como Array
TAD Pilhas: Operações
Criar uma pilha P vazia;
Testar se P está vazia;
Obter o elemento do topo da pilha (sem eliminar);
Seja pilha uma estrutura linear representada através de um array P com N posições.
Toda pilha tem um atributo topo que indica a posição do topo da pilha no array.
Inserir um novo elemento no topo de P
0
(empilhar/push);
Remover
o
Pilha:
elemento
do
topo
de
1
14
32
3
2
7
25
4
1
5
...
N-1
...
P
Onde deve ficar o topo da pilha?
(desempilhar/pop).
Estrutura de Dados
1
12/3/2012
Pilha como Array
Pilha como Array - Empilha
Seja pilha uma estrutura linear representada através de um array P com N posições.
Toda pilha tem um atributo topo que indica a posição do topo da pilha no array.
0
Pilha:
1
3
2
25
7
32
4
5
1
...
N-1
...
topo = numElementos-1
0
14
Pilha:
1
32
3
2
7
5
4
25
...
N-1
...
1
0
Pilha:
1
3
2
25
7
32
1
4
5
...
N-1
...
8
topo topo = numElementos-1
Pilha como Array - Desempilha
0
Pilha:
1
14
32
3
2
7
4
25
5
1
...
N-1
Implementação de Pilhas: Array ou Arranjos
Os itens da pilha são armazenados em posições contíguas de memória.