Filas e Pilhas

Prévia do material em texto

Aula
Estrutura de dados
Pilhas/Filas
Prof. Cenez Araújo de Rezende
Unifor
Universidade de Fortaleza
Fortaleza/CE, Brasil
 
Agenda
- Pilhas estáticas
- Pilhas dinâmicas
- Filas Estáticas
- Filas Dinâmicas
 
Pilhas estáticas
Aula
 4
Estrutura de dados
Pilhas estáticas
● Pilha é uma estrutura linear:
– inserções ocorrem no topo da pilha;
– exclusões ocorrem no topo da pilha;
– Pilha estática: arranjo de elementos de tamanho 
predefinidos;
– Controla-se a posição dos elementos que está no 
topo da pilha;
 5
Estrutura de dados
Pilhas estáticas
● Pilha é uma estrutura linear:
– Temos um campo para indicar a posição do 
elemento que está no topo;
– Exemplo
● A: [10, 8, 13, ?, ?, ?]
– topo: 2
● A: [10, 8, 13, 7, ?, ?]
– topo: 3
 6
Estrutura de dados
Pilhas estáticas
● Inicializar a estrutura: 
– topo = -1
● Retornar a quantidade de elementos válidos
– topo+1
● Exibir os elementos da estrutura
– Percorre elementos e manda imprimir a chave
● Inserir elementos: push
– passar o registro a ser inserido
● se não cheia, insere
● Excluir elementos: pop
– se há elemento, exclui/retorna o elemento do topo; topo--;
● Reinicializar a estrutura: topo = -1
 7
Estrutura de dados
Pilhas estáticas
#include <stdio.h>
#define MAX 8
#define true 1
#define false 0
typedef int bool;
typedef int KEY;
typedef struct {
KEY chave;
} DATA;
typedef struct {
DATA A[MAX];
int topo;
} PILHA;
 8
Estrutura de dados
Pilhas estáticasvoid inicializar(PILHA* p) {
p->topo = -1;
}
void reinicializar(PILHA* p) {
p->topo = -1;
}
int size(PILHA* p) {
return p->topo + 1;
}
void print(PILHA* p){
printf("Pilha <--: ");
int i;
for (i=p->topo; i>=0; i--)
printf("%i ", p->A[i].chave);
printf("\n");
}
 9
Estrutura de dados
Pilhas estáticas
bool push(PILHA* p, DATA data){
if (p->topo >= MAX-1) return false;
p->topo = p->topo+1;
p->A[p->topo] = data;
return true;
}
bool pop(PILHA* p, DATA* data){
if (p->topo == -1) return false;
*data = p->A[p->topo];
p->topo = p->topo-1;
return true;
}
 10
Estrutura de dados
Pilhas estáticas
int main() {
DATA e, d1, d2, d3, d4, d5, d6, d7, d8;
PILHA p;
inicializar(&p);
d1.chave = 1; d2.chave = 2; 
 d3.chave = 3; d4.chave = 4; 
d5.chave = 5; d6.chave = 6; 
 d7.chave = 7; d8.chave = 8;
push(&p, d1); push(&p, d2); ….
 pop(&p, &e);
 return 0;
}
 
Pilhas dinâmicas
Aula
 12
Estrutura de dados
Pilhas dinâmicas
● Pilha dinâmica
– Alocamos e desalocamos a memória sob 
demanda para elementos;
– Vantagem: otimização de memória
● Evita alocação de memória que não é 
usanda;
– Cada elemento indicará quem é seu sucessor. 
Ou seja, o elemento que está abaixo dele na 
pilha
– Controlar o endereço do elemento que está no 
topo;
 13
Estrutura de dados
Pilhas dinâmicas
● Princípio (Ideia)
8
NULL
3420
6
3060
3020
10
3420
3060
topo
3020
 14
Estrutura de dados
Pilhas dinâmicas
● Inserir elemento na pilha
8
NULL
3420
9
3020
3290
6
3060
3020
10
3420
3060
topo
3290
 15
Estrutura de dados
Pilhas dinâmicas
● Excluir elemento da pilha
8
NULL
3420
6
3060
3020
10
3420
3060
topo
3020
 16
Estrutura de dados
Pilhas dinâmicas
● Implementação 
– Modelagem
#define true 1
#define false 0
typedef int bool;
typedef int KEY;
typedef struct {
KEY chave;
} DATA;
typedef struct aux {
DATA data;
struct aux* prox;
} ELEMENTO, *NODE;
typedef struct {
NODE topo;
} PILHA;
 17
