Upload
bruna-gorjao-pedroso
View
215
Download
2
Embed Size (px)
Citation preview
Profa. Juliana Mafra([email protected])
ESTRUTURA DE DADOS
30 de Setembro de 2009
Faculdade de Informática e Tecnologia de Pernambuco
Tipos Especiais de Listas
ESTRUTURA DE DADOS Profa. Juliana Mafra2
Pilhas
Pilhas
3
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”).
ESTRUTURA DE DADOS Profa. Juliana Mafra
TAD Pilhas: Operações
4
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)
ESTRUTURA DE DADOS Profa. Juliana Mafra
Pilhas: Implementações
5
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.
ESTRUTURA DE DADOS Profa. Juliana Mafra
Implementação de Pilhas: Arranjos
6
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.
ESTRUTURA DE DADOS Profa. Juliana Mafra
...a0 a1 a20 1 2 MAX -1
topo
#define MAX 10 typedef int telem; typedef struct { telem v[MAX]; int topo; } tpilha
Operações sobre Pilhas: Arranjos
7
Criar uma pilha vazia
Obter o elemento do topo da pilha (sem eliminar)
ESTRUTURA DE DADOS Profa. Juliana Mafra
void criar (tpilha *p){ p->topo = -1; }
int elemtopo (tpilha p, telem *valor){ if (vazia(p)) return 0;
*valor = p.v[p.topo]; return 1; }
Operações sobre Pilhas: Arranjos
8
Inserir um novo elemento no topo da pilha (empilhar)
ESTRUTURA DE DADOS Profa. Juliana Mafra
int push (tpilha *p, telem valor) { if (p->topo == MAX-1) return 0; /* pilha cheia*/ p->topo++; p->v[p->topo] = valor; return 1; }
...a0 a1 a20 1 2 MAX -1
topo
3
a3
Operações sobre Pilhas: Arranjos
9
Remover o elemento do topo da pilha (desempilhar)
ESTRUTURA DE DADOS Profa. Juliana Mafra
int pop (tpilha *p, telem *valor){ if (vazia(*p)) return 0;
*valor = p->v[p->topo]; v[p->topo--]; return 1; }
...a0 a1 a20 1 2 MAX -1
topo
3
a3
Implementação de Pilhas: Apontadores
10
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.
ESTRUTURA DE DADOS Profa. Juliana Mafra
typedef int telem; typedef struct no{ telem dado; struct no* prox; } tno;
typedef tno* tpilha;
5topo 8 1
Indicador do fim da pilha (referência null)
dado|prox dado|prox
Operações sobre Pilhas: Apontadores
11
Criar uma pilha vazia
Obter o elemento do topo da pilha (sem eliminar)
ESTRUTURA DE DADOS Profa. Juliana Mafra
void criar (tpilha *p){ *p = NULL; }
int elemtopo (tpilha p, telem *elem) { if (vazia(p)) return 0; *elem = p->dado; return 1; }
Operações sobre Pilhas: Apontadores
12
Inserir um novo elemento no topo da pilha (empilhar)
ESTRUTURA DE DADOS Profa. Juliana Mafra
int push (tpilha *p, telem valor){ tpilha novo; novo = (tno *) malloc(sizeof(tno)); novo->dado = valor; novo->prox = *p; *p = novo; return 1; }
5topo 8
9novo nó
Operações sobre Pilhas: Apontadores
13
Remover o elemento do topo da pilha (desempilhar),
ESTRUTURA DE DADOS Profa. Juliana Mafra
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; }
1 29atual
topo ...
Pilha Sequencial x Encadeada
14
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.
ESTRUTURA DE DADOS Profa. Juliana Mafra