Faculdade de Informática e Tecnologia de Pernambuco
ESTRUTURA DE DADOS
Profa. Juliana Mafra
([email protected])
30 de Setembro de 2009
Tipos Especiais de Listas
Pilhas
2
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Pilhas
 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.
 Propriedade: o último item inserido é o primeiro item que pode
ser retirado da lista. São chamadas listas lifo (“last-in, first-out”).
3
ESTRUTURA DE DADOS
Profa. Juliana Mafra
TAD Pilhas: Operações
 Criar uma pilha P vazia
 Testar se P está vazia
 Obter o elemento do topo da pilha (sem eliminar)
 Inserir um novo elemento no topo de P (empilhar/push)
 Remover o elemento do topo de P (desempilhar/pop)
4
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Pilhas: Implementações
 Existem várias opções de estruturas de dados que
podem ser usadas para representar pilhas.
 As
duas representações mais utilizadas são as
implementações por meio de arranjos e de
apontadores.
5
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Implementação de Pilhas: Arranjos
 Os itens da pilha são armazenados em posições contíguas de
memória.
 Como as inserções e as retiradas ocorrem no topo da pilha, um
ponteiro chamado topo é utilizado para controlar a posição do item
no topo da pilha.
#define MAX 10
a0 a1 a2
0
1
2
topo
6
ESTRUTURA DE DADOS
typedef int telem;
...
MAX -1
typedef struct {
telem v[MAX];
int topo;
} tpilha
Profa. Juliana Mafra
Operações sobre Pilhas: Arranjos
 Criar uma pilha vazia
void criar (tpilha *p){
p->topo = -1;
}
 Obter o elemento do topo da pilha (sem eliminar)
int elemtopo (tpilha p, telem *valor){
if (vazia(p)) return 0;
*valor = p.v[p.topo];
return 1;
}
7
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Operações sobre Pilhas: Arranjos
 Inserir um novo elemento no topo da pilha (empilhar)
a0 a1 a2 a3
0
1
3
2
...
MAX -1
topo
int push (tpilha *p, telem valor) {
if (p->topo == MAX-1) return 0; /* pilha cheia*/
p->topo++;
p->v[p->topo] = valor;
return 1;
}
8
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Operações sobre Pilhas: Arranjos
 Remover o elemento do topo da pilha (desempilhar)
a0 a1 a2 a3
0
1
2
3
...
MAX -1
topo
int pop (tpilha *p, telem *valor){
if (vazia(*p)) return 0;
*valor = p->v[p->topo];
v[p->topo--];
return 1;
}
9
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Implementação de Pilhas: Apontadores
 Permite utilizar posições não contíguas de memória.
 Cada nó contém um item da pilha e um apontador para o nó
seguinte.
 Toda pilha possui um apontador chamado topo que aponta
para o primeiro nó da pilha.
typedef int telem;
topo
5
dado|prox
8
1
dado|prox
Indicador do fim da
pilha (referência null)
10
ESTRUTURA DE DADOS
typedef struct no{
telem dado;
struct no* prox;
} tno;
typedef tno* tpilha;
Profa. Juliana Mafra
Operações sobre Pilhas: Apontadores
 Criar uma pilha vazia
void criar (tpilha *p){
*p = NULL;
}
 Obter o elemento do topo da pilha (sem eliminar)
int elemtopo (tpilha p, telem *elem) {
if (vazia(p)) return 0;
*elem = p->dado;
return 1;
}
11
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Operações sobre Pilhas: Apontadores
 Inserir um novo elemento no topo da pilha (empilhar)
topo
5
8
9
novo nó
int push (tpilha *p, telem valor){
tpilha novo;
novo = (tno *) malloc(sizeof(tno));
novo->dado = valor;
novo->prox = *p;
*p = novo;
return 1;
}
12
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Operações sobre Pilhas: Apontadores

Remover o elemento do topo da pilha (desempilhar),
topo
1
9
...
2
atual
int pop (tpilha *p, telem *valor) {
tpilha atual;
if (vazia(*p)) return 0;
atual = *p;
*valor = (*p)->dado;
*p = atual->prox;
free(atual);
return 1;
}
13
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Pilha Sequencial x Encadeada
 No caso geral de listas ordenadas, a maior vantagem da
alocação encadeada sobre a sequencial - se a memória
não for problema - é a eliminação de deslocamentos
na inserção ou eliminação dos elementos.
 No caso das pilhas, essas operações de deslocamento
não ocorrem. Portanto, podemos dizer que a alocação
sequencial é mais vantajosa na maioria das vezes.
14
ESTRUTURA DE DADOS
Profa. Juliana Mafra