8 Pilhas e Filas

Prévia do material em texto

Pilhas e Filas
Computação 2
PIlha - Stack
Estrutura de dados que segue o comportamento 
LIFO (Last In First Out), na qual o último elemento 
inserido é o primeiro a ser removido.
Operações
Empilhar - Push
Adiciona um novo elemento ao topo da pilha.
Operações
Desempilhar - Pop
Retorna e remove o elemento do topo da pilha.
Implementação utilizando vetor
#define MAX 10
void empilha (int pilha[], int valor, int* topo) {
 if (*topo < MAX) {
 *topo = *topo + 1;
 pilha[*topo] = valor;
 } else {
 printf("Não foi possível empilhar: pilha cheia!");
 }
}
Implementação utilizando vetor
int desempilha (int pilha[], int* topo){
 int valor = 0;
 if (*topo >= 0) {
 valor = pilha[*topo];
 *topo = *topo - 1;
 } else {
 printf("Não foi possível desempilhar: pilha vazia!");
 }
 return valor;
}
Exemplo
● Exemplo de pilha no C Tutor
Exemplos de aplicações
Torre de Hanói é um "quebra-cabeça" que consiste em uma 
base contendo três pinos, em um dos quais são dispostos 
alguns discos uns sobre os outros, em ordem crescente de 
diâmetro, de cima para baixo. O problema consiste em passar 
todos os discos de um pino para outro qualquer, usando um 
dos pinos como auxiliar, de maneira que um disco maior 
nunca fique em cima de outro menor em nenhuma situação.
Exemplo: a expressão: 5 + (1 + 2) × 4 - 3
pode ser representada em RPN como:
5 1 2 + 4 × + 3 −
Podemos calculá-la numa pilha como:
se o valor lido for uma operação
desempilha dois valores
aplica a operação
empilha o resultado
senão
empilha o valor lido
Notação polonesa inversa (RPN)
Próximo valor Operação Pilha
5 empilha valor 5
1 adicionar valor 5, 1
2 adicionar valor 5, 1, 2
+ somar 5, 3
4 adicionar valor 5, 3, 4
× multiplicar 5, 12
+ somar 17
3 adicionar valor 17, 3
− subtrair 14
Resultado 14
Exercícios para praticar
1. Baseado no algoritmo apresentado no slide 
anterior implemente uma calculadora de notação 
polonesa inversa para aceitar as operações de 
soma, subtração e multiplicação.
2. Implemente as operações de empilhar e 
desempilhar para obter o comportamento de 
pilha em uma lista encadeada.
Fila - Queue
Estrutura de dados que 
segue o comportamento 
FIFO (First In First Out), 
na qual o primeiro 
elemento inserido é o 
primeiro a ser removido.
Exemplos de aplicação
● Fila de impressão
● Fila de processos
● Fila de pedidos
● Fila de pessoas
● Etc
Operações
Enfileirar - Enqueue
Adiciona um novo elemento ao fim da fila
Operações
Desenfileirar - Dequeue
Retorna e remove o primeiro elemento da fila
Implementação utilizando vetor
#define MAX 5
void enfileira(int fila[], int valor, int *inicio, 
int* qtd){
 int pos;
 if (*qtd < MAX) {
 pos=(*inicio+*qtd)%MAX ;
 fila[pos] = valor;
 *qtd = *qtd + 1;
 } else {
 printf("Não foi possível enfileirar: fila cheia!");
 }
}
Implementação utilizando vetor
int desenfileira(int fila[], int *inicio, int *qtd){
 int valor = 0;
 if (*qtd > 0) {
 valor=fila[*inicio];
 *inicio = (*inicio + 1) % MAX;
 *qtd = *qtd - 1;
 } else {
 printf("Não foi possível desenfileirar: fila 
vazia!");
 }
 return valor;
}
Exemplo
● Exemplo de Fila no C Tutor
Exercícios para praticar
3. Implemente um programa para gerenciar uma fila 
de pedidos de uma lanchonete. O programa 
deverá ter duas opções:
1. pedir: solicita ao usuário o pedido e adiciona na fila
2. servir: apresentar o próximo pedido da fila e remover
4. Implemente as operações de enfileirar e 
desenfileirar para obter o comportamento de fila 
em uma lista encadeada. (É recomendado o uso 
de um ponteiro para o início e outro para o fim da 
fila.)