AED Aula 07 Pilhas e Filas

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

ALGORITMO E ESTRUTURA DE DADOS 
FACULDADE DE CIÊNCIAS & TECNOLOGIA 
Pilhas e Filas 
• Pilhas e filas são casos especiais das listas 
ligadas. 
• 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 e Filas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
2 
• É 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 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
3 
• Verificação de parênteses. 
 
• Retirada de mercadorias em um caminhão de 
entregas. 
 
• Conversão de um número na base 10 para outra 
base numérica. 
 
Pilhas - Aplicações 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
4 
• 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 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
5 
 
Pilhas: Push 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
6 
topo 
k 
m 
x 
topo 
k 
m 
x 
a 
topo 
k 
m 
x 
a 
b 
push(a) push(b) 
 
Pilhas: Implementação 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
7 
typedef struct no { 
 float info; 
 struct no *prox; 
} No; 
 
struct pilha { 
 No* topo; 
} Pilha; 
• Criar uma estrutura Pilha 
 
 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: Operações básicas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
8 
 Criar uma pilha vazia 
Pilhas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
9 
Pilha* criar(void) 
{ 
Pilha *p; 
p = (Pilha*) malloc(sizeof(Pilha)); 
p->topo = NULL; 
return p; 
} 
 Inserir o elemento no topo da pilha 
 
 
Pilhas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
10 
Pilha push(Pilha *p, float v) 
{ 
No* aux; 
aux = (No*) malloc(sizeof(No)); 
aux -> info = v; 
aux -> prox = p->topo; 
return aux; 
} 
 Remover um elemento do topo – pop() 
Pilhas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
11 
void pop(Pilha *p) 
{ 
Int v; 
No* aux; 
if (vazia(p)) 
{ 
 printf(“Pilha vazia.”); 
 exit(1); /*aborta o programa*/ 
} 
aux = p->topo; 
v = aux->info; 
p->topo = p->topo->prox; 
free(aux); 
printf(“Retirou o elemento %d”, v); 
} 
 Verificar se a pilha está vazia 
Pilhas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
12 
int vazia(Pilha *p) 
{ 
return (p->topo == NULL); 
} 
 Eliminar todos os elementos da pilha 
Pilhas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
13 
void libera(Pilha *p){ 
No* q = p->topo; 
while (q != NULL) { 
 No *t = q; 
 q=q->prox; 
 free(t); 
} 
p->topo=NULL; 
} 
 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 reiranto elemento a 
elemento até encontrar o elemento desejado ou 
chegar ao final da fila 
Filas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
14 
 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 
router. 
 Buffer para gravação de dados em mídia. 
Filas- Aplicações 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
15 
 
Filas: Aplicações 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
16 
 
Filas: Inserção 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
17 
b a x m k 
x m k 
a x m k 
a 
b 
 Criação 
 Destruição 
 Inserção de um elemento 
 Remoção de um elemento 
 Localização de um elemento para consulta ou 
alteração 
Filas: Operações básicas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
18 
 Criação da estrutura fila 
Filas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
19 
typedef struct { 
 int info; 
 /* outros componentes*/ 
} tipoItem; 
 
typedef struct no { 
 tipoItem item; 
 struct no *prox; 
} No; 
 
typedef struct { 
No ini; 
No fim; 
} Fila; 
 Criação de uma fila vazia 
Filas 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
20 
Fila * ffvazia() { 
 fila f = (Fila*) malloc(sizeof(Fila)); 
 f->inicio= NULL; 
 f->fim= NULL; 
 return f; 
} 
 
int vazia(Fila fila) { 
 return (fila.frente== NULL); 
} 
Filas: Inserção 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
21 
 
void inserir(int x, Fila *fila) { 
 No* novo = (No*) malloc(sizeof(No)); 
 
 novo ->item = x; 
 novo->prox = NULL; 
 
 if(vazia(fila)){ 
 fila->ini=novo; 
 } 
 else 
 fila->fim->prox=novo; 
 fila->fim = novo; 
} 
Filas: Remoção 
.:FC&T:. :. Algoritmo e Estrutura de Dados 
22 
void remover(Fila *fila) { 
 No* 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.\n"); 
}