Upload
gibson
View
61
Download
2
Embed Size (px)
DESCRIPTION
Pilhas e Filas. Denise Guliato Faculdade de Computação – UFU www.facom.ufu.br/~guliato. Vários slides foram adaptados de Nina Edelwais e Renata Galante Estrutura de Dados – Série de Livros Didáticos - Informática - UFRGS. Pilhas e filas. Listas lineares especiais. - PowerPoint PPT Presentation
Citation preview
Pilhas e FilasPilhas e Filas
Denise GuliatoFaculdade de Computação – UFUwww.facom.ufu.br/~guliato
Vários slides foram adaptados de Nina Edelwais e Renata GalanteEstrutura de Dados – Série de Livros Didáticos - Informática - UFRGS
Pilhas e filas
Disciplina restrita
• acesso permitido somente em alguns nodos
Com disciplina restrita de organização e acesso a seus nodos
Listas lineares especiaisListas lineares especiais
Pilha
Listas lineares especiaisListas lineares especiaismais usuaismais usuais
Pilhas e filas
Fila
LIFO Last In First Out o último componente inserido é o primeiro a ser retirado
FIFO First In First Out o primeiro componente inserido é também o primeiro a ser retirado
Consultas
Exclusões Inserções
Topo
Base
Pilhas e FilasPilhas e Filas
Início FinalInserções
Exclusõese
Consultas
PILHA
FILA
PilhasPilhas
ConsultasExclusões Inserções
Topo
Base
• Criar uma pilha vazia• Inserir um elemento no topo da pilha• Remover um elemento do topo de pilha• Consultar o topo da pilha• Destruir a pilha• Verificar se é cheia•Verificar se é vazia
Operações sobre PilhasOperações sobre PilhasPilhas
TAD PilhaTAD Pilha
Dados: numeros inteiros
Operações:E_cheia entrada: o endereço da pilha processo: verifica se pilha esta na condição de
cheia saida: 1 se cheia, 0 caso contrário (-1 se pilha não
existe)
TAD PilhaTAD Pilha
E_vazia entrada: endereço da pilha processo: verifica se a pilha está na condição
de vazia saida: 1 se vazia, 0 caso contrario (-1 se a pilha
não existe)
TAD PilhaTAD Pilha
Cria_pilha entrada: nenhuma processo: aloca a pilha e a coloca na condição
de vazia saida: endereço da pilha
TAD PilhaTAD Pilha
Push entrada: endereço da variável que contém o
endereço da pilha e o elemento processo: insere elemento no topo da pilha e
atualiza pilha saida: 1 se sucesso , 0 se fracasso
TAD PilhaTAD Pilha
Pop entrada: endereço da variavel que contem o
endereço da pilha e endereço do elemento que conterá o valor do elemento a ser removido
processo: remove elemento do topo da pilha e atualiza pilha
saida: 1 se sucesso e 0 se fracasso
TAD PilhaTAD Pilha
Top entrada: endereço da pilha e o endereço do
elemento consultado processo: consulta o topo da pilha saida: 1 se sucesso e 0 se fracasso
TAD PilhaTAD Pilha
Libera_pilha entrada: endereço do endereço da pilha processo: libera toda área alocada para a pilha saida: nenhuma
PilhasPilhas
Pilhas Pilhas implementadas por implementadas por contiguidade físicacontiguidade física
Pilha - contigPilha - contiguuidade física idade física LIMITE
Topo
BasePilha
Índicesdo arranjo
Pilha – contiguidade física
• Implementada usando um arranjo
• Índices de controle da pilha:• BASE da pilha• TOPO atual da pilha• LIMITE máximo que pode ser ocupado pela pilha
Exemplo de manipulação de uma pilhaExemplo de manipulação de uma pilha
MAX-1
TOPO
BASE
PILHA
9
8
7
6
5
4
3
2
1
0 3
MAX-1
TOPOBASE 3
7
MAX-1
TOPOBASE 3
75
MAX-1
TOPO
BASE 37
MAX-1
TOPOBASE
Retorna “7”
1. Inicializar pilha de valores inteiros,a partir do índice 0, máximo 10 nós2. Inserir nodo com valor 33. Inserir nodo com valor 74. Inserir nodo com valor 55. Remover nodo do topo6. Consultar pilha
Pilha – contiguidade física
PILHA PILHA PILHA PILHA
9
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
Retorna “5”
Pilha – contiguidade física
struct stack { int pilha[MAX]; int topo; };typedef struct stack Pilha;
Tipo de dados utilizado nos algoritmos para pilha implementada por contiguidade física:
MAX - 1
TopoBase
Pilha
1. Alocar área para a pilha2. Indicar que a pilha está vazia
Exemplo:
Base 0Topo – 1MAX 10
Criação da pilhaCriação da pilha
Pilha – contiguidade física
9
8
7
6
5
4
3
2
1
0
Pilha *Cria_pilha(void){ Pilha *Ptp; Ptp = (Pilha*) malloc(sizeof(Pilha)); if (Ptp != NULL) Ptp->topo = -1; return Ptp;}
Algoritmo:Algoritmo: criação de uma pilha criação de uma pilhaPilha *Cria_pilha(void)Pilha *Cria_pilha(void)
Pilha – contiguidade física
Verifica se pilha é cheiaVerifica se pilha é cheia int E_cheia(Pilha *Ptp) int E_cheia(Pilha *Ptp)
int E_vazia(Pilha *Ptp)int E_vazia(Pilha *Ptp)
int E_cheia(Pilha *Ptp){ if ( Ptp == NULL) return -1; if (Ptp->topo == MAX-1) return 1; else return 0;}
int E_vazia(Pilha *Ptp){ if (Ptp == NULL) return -1; if (Ptp->topo == -1) return 1; else return 0;}
MAX -1
Topo
Base
Pilha
MAX - 1
Topo
Base
Pilha
9876543210
Operação PUSH
Inserção de um elemento na pilhaInserção de um elemento na pilhaPilha – contiguidade física
9
8
7
6
5
4
3
2
1
0
Pilha – contiguidade físicaAlgoritmo: Algoritmo: inserer elemento no topo da pilhaint Push(Pilha **Ptp, int elem)
int Push(Pilha **Ptp, int elem){ if ((*Ptp) == NULL||(*Ptp)->topo == MAX-1) return 0; (*Ptp)->topo++; (*Ptp)->pilha[(*Ptp)->topo] = elem; return 1;}
MAX - 1
Topo
Base
Pilha
MAX - 1
Topo
Base
Pilha
Operação POP
Pilha – contiguidade física
Remoção de um elemento da pilhaRemoção de um elemento da pilha
9
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
int Pop(Pilha **Ptp, int *elem){ if ((*Ptp) == NULL || (*Ptp)->topo == -1) return 0; *elem = (*Ptp)->pilha[(*Ptp)->topo]; (*Ptp)->topo--; return 1;}
Algoritmo:Algoritmo: Remover elemento do topo de Pilhaint Pop(Pilha **Ptp, int *elem)
?
MAX - 1
Topo
Base
Pilha
9876543210
Pilha – contiguidade física
Consulta o topa da pilhaConsulta o topa da pilha
• Acesso somente ao elemento do topo da pilha
int Top(Pilha *Ptp, int *elem){ if (Ptp == NULL || Ptp->topo == -1) return 0; *elem = Ptp->pilha[Ptp->topo]; return 1;}
Algoritmo:Algoritmo: Consultar o elemento do topo de Pilha int Top(Pilha *Ptp, int *elem)
Destruição da pilhaDestruição da pilhavoid Libera_pilha(Pilha** Ptp)void Libera_pilha(Pilha** Ptp)
void Libera_pilha(Pilha **Ptp){ free(*Ptp); *Ptp=NULL;}
typedef struct stack Pilha;
int E_cheia(Pilha *Ptp);int E_vazia(Pilha *Ptp);Pilha *Cria_pilha(void);int Push(Pilha **Ptp, int elem);int Pop(Pilha **Ptp, int *elem);Int Top(Pilha *Ptp, int *elem);void Libera_pilha(Pilha **Ptp);
paeas.hpaeas.h
Exercício para entregar agoraExercício para entregar agoraImplemente o TAD utilizando uma estrutura de dados com
alocação estática e acesso sequencialImplemente uma função que, usando o TAD Pilha,
verifique se uma dada palavra representada como uma STRING (que não contenha brancos) é uma palíndromo (palavras que não se alteram quando lidas da direita para a esquerda ou da esquerda para a direita). ReExemplos: ANA, ADGHGDA. Retorne 1 se palavra é palindromo, e 0 caso contrario.
Faça um programa que leia uma string (conjunto de palavras separadas por brancos) e indique quais palavras da string são palindromos e quais não são. A string eh dada por linha de comando
PilhasPilhas
Pilhas Pilhas implementadas por implementadas por encadeamentoencadeamento
Base
Topo
inserções
remoções
?consultas
PtPilha
Info prox
Topo da pilha
Base da pilha
Endereço do topo da pilha
Pilha implementada por encadeamentoPilha implementada por encadeamento
struct no{ int info; struct no* prox; };typedef struct no Pilha;
Tipo de dados utilizado nos algoritmos:
Pilha por encadeamento
Criação de pilha encadeadaCriação de pilha encadeada
• Pilha criada vazia
• Atribuir endereço nulo para apontador que contém o endereço do topo da pilha
Algoritmo:Algoritmo: Criar Pilha EncadeadaPilha* Cria_pilha(void)Pilha* Cria_pilha(void)
Pilha por encadeamento
Pilha* Cria_pilha(void){ return NULL;}
Topo
Inserção Inserção de um nodo de um nodo em pilha encadeadaem pilha encadeada
Topo
Pilha por encadeamento
• Novo nodo inserido sempre no topo da pilha
PtPilha PtPilha
Topo
Novo nodo
Base Base
int Push(Pilha **Ptp, int elem){ Pilha *pt; pt= (Pilha*)malloc(sizeof(Pilha)); if (pt == NULL) return 0; pt->prox = (*Ptp); pt->info = elem; (*Ptp) = pt; return 1;}
Algoritmo:Algoritmo: Inserir nodo em Pilha Encadeadaint Push(Pilha **Ptp, int elem)
Pilha por encadeamento
PtPilha
Topo
Desempilha um nodo de umaDesempilha um nodo de uma pilha encadeada pilha encadeada
Pilha por encadeamento
Topo
PtPilha
Base Base
• Só pode ser removido o nodo do topo da pilha
Nodo a ser removido
Pilha por encadeamentoAlgoritmo:Algoritmo: Desempilha nodo de Pilha Encadeadaint Pop(Pilha * *Ptp, int* elem)
int Pop(Pilha **Ptp, int *elem){ Pilha *aux = *Ptp; if (*Ptp == NULL) return 0; *elem = (*Ptp)->info; *Ptp= (*Ptp)->prox; free(aux); return 1;}
Consulta à pilha encadeada Consulta à pilha encadeada
Pilha por encadeamento
• Só pode ser acessado o nodo do topo da pilha
Topo
PtPilha
Base
Nodo que pode ser acessado
Pilha por encadeamentoAlgoritmo:Algoritmo: Consultar nodo do topo de Pilha Encadeadaint Top (Pilha *Ptp, int *elem)
int Top(Pilha *Ptp, int *elem){ if (Ptp == NULL) return 0; *elem = Ptp->info; return 1;}
PtPilha = nilBase
Topo
Base
Topo
Base
Topo
Base
Topo
PtPilha
PtPilha
PtPilha
Destruição de uma pilha encadeada Destruição de uma pilha encadeada
Pilha por encadeamento
• Liberar espaço ocupado pelos nodos, sempre a partir do topo da pilha
• No final: apontador para o topo = endereço nulo
Pilha por encadeamentoAlgoritmo:Algoritmo: Destruir Pilha Encadeadavoid Libera_pilha(Pilha **Ptp)
void Libera_pilha(Pilha **Ptp){ Pilha *aux; while ((*Ptp) != NULL) { aux = (*Ptp); (*Ptp) = (*Ptp)->prox; free(aux); }}
Verifica de pilha esta cheiaVerifica de pilha esta cheiaint E_cheia(Pilha *Ptp)int E_cheia(Pilha *Ptp)
Verifica de pilha esta vaziaVerifica de pilha esta vaziaint E_vazia(Pilha *Ptp)int E_vazia(Pilha *Ptp)
int E_cheia(Pilha *Ptp){ return 0;}
int E_vazia(Pilha *Ptp){ if (Ptp == NULL) return 1; else return 0;}
Exercício
Implemente o TAD Pilha utilizando alocação dinâmica de memória e acesso encadeado.
Teste o programa para reconhecer quais palavras são palíndromos em uma dada frase.
Aplicação da estrutura de dados Aplicação da estrutura de dados Pilha em avaliação de expressões Pilha em avaliação de expressões aritméticasaritméticasForma das expressõesConsidere: Operandos: [0,...,9] Operadores:[+,-,/,x,^] Delimitadores: [(,)]Exemplos:2 + 3 * 5 = 17(2 + 3) * 5 = 25
As operações são efetuadas de acordo com a ordem de precedência dos operadores;
Os parênteses alteram a ordem natural deavaliação dos operadores.
Proponham um algoritmo para Proponham um algoritmo para avaliar expressões aritméticas avaliar expressões aritméticas
22 – 56 / 2;(22-56)/2;40/(2x(3-1) +6);2^3x4;2^(3x4);
?
Notação Polonesa e Notação Polonesa Notação Polonesa e Notação Polonesa InversaInversa
Notação Polonesa (pré-fixada)- Proposta pelo matemático Jan lukasiewiscz em 1920 permite escrever uma expressão aritmética em que a precedência é implícita
Notação Polonesa Inversa (pós-fixada) - proposta por Charles Hamblin em 1950.
Notação Polonesa e Notação Notação Polonesa e Notação Polonesa Inversa Polonesa Inversa expressão:
---------- 2 + 5 x 3 2 + 3 – 42 + (3 – 4)(2 + 4)/(3 -1)(2+4)/(3-1)x42^2*3-4+1/2/(1+1)
forma pós-fixada
2 5 3 x + 2 3 + 4 - 2 3 4 - +2 4 + 3 1 - /2 4 + 3 1 – / 4 x2 2 ^ 3 * 4 – 1 2 / 1 1 + / +
forma pré-fixada
+ 2 x 5 3 - + 2 3 4+ 2 – 3 4/ + 2 4 -3 1x / +2 4-3 1 4 + -*^2 2 3 4 / / 1 2 + 1 1
Forma pós-fixada para avaliar expressoes aritmeticas Forma pós-fixada para avaliar expressoes aritmeticas usando pilha float avalia_expressao(char *pos-fixada)usando pilha float avalia_expressao(char *pos-fixada)
float avalia_expressao(char *pos-fixada)Inicio Ptp aponta para uma pilha vazia Enquanto (nao processou toda expressao pos-fixada) Inicio simbolo = token; se (simbolo é um operando) empilha simbolo na pilha Ptp senao inicio operando2 = desempilha elemento da pilha Ptp operando1 = desempilha elemento da pilha Ptp valor = operando1 simbolo operando2 empilha valor na pilha Ptp fim se Fim enquantoRetorna (desempilha o elemento da pilha Ptp)Fim da funçao
Como transformar uma expressão na forma infixa Como transformar uma expressão na forma infixa para pos-fixa???para pos-fixa???
- Expressões entre parênteses devem ser convertidos de tal forma que possam ser tratadas como um único operando.
- Somente operadores são empilhados . Um operador é empilhado apenas se possui precedência maior que o operador no topo da pilha.
- Abre parênteses é sempre empilhado- Fecha parênteses nunca é empilhado (menor
precedência).Todos os operadores são desempilhados até encontrar um ‘(‘.
- Operandos e operadores desempilhados são colocados na expressão na forma pós-fixa
Algoritmo: char* pos-fixa(char* in-fixa)Inicio inicializa pilha de operadores e aloca area do tamanho da expressao in-fixa enquanto (não processou toda a expressao in-fixa) inicio simbolo = token se (simbolo é operando) coloca simbolo na expressao pos-fixa senao inicio enquanto (pilha não eh vazia E precedencia(topo da pilha, simbolo) inicio elem-topo = desempilha coloca elem-topo na expressao pos-fixa fim enquanto se (pilha eh vazia OU simbolo # ‘)’ ) empilha simbolo senao enquanto ( (elem-topo = desempilha) != ‘(‘ ) coloca elem-topo na expressao pos-fixa; fim se fim se fim enquanto enquanto ( pilha não eh vazia) desempilha topo e coloca na expressao pos-fixa fim enquanto Fim da função
Precedencia(‘(‘, op) --- falsePrecedencia (op,’(‘) ---- false, exceto op=‘)’Precedencia (op,’)’) -----false, exceto op=‘(‘Precedencia (‘)’, op) --- indefinido
Se precedência do topo da pilha maior que símbolo true
símbolotopo de pilha
Exercício usando pilha Exercício usando pilha
Escreva uma função que transforma uma expressão da forma in-fixa para a forma pós-fixa.
Escreva uma função que avalie uma expressão na forma pós-fixa
Escreva um programa que entra com a expressão aritmética pela linha de comando e avalia a expressão.
Exercício usando pilha – cont.Exercício usando pilha – cont.
Os operandos são números reais (positivos e negativos);
Os operadores são: {+,-,x,/,^}Os delimitadores são: {(,)}
Ex: 3.4 x 5 + ( 2.1 – 12 ) (-23 + 24.3 / 2.1) ^ 3
Exercicio1- Altere a estrutura do TAD Pilha para conter caracter
( o campo info deve conter dado do tipo char)2- Escreva as funçoes para o novo TAD3- Escreva um programa de aplicação, que dada uma
string passada por linha de comando, verifique se os parenteses e conchetes estao corretamente balanceado. Use a Pilha para resolver o problema.
Ex: (([[]])) correto (([)]) errado (a + b –(d)) correto