A5_ED_Pilha

Prévia do material em texto

Estruturas de Dados
PILHA
ALOCAÇÃO ALOCAÇÃO ALOCAÇÃO ALOCAÇÃO ESTÁTICA DE ESTÁTICA DE ESTÁTICA DE ESTÁTICA DE MEMÓRIAMEMÓRIAMEMÓRIAMEMÓRIA
ESTRUTURAS DE DADOS BÁSICAS
� Conjunto de itens organizados. 
� Podem representar “coleções”. 
� É possível adicionar, remover ou pesquisar itens em uma estrutura de dados.
� Características como o lugar da estrutura onde itens são adicionados ou 
removidos diferenciam os tipos especiais de estruturas de dados. 
� Pilhas, Filas e Listas.
2
Estruturas de Dados Lineares
� Conjunto de dados organizados de forma linear.
� Exemplos:
� Lista
� Pilha
� Fila
3
PILHA
� Stack
� Estrutura de dados
� Funcionamento � baseado em uma pilha “natural” 
� Exemplo: Pilha de pratos.
� As operações de inserção e remoção realizadas sempre no final (topo) da 
pilha:
� Itens ADICIONADOS no topo da pilha.
� Itens REMOVIDOS do topo da pilha.
4
PILHA
� Chamadas de listas LIFO (Last-in, First-out) 
� O último elemento a ser inserido será o primeiro a ser retirado. 
� Pilhas são úteis para processar estruturas aninhadas, como: 
� Expressões algébricas. 
� Funções de programa que chamam outras funções.
� São utilizadas para implementar algoritmos de análise sintática e de avaliação 
de expressões
� Utilizados em compiladores e interpretadores.
5
Funcionamento de PILHA
6
Pilha – Alocação Sequencial
� Também denominada: pilha estática.
� Implementada por meio de vetores (estruturas estáticas). 
� Vetores possuem um espaço limitado para o armazenamento de dados. 
� É necessário definir um espaço grande o suficiente para guardar a pilha.
� A alocação sequencial exige uma área contígua de memória correspondente 
ao tamanho previsto pela estrutura. 
� Os vetores (alocação sequencial) são mais “simples” de implementar.
7
Implementação Sequencial
� A ordem linear é determinada pelos índices do vetor.
� Elementos dispostos em posições contíguas da memória.
� Mais fácil compreensão e implementação. 
� Requer espaço de memória com capacidade para guardar N elementos.
� Limitada com relação ao número de elementos que tem capacidade de manipular.
� O espaço reservado pode estar sendo pouco utilizado.
� Exige maior esforço computacional em determinadas situações.
8
Pilha – Alocação Encadeada
� Também denominada: pilha dinâmica.
� Utiliza a alocação dinâmica de memória. 
� Ponteiros são utilizados para identificar a sequência de elementos da 
pilha.
� Otimiza o uso da memória do computador.
9
Implementação Encadeada
� Elementos armazenados em posições não contínuas de memória.
� Cada elemento deve possuir uma referência para o próximo elemento.
� Desse modo, cada elemento deve conter o “dado” e um ponteiro com o 
endereço do próximo elemento da pilha. 
� Implementação dita mais “complexa” que a sequencial.
10
Pilha como um TDA
� TDA – Tipo Abstrato de Dado
� Um TDA engloba a definição do tipo do dado e as operações relacionadas 
sobre este tipo.
� Um TDA para a estrutura de dados Pilha envolve:
� A declaração do tipo de dado pilha. 
� As operações realizadas sobre a pilha.
� Pode ser implementada utilizando a alocação sequencial ou a alocação 
encadeada. 
11
Pilha – aspecto estrutural
� Utiliza um vetor para armazenar as informações da pilha. 
� Requer um indicador (índice) da posição do topo da pilha.
� A pilha pode ser representada por uma estrutura que contém:
� Uma matriz de itens da pilha.
� Índice para o topo da pilha. 
12
Implementando a Pilha em C
� implementação
#define MAX 100
typedef struct{
int item[MAX];
int topo;
}Pilha;
.....
Pilha p;
13
Pilha – aspecto funcional
� Operações da pilha
� Inicializar a pilha.
� Adicionar um item na pilha � push().
� Remover um item da pilha � pop().
� Testar se a pilha está vazia.
� Testar se a pilha está cheia.
14
ALGORITMO Inicializa Pilha
Objetivo: Inicializar a pilha.
� Exemplo de implementação
void iniPilha(Pilha *p) {
p->topo = 0;
}
15
ALGORITMO Verifica se Pilha Vazia
Objetivo: Verificar se a pilha está vazia.
� Exemplo de implementação
int vaziaPilha(Pilha *p) {
if (p->topo == 0){
return(1);
}
else {
return(0);
}
}
16
ALGORITMO Verifica se Pilha Cheia
Objetivo: Verificar se a pilha está cheia.
� Exemplo de implementação
int cheiaPilha(Pilha *p) {
if (p->topo == MAX){
return(1);
}
else {
return(0);
}
}
17
ALGORITMO pushpushpushpush
� Procedimentos realizados
� Verifica se há espaço, ou seja, se a pilha não está cheia.
� Adiciona o novo item na pilha.
� Incrementa o topo da pilha.
� Parâmetros
� O dado a ser inserido.
� A pilha.
� Constante utilizada pelo algoritmo
constante ErroPilhaCheia = -1
18
ALGORITMO pushpushpushpush
� Exemplo de implementação
int push(Pilha *p, int x)
{
if (cheiaPilha(p)) {
return(ERROPILHACHEIA);
}
else {
p->item[p->topo] = x;
p->topo++;
return(p->topo);
}
}
19
ALGORITMO poppoppoppop
� Procedimentos realizados
� Verifica se há elementos na pilha, ou seja, se a pilha não está vazia.
� Decrementa o topo da pilha.
� Retorna o elemento do topo da pilha.
� Parâmetros
� A pilha.
� Constante utilizada pelo algoritmo
constante ErroPilhaVazia = -2
20
Exercício 1
Desenhe a pilha resultante depois de executar as seguintes funções (nesta ordem):
1. iniPilha();
2. push(1);
3. push(5);
4. pop();
5. push(32);
6. push(20);
7. push(55);
8. pop();
21
Exercício 2
Desenhe a pilha resultante depois de executar as seguintes funções (nesta ordem):
1. iniPilha();
2. push(‘A’);
3. push(‘B’);
4. pop();
5. push(‘C’);
6. push(‘D’);
7. iniPilha();
8. pop();
22