Estrutura de dados
Pilhas dinâmicas
● Implementação 
– Inicializar a estrutura
● Acertar o topo, colocando NULL nele
● topo=NULL;
void inicializar(PILHA* p){
p->topo = NULL;
}
 18
Estrutura de dados
Pilhas dinâmicas
● Implementação 
– Retornar a quantidade de elementos válidos
● Precisamos iterar todos os elementos para 
descobrir
int tamanho(PILHA* p){
NODE fim = p->topo;
int tam = 0;
while (fim != NULL) {
tam++;
fim = fim->prox;
}
return tam;
}
 19
Estrutura de dados
Pilhas dinâmicas
● Implementação 
– Exibir os elementos da estrutura
● Percorrer cada elemento e imprimir chave
void print(PILHA* p){
NODE fim = p->topo;
printf("Pilha: ");
while (fim != NULL) {
printf("%i ", fim->data.chave);
fim = fim->prox;
}
printf("\n");
}
 20
Estrutura de dados
Pilhas dinâmicas
● Implementação
– Inserir elementos (push)
● passar registro para alocação;
● Elemento será inserido “acima” do elemento 
que está no topo atualmente;
● Novo elemento apontará para o elemento que 
estava no topo;
 21
Estrutura de dados
Pilhas dinâmicas
● Implementação
– Inserir elementos (push)
bool push(PILHA* p, DATA data){
NODE novo = (NODE) malloc(sizeof(ELEMENTO));
novo->data = data;
novo->prox = p→topo;//prox aponta quem estava no topo
p->topo = novo;
return true;
}
 22
Estrutura de dados
Pilhas dinâmicas
● Implementação
– Excluir elementos (pop)
● Verificar se a pilha está vazia
● copiar o elemento do topo para a memória 
passada pelo usuário
● O elemento topo aponta para o "topo-1" 
elemento bool pop(PILHA* p, DATA* data){
if(p->topo == NULL) return false;
*data = p->topo->data;
NODE apagar = p->topo;
p->topo = p->topo->prox;
free(apagar);
return true;
}
 23
Estrutura de dados
Pilhas dinâmicas
● Implementação
– Reinicializar a estrutura
● apagar todos os elementos válidos
● colocar NULL no campo topo
void reinicializar(PILHA* p){
NODE apagar;
NODE posicao = p->topo;
while (posicao != NULL) {
apagar = posicao;
posicao = posicao->prox;
free(apagar);
}
p->topo = NULL;
}
 
Filas estáticas
Aula
 25
Estrutura de dados
Filas estáticas
● Fila
– Fila de banco, supermercado, loteria, estádio, 
cinemas
– Entra no final, mas atende-se o primeiro
● Estrutura linear na computação
– Mesma lógica fila de pessoas
– Inserções no final
– Exclusões no início
 26
Estrutura de dados
Filas estáticas
● Fila estática: Ideia
– Arranjo de elementos com tamanho 
predefinido;
– Campo indicando a posição do primeiro
– Campo indicando o número de elementos
?? 9 710A
inicio=2
nroElem=3
 27
Estrutura de dados
Filas estáticas
● Fila estática: Ideia
– Arranjo de elementos com tamanho 
predefinido;
– Campo indicando a posição do primeiro
– Campo indicando o número de elementos
?13 9 710A
inicio=2
nroElem=4
 28
Estrutura de dados
Filas estáticas
● Implementação
– inicializar a estrutura
● Acertar variáveis "nroElem" (não há elementos, 
por exemplo 0)
● Acertar variável "inicio" (por exemplo 0)
– Quantidade de elementos válidos: "nroElem"
– Exibir os elementos da estrutura
● percorrer/iterar todos
● abstração circular
● após o elemento da última posíção (MAX-1) está 
o elemento da posição 0
 29
Estrutura de dados
Filas estáticas
● Implementação
– push no fim
● Inserir como último elemento da fila, se não 
cheia, de forma circular
● Se cheia, não há como inserir
– pop no início
● Se não vazia, copiar o elemento para o 
endereço passado pelo usuário
● Acertar "nroElem e inicio"
– reinicializar estrutura
● mesmo comando da inicialização
 30
Estrutura de dados
Filas estáticas
#include <stdio.h>
#define MAX 5
#define true 1
#define false 0
typedef int bool;
typedef int KEY;
typedef struct {
KEY chave;
} DATA;
typedef struct {
DATA A[MAX];
int inicio;
int nroElem;
} FILA;
 31
