Algoritmos e Estruturas de Dados
Pilhas e Filas
Prof. Me. Claudio Benossi
[email protected]
Pilhas e Filas
Pilhas e filas são casos especiais das listas
encadeadas.
Ambas possuem regras rigorosas para acessar
os dados armazenados nelas.
As operações de recuperação de dados são
destrutivas, ou seja, para se alcançar dados
intermediários a tais estruturas, é necessário
destruir sequencialmente os dados anteriores.
Pilhas
 É uma das estruturas de dados mais simples
 É a estrutura de dados mais utilizada em programação,
sendo inclusive implementada diretamente pelo
hardware da maioria das máquinas modernas.
 A idéia fundamental da pilha é que todo o acesso a seus
elementos é feito através do seu topo.
 Assim, quando um elemento novo é introduzido na
pilha, passa a ser o elemento do topo, e o único
elemento que pode ser removido da pilha é o do topo.
Pilhas
:: Aplicações
Verificação de parênteses.
Retirada de vagões de um trem.
Retirada de mercadorias em um caminhão de
entregas.
Conversão de um número na base 10 para outra
base numérica.
Pilhas
Os elementos da pilha são retirados na ordem
inversa à ordem em que foram introduzidos: o
primeiro que sai é o último que entrou (LIFO –
last in, first out).
Existem duas operações básicas que devem ser
implementadas numa estrutura de pilha:
 operação para empilhar (push) um novo elemento,
inserindo-o no topo,
 operação para desempilhar (pop) um elemento,
removendo-o do topo
Pilhas
:: Push
push(b)
push(a)
b
a
topo
x
m
k
Pilhas
:: Push
topo
topo
topo
b
a
a
x
x
x
m
m
m
k
push(a)
k
push(b)
k
Pilhas
:: Pop
pop(b)
pop(a)
topo
b
a
x
m
k
Pilhas
:: Pop
topo
b
a
topo
a
x
x
m
m
k
pop(b)
k
topo
x
m
pop(a)
k
Pilhas
:: Implementação de pilha usando vetor
Supondo a pilha está armazenada em um vetor
pilha[0..n-1].
Considerando que os elementos são inteiros
(isso é só um exemplo, os elementos de pilha
poderiam ser quaisquer outros objetos).
A parte do vetor ocupada pela pilha será:
0
t
pilha[0..n-1]
n-1
Pilhas
:: Implementação de pilha usando vetor
#define MAX 50
struct pilha {
int n;
int vet[MAX];
} tipoPilha;
172
173
Pilhas
:: Implementação de pilha usando estruturas
typedef struct noh {
float
info;
struct no
*prox;
} tipoNo;
struct pilha {
tipoNo* topo;
} tipoPilha;
Pilhas
:: Operações básicas
Criar uma estrutura de pilha;
Inserir um elemento no topo (push);
Remover o elemento do topo (pop);
Verificar se a pilha está vazia;
Liberar a estrutura de pilha
Pilhas
:: Criar uma estrutura de pilha
tipoPilha* criar(void)
{
tipoPilha *p;
p = (tipoPilha*) malloc(sizeof(tipoPilha));
p->topo = NULL;
return p;
}
Pilhas
:: Inserir o elemento do topo - push()
tipoPilha push(tipoPilha *p, float v)
{
tipoNo* aux;
aux = (tipoNo) malloc(sizeof(tipoNo));
aux -> info = v;
aux -> prox = p->topo;
return aux;
}
Pilhas
:: Remover o elemento do topo - pop()
void pop(tipoPilha *p)
{
float v;
tipoNo* aux;
if (vazia(p))
{
printf(“Pilha vazia.”);
exit(1); /*aborta o programa*/
}
v
= p->topo->info;
aux = p->prox;
free(p);
printf(“Retirou o elemento %d”, v);
}
Pilhas
:: Verificar se a pilha está vazia
int vazia(tipoPilha *p)
{
return (p->topo == NULL);
}
Pilhas
:: Liberar a estrutura de pilha
void libera(tipoPilha *p)
{
tipoNo* q = p->topo;
while (q != NULL)
{
tipoNo *t = q->prox;
free(q);
q = t;
}
free(p);
}
174
Filas
 São listas lineares que adotam a política FIFO (First In
First Out – o primeiro que entra é o primeiro que sai)
para a manipulação de elementos.
 As inserções são feitas no final da fila.
 As remoções são feitas no início da fila.
 A consulta na fila é feita desenfileirando elemento a
elemento até encontrar o elemento desejado ou chegar
ao final da fila.
Filas
:: Aplicações
Alocação de recursos para impressão de
documentos em uma impressora (spooler de
impressão).
Atendimento de processos requisitados ao um
sistema operacional.
Ordenação do encaminhamento dos pacotes em
um roteador.
Buffer para gravação de dados em mídia.
Filas
:: Aplicações
fila para pouso
fila para decolagem
Filas de tamanho variável
:: Inserção
x
m
k
a
a
x
m
k
b
b
a
x
m
k
Filas de tamanho variável
:: Remoção
b
a
x
m
k
m
k
m
k
k
a
x
m
x
Filas de tamanho fixo
x
m
k
a
a
x
m
k
b
b
a
x
m
Filas
:: Estrutura de uma fila
Filas
:: Operações básicas
 Criação
 Destruição
 Inserção de um elemento
 Remoção de um elemento
 Localização de um elemento para consulta ou alteração
 Ordenação de uma lista
 Intercalação de duas listas
 Concatenação de duas listas
 Divisão de uma lista em duas
Filas
:: Criação de uma fila
typedef struct {
int info;
/* outros componentes*/
} tipoItem;
typedef struct no {
tipoItem item;
struct no *prox;
} tipoNo;
typedef struct {
tipoNoh frente;
tipoNoh tras;
} tipoFila;
Filas
:: Inserção de um elemento
void ffvazia(tipoFila *fila) {
fila->frente = (tipoNo) malloc(sizeof(tipoNo));
fila->tras = fila->frente;
fila->frente->prox = NULL;
}
int vazia(tipoFila fila) {
return (fila.frente == fila.tras);
}
void enfileira(tipoItem x, tipoFila *fila) {
fila->tras->prox = (tipoNo) malloc(sizeof(tipoNo));
fila->tras
= fila->tras->prox;
fila->tras->item = x;
fila->tras->prox = NULL;
}
Filas
:: Remoção de um elemento
void desenfileira(tipoFila *fila) {
ptr p;
if (vazia(*fila))
{
printf("Erro: Fila vazia.\n");
return;
}
p
= fila->frente;
fila->frente = fila->frente->prox;
free(p);
printf("Item da fila excluido com sucesso.");
getch();
}
175
Questões