View
231
Download
0
Category
Preview:
Citation preview
Algoritmos e Estruturas de Dados IIEC012
Pilhas e FilasPilhas e Filas
Prof. César MeloTodos os créditos ao Prof. Leandro Galvão
Pilhas e FilasPilhas e Filas
Pilhas e filas são casos especiais das listas Pilhas e filas são casos especiais das listas encadeadas.encadeadas.
Ambas possuem regras rigorosas para Ambas possuem regras rigorosas para acessar os dados armazenados nelas.acessar os dados armazenados nelas.
As operações de recuperação de dados são As operações de recuperação de dados são destrutivas....destrutivas....
Pilha, característicasPilha, características
É uma das estruturas de dados mais simples;É uma das estruturas de dados mais simples;
Todo o acesso a seus elementos é feito através do Todo o acesso a seus elementos é feito através do seu topo;seu topo;
Quando um novo elemento é introduzido na pilha, Quando um novo elemento é introduzido na pilha, ele passa a ser o elemento do topo, e o único ele passa a ser o elemento do topo, e o único elemento que pode ser removido da pilha é o do elemento que pode ser removido da pilha é o do topo.topo.
PilhasPilhas
Implementa uma política “o primeiro que sai Implementa uma política “o primeiro que sai é o último que entrou (LIFO – last in, first é o último que entrou (LIFO – last in, first out)”.out)”.
Existem duas operações básicas que devem Existem duas operações básicas que devem ser implementadas numa estrutura de pilha: ser implementadas numa estrutura de pilha:
operação para operação para empilharempilhar ( (pushpush) um novo elemento, ) um novo elemento, inserindo-o no topo, inserindo-o no topo,
operação para operação para desempilhardesempilhar ( (poppop) um elemento, ) um elemento, removendo-o do toporemovendo-o do topo
PilhasPilhas:: :: PushPush
topo
k
m
x
topo
k
m
x
a
topo
k
m
x
a
b
push(a)
push(b)
PilhasPilhas:: :: PopPop
k
m
x
topo
topo
k
m
x
topo
k
m
x
aa
b
pop(b)
pop(a)
PilhasPilhas:: Operações básicas:: Operações básicas
Criar uma estrutura de pilha;Criar uma estrutura de pilha;
Inserir um elemento no topo (push);Inserir um elemento no topo (push);
Remover o elemento do topo (pop);Remover o elemento do topo (pop);
Verificar se a pilha está vazia;Verificar se a pilha está vazia;
Verificar se a pilha está cheia(se pilha Verificar se a pilha está cheia(se pilha estática)estática)
Liberar a estrutura de pilhaLiberar a estrutura de pilha
PilhasPilhas:: Implementação de pilha usando :: Implementação de pilha usando alocação dinâmicaalocação dinâmica
typedef struct noh TNo;struct noh { int info; TNo* prox;};
typedef struct pilha TPilha;struct pilha {
TNo* topo;};
PilhasPilhas:: Criar uma estrutura de pilha:: Criar uma estrutura de pilha
Mostrar a implementaçãoMostrar a implementação
PilhasPilhas:: Inserir o elemento do topo - :: Inserir o elemento do topo - push()push()
Mostrar a implementaçãoMostrar a implementação
PilhasPilhas:: Remover o elemento do topo - :: Remover o elemento do topo - pop()pop()
Mostrar a implementaçãoMostrar a implementação
PilhasPilhas:: Verificar se a pilha está vazia:: Verificar se a pilha está vazia
Mostrar a implementaçãoMostrar a implementação
PilhasPilhas:: Liberar a estrutura de pilha:: Liberar a estrutura de pilha
174
Mostrar a implementaçãoMostrar a implementação
QuestõesQuestões
FilasFilas
São São listas lineares listas lineares que adotam a política que adotam a política FIFOFIFO (First (First In First Out – o primeiro que entra é o primeiro que In First Out – o primeiro que entra é o primeiro que sai) para a manipulação de elementos.sai) para a manipulação de elementos.
As inserções são feitas no final da fila.As inserções são feitas no final da fila.
As remoções são feitas no início da fila.As remoções são feitas no início da fila.
A consulta na fila é feita desenfileirando elemento a A consulta na fila é feita desenfileirando elemento a elemento até encontrar o elemento desejado ou elemento até encontrar o elemento desejado ou chegar ao final da fila.chegar ao final da fila.
FilasFilas:: Aplicações:: Aplicações
Alocação de recursos para impressão de Alocação de recursos para impressão de documentos em uma impressora (impressão documentos em uma impressora (impressão de documentos).de documentos).
Atendimento de processos requisitados ao Atendimento de processos requisitados ao um sistema operacional(Software Básico).um sistema operacional(Software Básico).
Ordenação do encaminhamento dos pacotes Ordenação do encaminhamento dos pacotes em um roteador(redes de computadores).em um roteador(redes de computadores).
Buffer para gravação de dados em Buffer para gravação de dados em mídia(Computação Pessoal).mídia(Computação Pessoal).
FilasFilas:: Aplicações:: Aplicações
fila para pouso
fila para decolagem
Filas de tamanho variávelFilas de tamanho variável:: Inserção:: Inserção
B B
A A
X X
MM
K K
XX
MM
KK
A A
X X
MM
K K
AA
BB
Filas de tamanho variávelFilas de tamanho variável:: Remoção:: Remoção
B B
A A
X X
MM
K K
B B
A A
X X
B B
A A
X X
MM
kk
mm
Filas de tamanho fixoFilas de tamanho fixo
X X
MM
K K
A A
X X
MM
B B
A A
X X
AA KK
BB MM
FilasFilas:: Operações básicas:: Operações básicas
CriaçãoCriação
DestruiçãoDestruição
Inserção de um elementoInserção de um elemento
Remoção de um elementoRemoção de um elemento
Localização de um elemento para consulta ou Localização de um elemento para consulta ou alteração alteração
FilasFilas:: Criação de uma fila:: Criação de uma fila
typedef struct no TNo; struct no { int info; TNo* prox;};
typedef struct fila TFila; struct fila { TNo* cabeca; TNo* fim; };
FilasFilas:: Inserção de um elemento:: Inserção de um elemento
Ver códigoVer código
FilasFilas:: Remoção de um elemento:: Remoção de um elemento
175
Ver códigoVer código
Recommended