Pilhas e Filas
Prof. Frederico Brito Fernandes
[email protected]
CONTEÚDO
(1) Pilhas
(2) Filas
(1) Pilhas
Definição...
• A idéia fundamental da pilha é que todo o acesso a seus
elementos é feito através do seu topo
• Quando um elemento novo é introduzido na pilha, ele
passa a ser o elemento do topo
• O único elemento que pode ser removido da pilha é o do
topo.
– Análogo a uma pilha de pratos
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
2
(1) Pilhas
Operações
• O processo de inserção e remoção acontecem no topo da
pilha
• Operações:
– push (empilhar) e pop (desempilhar)
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
3
(1) Pilhas
Resumindo...
• O tipo Pilha armazena
dados
• Inserções e remoções
seguem o esquema
“último a entrar é o
primeiro a sair” (last-in
first-out ou LIFO)
• Inserções e remoções são
feitas no topo da pilha
Estrutura, Pesquisa e Ordenação de Dados
• Exceções
– Pode acontecer na tentativa de
retirar um elemento de uma
pilha vazia
• Tem de usar a operação vazia()
para checar a pilha antes de
retirar um elemento
– Pode acontecer na tentativa de
adicionar um elemento em uma
pilha cheia
Frederico Brito Fernandes
• Tem de checar se a pilha está
cheia antes de adicionar o novo
elemento
4
(1) Pilhas
Aplicações...
• É a estrutura de dados mais utilizada em programação,
sendo inclusive implementada diretamente pelo
hardware da maioria das máquinas modernas.
• Implementação de compiladores
– Pilha de execução de funções chamadas
– Avaliação de expressões
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
5
(1) Pilhas
Implementação em vetor
• Fixar o número máximo de elementos na pilha
• O tipo Pilha possui dois atributos:
– n é o número de elementos armazenados no vetor
– Vet é o vetor de elementos
• pilha vazia se caracteriza por n = 0
• pilha cheia se caracteriza por n = MAX
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
6
(1) Pilhas
Operações
push (elemento)
elemento pop()
boolean ehVazia()
imprime()
1. Implementar com vetor
2. Implementar com lista encadeada
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
7
(2) Filas
Definição
• Uma fila é um conjunto ordenado de itens a partir do
qual pode-se eliminar itens numa extremidade (chamada
início da fila) e no qual pode-se inserir itens na outra
extremidade (chamada final da fila).
– Uma fila de banco ou no ponto de ônibus
– Um grupo de carros aguardando sua vez no pedágio
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
8
(2) Filas
Resumindo...
• O tipo Fila armazena
dados
• Inserções e remoções
seguem o esquema
“primeiro a entrar é o
primeiro a sair” (first-in
first-out ou FIFO)
• Inserções são feitas no
final da fila e remoções
são feitas no início da fila
Estrutura, Pesquisa e Ordenação de Dados
• As principais operações
são:
– insere(elemento)
• insere um elemento no final
da fila
– retira(): elemento
• Remove e retorna o
elemento do início da fila
– vazia():booleano
Frederico Brito Fernandes
• Indica se não há nenhum
elemento armazenado
9
(2) Filas
Operações
•
•
•
•
•
•
Estrutura, Pesquisa e Ordenação de Dados
insere(q, A);
insere(q, B);
insere(q, C);
x = retira (q);
insere(q, D);
insere(q, E)
Frederico Brito Fernandes
10
(2) Filas
Cuidado...
• A operação insere sempre pode ser executada
• A operação retira só pode ser aplicada se a fila não
estiver vazia;
– Remoção de uma fila vazia causa underflow.
– A operação vazia é sempre aplicável na operação retira .
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
11
(2) Filas
Resumindo...
• Operações auxiliares:
• Exceções
– início(): elemento
• Retorna o elemento do
início da fila sem removê-lo
– Pode acontecer na tentativa de
retirar um elemento de uma fila
vazia
• Tem de usar a operação vazia()
para checar a fila antes de
retirar um elemento
– tamanho(): inteiro
• Retorna o número de
elementos armazenados
– Pode acontecer na tentativa de
adicionar um elemento em uma
fila cheia
• Tem de checar se a fila está
cheia antes de adicionar o novo
elemento
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
12
(2) Filas
Aplicações
• Acesso a recursos compartilhados
– Fila de impressão
• Quando uma impressora é compartilhada por várias máquinas
• Usa-se a estratégia mais simples de tratar todas as requisições com a
mesma prioridade e imprimir os documentos na ordem em que foram
submetidos – o primeiro submetido é o primeiro a ser impresso
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
13
(2) Filas
Implementação com vetor
• Fixe o número máximo N de elementos na fila
• O processo de inserção e remoção em extremidades
opostas fará com que a fila “ande” no vetor
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
14
(2) Filas
Implementação com vetor
• Problema: em um dado instante, a parte ocupada do
vetor pode chegar à última posição
• Solução: podemos incrementar as posições do vetor de
forma “circular”
– se o último elemento da fila ocupa a última posição do vetor,
inserimos os novos elementos a partir do início do vetor
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
15
(2) Filas
Implementação com vetor
• Fixar o número máximo de elementos na pilha
• O tipo Fila possui três atributos:
– ini marca a posição do próximo elemento a ser retirado da fila;
– fim marca a posição (vazia), onde será inserido o próximo
elemento
– Vet é o vetor de elementos
• a fila vazia se caracteriza por ter ini == fim
• fila cheia se caracteriza por incr(fim) == ini
• a posição indicada por fim permanece sempre vazia
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
16
(2) Filas
Implementação com vetor
• Os índices do vetor são incrementados de maneira que
seus valores progridam “circularmente”
– Função auxiliar responsável por incrementar o valor de um
índice
int incr(int i)
{
return (i+1)%N;
}
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
17
(2) Filas
Operações
boolean ehVazia ()
insere(elemento)
elemento retira()
imprime()
1. Implementar com vetor
2. Implementar com lista encadeada
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
18