Estrutura de dados
Filas estáticas
void inicializar(FILA* f){
f->inicio = 0;
f->nroElem = 0;
}
int size(FILA* f) {
return f->nroElem;
}
 32
Estruturade dados
Filas estáticas
void print(FILA* f) {
printf("Fila: [");
int i = f->inicio;
int temp;
for (temp=0; temp< f->nroElem; temp++) {
printf("%i ", f->A[i].chave);
i = (i + 1) % MAX;
}
printf("]\n");
}
 33
Estrutura de dados
Filas estáticas
bool push(FILA* f, DATA data) {
if (f->nroElem >= MAX) return false;
int posicao = (f->inicio + f->nroElem) % MAX;
f->A[posicao] = data;
f->nroElem++;
return true;
}
bool pop(FILA* f, DATA* data) {
if (f->nroElem==0) return false;
*data = f->A[f->inicio];
f->inicio = (f->inicio+1) % MAX;
f->nroElem--;
return true;
}
 34
Estrutura de dados
Filas estáticas
void reinicializar(FILA* f){
f->inicio = 0;
f->nroElem = 0;
}
 35
Estrutura de dados
Observações de código c
//NODEEIROS ENDERECOS
int *p;
int i = 8;
p = &i;
*p = 80;
 
 p aponta para i, portanto p==&i
*p é o valor do endereço de memória apontado
 &p é o endereço de memória do ponteiro
 p->atributo é um atalho para (*p).atritubo
 
Filas dinâmicas
Aula
 37
Estrutura de dados
Filas dinâmicas
● Fila dinâmica
– Alocamos e desalocamos a memória sob 
demanda para elementos;
– Vantagem: otimização de memória
● Evita alocação de memória que não é 
usanda;
– Cada elemento indicará quem é seu sucessor, 
quem é o próximo na fila
– Controlamos os endereços dos elementos que 
estão no início e fim da fila.
 38
Estrutura de dados
Filas dinâmicas
● Princípio (Ideia)
8
NULL
3420
6
3060
3020
10
3420
3060inicio
3020
fim
3420
prox
Legenda
Ponteiro prox
typedef struct aux {
DATA data;
struct aux* prox;
} ELEMENTO, 
*NODE;
typedef struct {
NODE inicio;
NODE fim;
} FILA;
 39
Estrutura de dados
Filas dinâmicas
● Inserir elemento na fila
8
3333
3420
6
3060
3020
10
3420
3060inicio
3020
fim
3333
prox
Legenda
Ponteiro prox
9
NULL
3333
typedef struct aux {
DATA data;
struct aux* prox;
} ELEMENTO, *NODE;
typedef struct {
NODE inicio;
NODE fim;
} FILA;
 40
Estrutura de dados
Filas dinâmicas
● Excluir elemento da fila
8
3333
3420
10
3420
3060inicio
3060
fim
3333
prox
Legenda
Ponteiro prox
9
NULL
3333
typedef struct aux {
DATA data;
struct aux* prox;
} ELEMENTO, *NODE;
typedef struct {
NODE inicio;
NODE fim;
} FILA;
 41
Estrutura de dados
Filas dinâmicas
● Implementação 
– Inicializar a estrutura
● Acertar os valores inicio e fim, colocando 
NULL neles
– Retornar a quantidade de elementos válidos
● Precisamos iterar todos os elementos, até 
último elemento é NULL
– Exibir os elementos da estrutura
● Percorrer/iterar cada elemento e imprimir 
chave
 42
Estrutura de dados
Filas dinâmicas
● Implementação
– Inserir elementos (push)
● passar registro para alocação;
● Alocar memória para novo elemento;
● Elemento será inserido no fim da fila, e o 
penúltimo agora apontará para ele. Além 
disso, fim também apontará para ele;
● Novo elemento apontará para NULL;
● Contudo, se a fila estiver vazia, inicio e fim 
apontarão para novo elemento.
 43
Estrutura de dados
Filas dinâmicas
● Implementação
– Excluir elementos (pop)
● Verificar se a fila está vazia
● copiar o elemento do inicio para a memória 
passada como parâmetro pelo usuário
● O elemento inicio aponta para o "próximo" 
elemento do que está sendo excluído.
● Excluir elemento. Se fila vazia: fazer fim=NULL
– Reinicializar a estrutura
● apagar todos os elementos válidos
● colocar NULL nos campos inicio e fim
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43