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
Listas lineares especiais
Pilhas e filas
Com disciplina restrita de
organização e acesso a seus
nodos
Disciplina restrita
• acesso permitido
somente em alguns nodos
Listas lineares especiais
mais usuais
LIFO Last In First Out
o último componente inserido
é o primeiro a ser retirado
Pilhas e filas
Pilha
FIFO First In First Out
o primeiro componente inserido
é também o primeiro a ser retirado
Fila
Pilhas e Filas
Exclusões
Inserções
Consultas
Topo
PILHA
Base
FILA
Exclusões
e
Consultas
Início
Final
Inserções
Pilhas
Pilhas
Operações sobre Pilhas
Exclusões
Inserções
Consultas
Topo
• 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
Base
TAD 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
TAD 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
TAD Pilha
Cria_pilha
entrada: nenhuma
processo: aloca a pilha e a coloca na condição
de vazia
saida: endereço da pilha
TAD Pilha
Push
entrada: endereço da lista e o elemento
processo: insere elemento no topo da pilha e
atualiza pilha
saida: 1 se sucesso , 0 se fracasso
TAD Pilha
Pop
entrada: endereço da lista
processo: remove elemento do topo da pilha e
atualiza pilha
saida: endereço do elemento no topo da pilha
ou NULL se pilha é vazia
TAD Pilha
Top
entrada: endereço da lista
processo: consulta o topo da pilha
saida: endereço do elemento no topo da pilha
ou NULL se pilha é vazia
TAD Pilha
Libera_pilha
entrada: endereço da lista
processo: libera toda area alocada para a pilha
saida: nenhuma
Pilhas
Pilhas implementadas
por contiguidade física
Pilha – contiguidade física
Pilha - contiguidade física
LIMITE
• Implementada sobre um arranjo
Topo
• Índices de controle da pilha:
• BASE da pilha
• TOPO atual da pilha
• LIMITE máximo que pode ser
ocupado pela pilha
Base
Pilha
Índices
do arranjo
Pilha – contiguidade física
Exemplo de manipulação de uma pilha
1. Inicializar pilha de valores inteiros,a partir do índice 0, máximo 10 nós
2. Inserir nodo com valor 3
3. Inserir nodo com valor 7
4. Inserir nodo com valor 5
5. Remover nodo do topo
6. Consultar pilha
Retorna “5”
Retorna “7”
MAX-1
9
MAX-1
9
8
7
6
5
4
3
2
1
BASE
0
TOPO
PILHA
3
PILHA
9
MAX-1
9
MAX-1
9
8
8
8
8
7
7
7
7
6
6
6
6
5
5
5
5
4
4
4
4
3
3
3
3
2
2
2
2
1
BASE
TOPO
MAX-1
0
TOPO
BASE
7
3
PILHA
TOPO
1
0
BASE
5
7
3
PILHA
1
0
TOPO
BASE
7
3
PILHA
1
0
Pilha – contiguidade física
Tipo de dados utilizado nos algoritmos para pilha implementada
por contiguidade física:
struct stack {
int pilha[MAX];
int topo;
};
typedef struct stack *Pilha;
Pilha – contiguidade física
Criação da pilha
9
MAX - 1
8
7
6
5
1. Alocar área para a pilha
2. Indicar que a pilha está vazia
4
3
2
1
Exemplo:
Base  0
Topo  – 1
MAX  10
Base
Topo
0
Pilha
Algoritmo: criação de uma pilha
Pilha Cria_pilha(void)
Pilha – contiguidade física
Pilha Cria_pilha(void)
{
Pilha Ptp;
Ptp = (Pilha) malloc(sizeof(struct stack));
if (Ptp != NULL)
Ptp->topo = -1;
return Ptp;
}
Verifica se pilha é cheia
int E_cheia(Pilha Ptp)
int E_cheia(Pilha Ptp)
{
if (Ptp->topo == MAX-1)
return 1;
else return 0;
}
int E_vazia(Pilha Ptp)
int E_vazia(Pilha Ptp)
{
if (Ptp->topo == -1)
return 1;
else return 0;
}
Pilha – contiguidade física
Inserção de um elemento na pilha
Operação PUSH
9
MAX -1
9
8
7
6
5
4
3
2
1
0
MAX - 1
8
7
6
5
4
3
Topo
Topo
2
1
Base
0
Pilha
Base
Pilha
Algoritmo:
Pilha – contiguidade física
inserer elemento no topo da pilha
int Push(Pilha *Ptp, int elem)
int Push(Pilha *Ptp, int elem)
{
if ((*Ptp)->topo == MAX-1)
return 0;
(*Ptp)->topo++;
(*Ptp)->pilha[(*Ptp)->topo] = elem;
return 1;
}
Pilha – contiguidade física
Remoção de um elemento da pilha
Operação POP
9
MAX - 1
Topo
8
8
7
7
6
6
5
5
4
4
3
Base
Topo
3
2
2
1
1
0
Pilha
9
MAX - 1
Base
0
Pilha
Algoritmo: Remover elemento do topo de Pilha
int* Pop(Pilha *Ptp)
int* Pop(Pilha *Ptp)
{
int* elem;
if ((*Ptp)->topo == -1)
return NULL;
elem = (int*)malloc(sizeof(int));
*elem = (*Ptp)->pilha[(*Ptp)->topo];
(*Ptp)->topo--;
return elem;
}
Pilha – contiguidade física
Consulta o topa da pilha
MAX - 1
• Acesso somente ao elemento do topo da pilha
Topo
?
Base
Pilha
9
8
7
6
5
4
3
2
1
0
Algoritmo:
Consultar o elemento do topo de Pilha
int* Top(Pilha Ptp)
int* Top(Pilha Ptp)
{
int* elem;
if (Ptp->topo == -1)
return NULL;
elem = (int*)malloc(sizeof(int));
*elem = Ptp->pilha[Ptp->topo];
return elem;
}
int* Top(Pilha Ptp)
{
if (Ptp->topo == -1)
return NULL;
return &(Ptp->pilha[Ptp->topo]);
}
Destruição da pilha
void Libera_pilha(Pilha* Ptp)
void Libera_pilha(Pilha *Ptp)
{
free(*Ptp);
(*Ptp)=NULL;
}
paeas.h
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* Top(Pilha Ptp);
void Libera_pilha(Pilha *Ptp);
Exercício para entregar dia 17/06
Implemente o TAD utilizando uma estrutura de dados
com alocação estática e acesso sequencial
Implemente 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.
Pilhas
Pilhas implementadas
por encadeamento
Pilha implementada por encadeamento
Endereço do topo da pilha
PtPilha
remoções
?
consultas
Info Elo
Topo da pilha
inserções
Topo
Base
Base da pilha
Tipo de dados utilizado nos algoritmos:
struct no{
int info;
struct no* elo;
};
typedef struct no* Pilha;
Pilha por encadeamento
Criação de pilha encadeada
• Pilha criada vazia
• Atribuir endereço nulo para apontador que contém
o endereço do topo da pilha
Algoritmo:
Criar Pilha Encadeada
Pilha Cria_pilha(void)
Pilha Cria_pilha(void)
{
return NULL;
}
Pilha por encadeamento
Pilha por encadeamento
Inserção de um nodo em pilha encadeada
• Novo nodo inserido sempre no topo da pilha
PtPilha
PtPilha
Topo
Novo nodo
Topo
Topo
Base
Base
Algoritmo:
Pilha por encadeamento
Inserir nodo em Pilha Encadeada
int Push(Pilha *Ptp, int elem)
int Push(Pilha *Ptp, int elem)
{
Pilha pt;
pt= (Pilha)malloc(sizeof(struct no));
if (pt == NULL)
return 0;
pt->elo = (*Ptp);
pt->info = elem;
(*Ptp) = pt;
return 1;
}
Pilha por encadeamento
Desempilha um nodo de uma pilha encadeada
• Só pode ser removido o nodo do topo da pilha
Nodo a ser removido
PtPilha
Topo
PtPilha
Topo
Base
Base
Algoritmo:
Pilha por encadeamento
Desempilha nodo de Pilha Encadeada
int* Pop(Pilha* Ptp)
int* Pop(Pilha* Ptp)
{
int* elem;
Pilha aux = (*Ptp);
if ((*Ptp) == NULL)
return NULL;
elem = (int*) malloc(sizeof(int));
*elem = (*Ptp)->info;
(*Ptp)= (*Ptp)->elo;
free(aux);
return elem;
}
Pilha por encadeamento
Consulta à pilha encadeada
• Só pode ser acessado o nodo do topo da pilha
Nodo que pode ser
acessado
PtPilha
Topo
Base
Algoritmo:
Pilha por encadeamento
Consultar nodo do topo de Pilha Encadeada
int* Top (Pilha Ptp)
int* Top(Pilha Ptp)
{
int* elem;
if (Ptp == NULL)
return NULL;
elem = (int*) malloc(sizeof(int));
*elem = Ptp->info;
return elem;
}
Pilha por encadeamento
Destruição de uma pilha encadeada
• Liberar espaço ocupado pelos nodos, sempre a partir do topo
da pilha
• No final: apontador para o topo = endereço nulo
PtPilha
Topo
PtPilha
Topo
PtPilha
Topo
Topo
Base
Base
Base
Base
PtPilha = nil
Algoritmo:
Destruir Pilha Encadeada
void Libera_pilha(Pilha*Ptp)
void Libera_pilha(Pilha* Ptp)
{
Pilha aux;
while ((*Ptp) != NULL)
{
aux = (*Ptp);
(*Ptp) = (*Ptp)->elo;
free(aux);
}
}
Pilha por encadeamento
Verifica de pilha esta cheia
int E_cheia(Pilha Ptp)
int E_cheia(Pilha Ptp)
{
return 0;
}
Verifica de pilha esta vazia
int E_vazia(Pilha Ptp)
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 Pilha
em avaliação de expressões aritméticas
Forma das expressões
Considere:
Operandos: [0,...,9]
Operadores:[+,-,/,x,^]
Delimitadores: [(,)]
Exemplos:
As operações são efetuadas de acordo com
2 + 3 * 5 = 17
a ordem de precedência dos operadores;
(2 + 3) * 5 = 25
Os parênteses alteram a ordem natural de
avaliação dos operadores.
Proponham um algoritmo para avaliar
expressões aritméticas
22 – 56 / 2;
(22-56)/2;
40/(2x(3-1) +6);
2^3x4;
2^(3x4);
?
Notação Polonesa
Proposta pelo lógico polones Jan lukasiewiscz
em ?
Permite escrever uma expressao aritmética em
que a precedencia é implicita
Notação Polonesa
expressão: --------2+5x3
2+3–4
2 + (3 – 4)
(2 + 4)/(3 -1)
(2+4)/(3-1)x4
2^2*3-4+1/2/(1+1)
forma pósfixada
253x+
23+4234-+
24+31-/
forma préfixada
+2x53
-+234
+2–34
/ + 2 4 -3 1
24+31–/4x
x / +2 4-3 1 4
22^3*4–12/11+/+
+ -*^2 2 3 4 / / 1 2 + 1 1
Forma pós-fixada para avaliar expressoes aritmeticas
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 enquanto
Retorna (desempilha o elemento da pilha Ptp)
Fim da funçao
Como transformar uma expressão na forma infixa 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
símbolo
topo de pilha
topo = desempilha
coloca topo na expressao pos-fixa
Precedencia(‘(‘, op) --- false
fim enquanto
Precedencia (op,’(‘) ---- false, exceto op=‘)’
se (pilha eh vazia OU simbolo # ‘)’ )
Precedencia (op,’)’) -----false, exceto op=‘(‘
empilha simbolo
Precedencia (‘)’, op) --- indefinido
senao enquanto ( (topo = desempilha) != ‘(‘)
coloca topo na expressao pos-fixa;
fim se
fim se
fim enquanto
enquanto ( pilha não eh vazia)
Exercício usando pilha (entregar dia
30/06 )
Escreva uma função que transforma uma
expressão da forma in-fixa para a forma pósfixa.
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.
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