/39
1/45
MCTA028-15: Programação Estruturada
Aula 10: Filas e Pilhas (Prática)
Francisco de Assis Zampirolli e Wagner Tanaka Botelho
[email protected] /
[email protected] /
[email protected]Universidade Federal do ABC (UFABC)
Centro de Matemática, Computação e Cognição (CMCC)
2/46
Fila Sequencial Estática
3/46
Definindo o Tipo
Ex_1.c
4/46
Fila *fi;
qtd início fim
4 0 4
num 45 5 4 12
0 1 2 3 tamArray-1
5/46
Criando a Fila
6/46
qtd início fim
0 0 0
Fila *fi;
num
0 1 2 3 tamArray-1
7/46
Liberando a Fila
8/46
X
qtd início fim
0 0 0
Fila *fi;
num
0 1 2 3 tamArray-1
9/46
Tamanho e Fila Cheia/Vazia
10/46
qtd início fim
4 0 4 tam = fi->qtd;
qtd início fim
num 65 4 12 33
0 2 2 Fila Vazia:
0 1 2 3 tamArray-1 fi->qtd == 0
qtd início fim num
5 2 2 Fila Cheia: 0 1 2 3 tamArray-1
fi->qtd == tamArray
num 55 4 12 33 5
0 1 2 3 tamArray-1
11/46
Inserir e Remover um Elemento
A INSERÇÃO NA FILA É SEMPRE NO FINAL!!! 12/46
qtd início fim
insere_fila (pFila, 12); 3
2 0 32
fi->num[2]=12
fi->fim = 3
fi->qtd = 3 num 4 65 12
0 1 2 3 tamArray-1
A REMOÇÃO NA FILA É SEMPRE NO INÍCIO!!!
qtd início fim
remove_Fila (pFila); 23 1
0 3
fi->inicio = 1
fi->qtd-- = 2
num 4 65 12
O início da fila fica com um número. 0 1 2 3 tamArray-1
Entretanto, a posição é considerada
NÃO ocupada por elementos na fila.
13/46
Fila Dinâmica Encadeada
14/46
Definindo o Tipo
Ex_2.c 15/46
pro
numero
x
Fila *fi
inicio fim qtd=0
16/46
Criando a Fila
17/46
Fila *fi
inicio fim qtd=0
NULL
18/46
“Destruindo” e Tamanho da Fila
19/46
inicio fim qtd=2 fi
23 2 NULL
nó nó
inicio fim qtd=2 fi
23 2 NULL
20/46
Fila Cheia e Vazia
21/46
Fila cheia: apenas ocorrerá quando a chamada da função
malloc() retornar NULL.
Fila Vazia:
fi->inicio == NULL
fi inicio fim qtd=0
NULL
22/46
Inserindo e Removendo um Elemento na Fila
Como a inserção é no final da fila, o elemento a ser inserido obrigatoriamente 23/46
deve apontar para a constante NULL.
inicio fim qtd=2 fi
qtd=3
no no
23 2 12
NULL 12 NULL NULL
Remoção:
inicio fim qtd=2 fi
qtd=3
23 2 12 NULL
nó
24/46
Pilha Sequencial Estática
25/46
Definindo o Tipo
26/46
4 qtd
tamMax - 1
2
43
20
19 0
27/46
Criando a Pilha
28/46
Pilha *pi;
0 qtd
tamMax - 1
0
29/46
“Destruindo” a Pilha
30/46
Liberando a memória alocada para a estrutura que
representa a pilha.
Pilha *pi;
0 qtd
tamMax - 1
0
31/46
Tamanho e Pilha Cheia/Vazia
Para saber o tamanho da pilha, 2 qtd 32/46
basta retornar o valor de qtd.
tam = pi->qtd; tamMax - 1
Pilha Cheia: Pilha Vazia:
pi->qtd == tamMax pi->qtd == 0
13
tamMax qtd 0 qtd 5 0
9 tamMax - 1 tamMax - 1
88
4
12
13
5 0 0
33/46
Inserindo e Removendo na Pilha
34/46
234 qtd
insere_pilha(pPilha, 12);
pi->num[2] = 12 tamMax - 1
pi->qtd = 3
insere_pilha(pPilha, 77); 77
pi->num[3] = 77 12
pi->qtd = 4 13
5 0
43 qtd
remove_Pilha(pPilha);
pi->qtd = 3 tamMax - 1
O topo da pilha fica duplicado. 77
Entretanto, a posição é 12
considerada NÃO ocupada por 13
elementos na pilha. 5 0
35/46
Pilha Dinâmica Encadeada
36/46
Definindo o Tipo
37/46
pro
numero
x
Topo (*pi)
pro
numero
x
38/46
Criando a Pilha
39/46
Pilha *pi;
Topo
NULL
40/46
“Destruindo” e Tamanho da Pilha
41/46
Pilha *pi; Pilha *pi;
Topo cont = 3
21
0
Topo Percorre a pilha até o
valor do nó for
no 44 no
44 diferente de NULL
(fim da pilha).
no 76 no
76
2 no
2 no
no
NULL
NULL
42/46
Pilha Cheia/Vazia
43/46
Pilha Cheia: apenas ocorrerá quando a chamada da função
malloc() retornar NULL.
Pilha Não Vazia: Pilha Vazia:
Topo Pilha *pi; Topo Pilha *pi;
44
NULL
76
NULL
44/46
Inserindo e Removendo um Elemento na Pilha
45/46
Inserindo: Removendo:
Pilha *pi; no Topo Pilha *pi;
Topo 14
no
44
76
76
2
NULL 2
NULL
46/46
Referências
Slides do Prof. Luiz Rozante;
SALES, André Barros de; AMVAME-NZE, Georges. Linguagem C: roteiro de
experimentos para aulas práticas. 2016;
BACKES, André. Linguagem C Completa e Descomplicada. Editora Campus. 2013;
SCHILDT, Herbert. C Completo e Total. Makron Books. 1996;
DAMAS, Luís. Linguagem C. LTC Editora. 1999;
DEITEL, Paul e DEITEL, Harvey. C Como Programar. Pearson. 2011;
BACKES, André. Estrutura de Dados Descomplicada em Linguagem C. GEN LTC.
2016.
