Aula 05 Pilhas CONCEITOS e IMPLEMENTAÇÕES (1)

Prévia do material em texto

Estrutura de Dados I
Prof. Leandro Melo
CC / 2024.1
Aula 5: Pilhas e Fila
Objetivos
Aula 5: Pilhas
• Pilhas - conceito
• Pilha Sequencial
• Pilha Encadeada
• Implementações
2
3
Pilhas (Stack)
 Definição
 Pilhas são listas onde a inserção de um novo item ou a 
remoção de um item já existente se dá em uma única 
extremidade, no topo.
 É uma lista onde as operações de inserção e remoção 
são efetuadas apenas no final da lista
 LIFO (last in first out).
4
Pilhas (Stack)
 Ilustração:
Topo
Base
5
Pilhas
 Operações básicas:
empilhar (push) um novo elemento, inserindo-o 
no topo.
desempilhar (pop) um elemento, removendo-o do 
topo.
6
Pilhas
 Exemplo:
7
Pilhas
 Exemplos:
 Uma rua sem saída e estreita, onde apenas um carro passa por vez
 O último carro que entrar será o primeiro a sair
 Não podemos retirar qualquer carro
 Não podemos inserir um carro de tal forma que ele não seja o ultimo
 Uma pilha de pratos em um restaurante
 Pilha de execução na linguagem C
 Variáveis locais são empilhadas na pilha
 Ao término da função, as variáveis são desempilhadas
 Avaliação de expressões aritméticas
8
Pilhas
 Outro exemplo de uso prático:
 Recursividade ou Chamadas de procedimentos. Exemplo:
e1
e2
e1
e3
TOPO
TOPO
TOPO
TOPO
e2
e1
9
Pilhas
 Quando o procedimento A1 é executado, ele efetua uma chamada a A2, 
que deve carregar consigo o endereço de retorno e1. Ao término de A2, o 
processamento deve retornar ao A1, no devido endereço. Situação 
idêntica ocorre em A2 e A3.
 Assim, quando um procedimento termina, é o seu endereço de retorno 
que deve ser consultado. Portanto, há uma lista implícita de endereços 
(e0, e1, e2, e3) que deve ser manipulada como uma pilha pelo sistema, 
onde e0 é o endereço de retorno de A1.
 No caso de processamento recursivo - por exemplo uma chamada a A2 
dentro de A4 - o gerenciamento da lista como uma pilha resolve 
automaticamente a obtenção dos endereços de retorno na ordem 
apropriada (e0, e1, e2, e3, e4).
10
Pilhas
 Exemplos:
 Notação para expressões aritméticas:
 Infixa:
• operador entre os operandos.
• (1 – 2) * (4 + 5)
 Pósfixa:
• operador após os operandos.
• 1 2 – 4 5 + *
 Préfixa:
• operador antes dos operandos.
• * - 1 2 + 4 5
11
Pilhas
 A calculadora HP, por exemplo, utiliza a notação pósfixa.
 A avaliação de expressões aritméticas pósfixadas:
 cada operando é empilhado numa pilha de valores.
 quando se encontra um operador:
 Desempilha-se o número apropriado de operandos (dois para 
operandos binários e um para operadores unários).
 realiza-se a operação devida.
 empilha-se o resultado.
 Exemplo: avaliação da expressão (1 – 2) * (4 + 5) ou
1 2 – 4 5 + *
12
Pilhas
 Exemplo: avaliação da expressão (1 – 2) * (4 + 5) ou
1 2 – 4 5 + *
13
Pilhas
Expressão posfixa 3 9 * 8 2 / +
14
Pilhas
ESCREVA AS EXPRESSÕES NA FORMA PÓS-FIXADA
 (4 + 5) * 3 + (2 / 1)
 (4 + (3 / 1) * 2) – 5 * 3
 4 + (3 / 1) * (2 – 5) * 3
 (((4 + 3) / 1) * 2) – (5 * 3)
15
Pilhas [[()()]()]
ANALISE O CÓDIGO E DIGA O QUE ELE FAZ
int bemFormada (char s[]) 
{
criapilha ();
for (int i = 0; s[i] != '\0'; ++i) {
char c;
switch (s[i]) {
case ')': if (pilhavazia ()) return 0;
c = desempilha ();
if (c != '(') return 0;
break;
case ']': if (pilhavazia ()) return 0;
c = desempilha ();
if (c != '[') return 0;
break;
default: empilha (s[i]);
}
}
return pilhavazia ();
}
16
Pilhas
EXERCÍCIOS DE FIXAÇÃO
Neste ponto você deve realizar os
exercícios propostos no arquivo
“Aula 05 Pilhas EXERCÍCIOS”.
17
COMO PODEMOS IMPLEMENTAR UMA 
PILHA???
 Como lista Sequencial ou Encadeada?
Pilhas
18
Pilhas
 Implementação de Pilhas
 Como lista Sequencial ou Encadeada?
– No caso geral de listas ordenadas, a maior vantagem da alocação 
encadeada sobre a seqüencial - se a memória não for problema - é a 
eliminação de deslocamentos na inserção ou eliminação dos 
elementos. No caso das pilhas, essas operações de deslocamento não 
ocorrem.
– Portanto, podemos dizer que a alocação sequencial é mais vantajosa 
na maioria das vezes.
SÓ 
isso????
Pilha Sequencial
 O que precisaremos para implementar uma pilha 
sequencial?
 Um vetor de elementos
 Uma variável para controlar o topo
 Representação:
SIIIIMMM
M!!!!
Afinal, 
você que 
já 
dominou 
lista 
sequenci
al, 
agora é 
só 
repetir 

Pilha Sequencial
Precisamos 
desclocar os 
elementos na 
inserção e 
remoção?
Claro 
que não!
Pilhas
IMPLEMENTAÇÕES EM C e JAVA
•SEQUENCIAL
•ENCADEADA
21
22
Pilha Sequencial
 Operações:
 Criar uma pilha;
 Testar se a pilha está vazia;
 Testar se a pilha está cheia;
 Obter o elemento do topo (sem eliminar);
 Empilhar um novo elemento (push);
 Desempilhar o elemento do topo (pop).
 Exibir os elementos da pilha
Crie um Novo Projeto Java
• Crie um novo projeto Java chamado Pilha Sequencial;
• Crie a classe Principal contendo o método main;
• Dentro do método main, digite o seguinte código...
Classe Principal
Classe PilhaSequencial
• Crie mais uma classe no projeto. Chame-a de PilhaSequencial;
• NÃO ADICIONE O MÉTODO main!!!
A classe terá 2 variáveis de instância: 
• Um vetor de String para armazenar 100 posições, chamado “elementos”.
• Uma variável inteira para controlar o tamanho da pilha que vamos chamar de 
“topo”.
26
Pilha Sequencial
 Implementação:
27
Pilha Sequencial
 Implementação:
 Estrutura:
// Tipo base dos elementos da lista
typedef struct elementos {
char nome[50];
int num;
} t_elemento;
// Estrutura da pilha
typedef struct pilha {
t_elemento vetor[MAX];
int topo;
} t_pilha;
Aqui minha 
pilha vai 
guardar 
STRING
Aqui minha 
pilha vai 
guardar 
STRING e 
INTEIRO
28
Pilha Sequencial
 Implementação:
 Criação:
/**
* Cria uma nova pilha, aloca a sua regiao de memoria,
* inicializa o topo, e retorna a pilha criada.
* 
* @return Pilha inicializada
*/
t_pilha criar() {
t_pilha pilha;
pilha.topo = -1;
return pilha;
}
Essa 
função é o 
“construto
r” em C
Esse é o 
CONSTRUTOR do 
vetor
Inicialização 
do TOPO
29
Pilha Sequencial
 Implementação:
 Verificações:
/**
* Verifica se a pilha esta vazia ou nao.
* 
* @param pilha ponteiro para a pilha, a pilha ja deve ter sido inicializada
*
* @return Verdadeiro (1) se a pilha estiver vazia, ou falso (0) caso contrario.
*/
int isVazia(t_pilha * pilha) {
return (pilha->topo == -1);
}
30
Pilha Sequencial
 Implementação:
 Verificações:
/**
* Verifica se a pilha esta cheia ou nao.
* 
* @param pilha ponteiro para a pilha, a pilha ja deve ter sido inicializada
*
* @return Verdadeiro (1) se a pilha estiver cheia, ou falso (0) caso contrario.
*/
int isCheia(t_pilha * pilha) {
return (pilha->topo == MAX-1);
}
Por que a 
comparação 
é 
realizada 
com (length –
1) ?
OU com 
(MAX – 1) ?
31
Pilha Sequencial
 Implementação:
 Elemento do topo:
/**
* Obter o elemento do topo da pilha (sem eliminar)
* 
* @param pilha ponteiro para a pilha, a pilha ja deve ter sido inicializada
*
* @return o elemento desejado, caso a posicao seja invalida retorna vazio.
*/
t_elemento getElementoTopo(t_pilha * pilha)
{
t_elemento vazio = { "" } ;
if (isVazia(pilha))
return vazio; // erro
else
return pilha->vetor[pilha->topo];
}
Notem que o 
elemento NÃO é 
removido, apenas 
retornado para quem 
chamou a 
função/método
32
Pilha Sequencial
 Implementação:
 Desempilha:
/**
* Remove o elemento do topo da pilha (desempilhar), retornando o elemento removido
* 
* @param pilha ponteiro para a pilha, a pilha ja deve ter sido inicializada
*
* @return Uma copia do elemento do topo.
*/
t_elemento pop(t_pilha * pilha)
{
t_elemento vazio = { "" };
if (isVazia(pilha))
return vazio; // erro
else
return pilha->vetor[pilha->topo--];
}
33
Pilha Sequencial
 Implementação:
 Empilha (push):
/**
* Inserir um novo elemento no topo da pilha (empilhar)
* 
* @param pilhaponteiro para a pilha, a pilha ja deve ter sido inicializada
* @param dado elemento a ser inserido na pilha
*
* @return Falso(0) se a posição for invalida ou se a pilha estiver cheia, caso contrario, retorna Verdadeiro(1)
*/
int push(t_pilha *pilha, t_elemento valor)
{
if (isCheia(pilha))
return 0; // erro
pilha->vetor[++pilha->topo] = valor;
return 1; // sucesso
}
34
Pilha Sequencial
 Implementação:
 Exibir todos os elementos?
/**
* Exibir todos elementos da pilha
* 
* @param pilha ponteiro para a pilha, a pilha ja deve ter sido inicializada
*
*/
void exibirTudo(t_pilha *pilha)
{
}
35
Pilha Encadeada
 Implementação com nós ligados por meio de ponteiros
 As operações sob listas simplesmente encadeadas poderão 
ser tomadas como referência
 Como poderíamos adaptar uma lista simplesmente 
encadeada para uma pilha?
 Preciso modificar radicalmente a forma de programar de uma 
lista para uma pilha?
 Onde será o topo da pilha?
 No final?
 No inicio?
36
Pilha Encadeada
 Operações:
 Criar uma pilha;
 Testar se a pilha está vazia;
 Obter o elemento do topo (sem eliminar);
 Desempilhar o elemento do topo (pop).
 Empilhar um novo elemento (push);
 Exibir os elementos da pilha
 Algoritmos
37
Pilha Encadeada
 Implementação:
Estrutura:
// Tipo base dos elementos da pilha 
typedef struct elementos {
char nome[50];
char c; 
} t_elemento;
// Estrutura da pilha
typedef struct no {
t_elemento dado; // elemento contendo os dados
struct no * prox; // ponteiro para o proximo elemento
} t_no; // tipo da estrutura
// define t_pilha como sendo um outro nome para "t_no *"
typedef t_no * t_pilha;
38
Pilha Encadeada
 Implementação:
Criação:
/**
* Cria um novo no, aloca a sua regiao de memoria,
* inicializa o ponteiro prox, e retorna o ponteiro para a pilha criada.
* 
* @return No alocada e inicializada
*/
t_no * criaNo() {
t_no * no = (t_no*) malloc(sizeof(t_no));
// verifica se houve memoria suficiente para alocar
if (no)
no->prox = NULL;
return no;
}
39
Pilha Encadeada
 Implementação:
Verificações:
/**
* Verifica se a pilha esta vazia ou nao. Isto so acontece quando ela eh nula
* 
* @param pilha ponteiro para a pilha
*
* @return Verdadeiro (1) se a pilha estiver vazia, ou falso (0) caso contrario.
*/
int isVazia(t_pilha pilha) {
return (pilha == NULL);
}
40
Pilha Encadeada
 Implementação:
Elemento do topo:
/**
* Obter o elemento do topo da pilha (sem eliminar)
* 
* @param pilha ponteiro para a pilha, a pilha ja deve ter sido inicializada
*
* @return ponteiro para o elemento desejado, caso a posicao seja invalida retorna 0.
*/
t_elemento getElementoTopo(t_pilha pilha)
{
t_elemento valor = { "" };
if (isVazia(pilha))
return valor;
else
return pilha->dado;
}
41
Pilha Encadeada
 Desempilha (pop):
/**
* Remove o elemento do topo da pilha (desempilhar), retornando o elemento removido.
* 
* @param pilha ponteiro para a pilha, a pilha ja deve ter sido inicializada
*
* @return Falso(0) se a posicao for invalida ou se a pilha estiver cheia, caso contrario, retorna Verdadeiro(1)
*/
t_elemento pop(t_pilha *pilha)
{
t_no * aux;
t_elemento valor = { "" };
if (isVazia(*pilha))
return valor; // erro: pilha vazia
aux = *pilha;
valor = (*pilha)->dado;
*pilha = aux->prox;
free(aux); // libera o no que continha o dado do topo da pilha
return valor;
}
42
Pilha Encadeada
 Empilha (push):
/**
* Insere um novo elemento (dado) no topo da pilha (empilhar)
* 
* @param pilha ponteiro para a pilha
* @param dado elemento a ser inserido na pilha
*
* @return Falso(0) se a posição for invalida ou se a pilha estiver cheia, caso contrario, retorna Verdadeiro(1).
*/
int push(t_pilha *pilha, t_elemento dado)
{
t_no* novo;
novo = criaNo();
if (novo == NULL)
return 0; // erro: memoria insuficiente
novo->dado = dado;
novo->prox = *pilha;
*pilha = novo;
return 1; // sucesso
}
43
Pilha Encadeada
 Pilha Circular?
 Pilha Duplamente Encadeada?
 Faz sentido?
ATIVIDADE PARA CASA
Você está na entrada de um beco comprido, estreito e sem saída, no qual carros 
entram e saem em fila única, pois não há espaço lateral para dois carros. Neste beco 
cabem três carros. Escreva um algoritmo em C que simula as seguintes situações:
a) três carros entram no beco e seu algoritmo registra (guarda) as placas dos carros 
que entraram;
b) mostra a placa do terceiro carro que entrou;
c) três carros saem do beco e seu algoritmo mostra a placa de cada carro que saiu.
d) mostra quantos carros ficaram no beco
(*) Escolher a estrutura de dados que melhor se adequa a esta situação; implementar 
uma função para cada item (a e c); os itens b) e d) são executados no main() de seu 
algoritmo.
44
Pontos Abordados
• Conceito de Pilha
• Tipos Sequencial e Encadeada
• Implementação destas Pilhas
45
Objetivos
Aula 8: Filas
• Filas - conceito e utilização
• Fila Sequencial
• Fila Encadeada
• Fila Circular
• Implementações
46
47
Filas
 Definição
 Conjunto de itens onde as eliminações são feitas em 
uma extremidade (início da fila) e as inserções são 
realizadas na outra extremidade (final da fila).
 É uma lista linear em que a inserção é feita numa 
extremidade e a eliminação na outra.
48
Filas
 O que diferencia a fila da pilha?
 A Ordem de saída dos elementos!
 Pilha: LIFO (Last In, First Out)
 Fila: FIFO (First In, First Out)
 Lista?
 Idéia fundamental:
 Só podemos inserir um elemento no final da fila e só 
podemos retirar o elemento do início. 
49
Filas
 Analogia natural do conceito de uma fila
 Fila de um banco:
 Fila do cinema:
 Fila de atendimento:
 Quem primeiro entrar na fila, é o primeiro a ser 
atendido (a sair da fila).
Grupo de carros esperando sua vez para passar no 
pedágio
50
Filas
 Utilização na computação:
Gerenciador de impressão num ambiente multiusuário 
(impressora compartilhada)
 Tratar todas as requisições com a mesma prioridade e 
imprimir os documentos na ordem em que foram 
submetidos.
 Escalonamento de tarefas: fila de processos aguardando 
os recursos do sistema operacional.
 Fila de pacotes a serem transmitidos numa rede de 
computadores.
Multiplexação de vídeos.
51
Filas
 Ilustração:
InicioFinal
Inserir vermelho, laranja e azul
InicioFinal InicioFinal
Retirar dois elementos:
1
2
3
4
5
52
Filas
 Implementação de Filas:
Realizada a partir de uma lista com duas 
cabeças (ponteiros).
Lista Sequencial ou Encadeada ?
A implementação encadeada dinâmica 
torna mais simples as operações de inserção 
e remoção. Já a implementação seqüencial
é um pouco mais complexa (por que?), mas 
pode ser usada quando há previsão do 
tamanho máximo da fila.
53
Fila Sequencial
 O que precisaremos para montar a estrutura
de uma fila sequencial?
Um vetor de elementos
Um campo para controlar o início da fila
Outro campo para controlar o final da fila
54
Fila Sequencial
 Forma de uso:
55
Fila Sequencial
 Forma de uso (CONT.):
56
Fila Sequencial
 Problemas…
Existem cinco espaços livres na fila, mas 
nenhum outro elemento pode ser inserido
 Fila.final chegou à condição de limite (MAX -1)
Podemos chegar à situação absurda em que 
a fila está vazia, mas nenhum elemento
novo pode ser inserido.
Conclusão: A representação sequencial
descrita anteriormente não é adequada!
57
Fila Sequencial
 Solução?
Deslocar todos os elementos a cada remoção?
• Nao precisaria do índice do primeiro
elemento.
58
Fila Sequencial
 Consequência:
O método anterior é bastante ineficiente:
Cada operação envolve o deslocamento de 
cada elemento restante na fila
 Exemplo: Se uma fila contiver 1000 elementos, 
teria-se que deslocar 999 elementos para
remover um. Evidentemente seria um preço
muito alto a pagar
A operação envolve apenas a remoção de um 
único elemento. Para que envolver inúmeras
operações adicionais?
59
Fila Circular
 Solução:
Forçar finala usar o 
espaço liberado na 
frente
Para permitir a 
reutilização das posições 
já ocupadas, usa-se o 
conceito de Fila Circular
60
Fila Circular
 Fila cheia?
Quando o fim == (inicio-1) ou
Se o inicio for zero?
• Quando o fim == (MAX-1);
O ponteiro do fim não pode passar pelo do inicio;
61
Filas
 Implementação de uma fila sequencial
 Quais operações deverão ser implementadas?
 criarFila()
 isVazia()
 isCheia()
 inserir()
 remover()
 exibir()
 esvaziar()
62
Fila Sequencial
 Implementação:
 Estrutura:
// tamanho maximo da fila
#define MAX 5
// Tipo base dos elementos da fila 
typedef struct elementos {
char nome[50];
} t_elemento;
typedef struct fila {
t_elemento vetor[MAX]; // vetor que armazena a fila
int inicio; // posicao do primeiro elemento
int fim; // posicao do ultimo elemento
int quant_element; // numero de elementos da fila
} t_fila;
63
Fila Sequencial
 Implementação:
 Criação:
/**
* Cria uma nova fila, aloca a sua regiao de memoria,
* inicializa o inicio, fim e a quantidade de elementos.
* Por fim, retorna a fila criada.
*
* @return Fila inicializada
*/
t_fila criar()
{
t_fila fila;
fila.inicio = 0;
fila.fim = -1;
fila.quant_element = 0;
return fila;
}
64
Fila Sequencial
 Implementação:
 Verificações:
/**
* Verifica se a fila esta vazia ou nao.
*
* @param fila ponteiro para a fila, a fila ja deve ter sido inicializada
*
* @return Verdadeiro (1) se a fila estiver vazia, ou falso (0) caso contrario.
*/
int isVazia (t_fila * fila)
{
return (fila->quant_element == 0);
}
/**
* Verifica se a fila esta cheia ou nao.
*
* @param fila ponteiro para a fila, a fila ja deve ter sido inicializada
*
* @return Verdadeiro (1) se a fila estiver cheia, ou falso (0) caso contrario.
*/
int isCheia(t_fila * fila)
{
return (fila->quant_element == MAX);
}
65
Fila Sequencial
 Implementação:
 Inserir:
/**
* Insere um elemento (valor) no final da fila.
* 
* @param fila ponteiro para a fila, a fila ja deve ter sido inicializada
* @param valor elemento a ser inserido na fila
*
* @return Falso(0) se a fila estiver cheia, caso contrario, retorna Verdadeiro(1)
*/
int inserir (t_fila * fila, t_elemento valor)
{
if (isCheia(fila))
return 0;
(fila->quant_element)++;
fila->fim = (fila->fim + 1) % MAX;
fila->vetor[fila->fim] = valor;
return 1;
}
66
Fila Sequencial
 Implementação:
 Remover:
/**
* Remove um elemento do inicio da fila.
* 
* @param fila ponteiro para a fila, a fila ja deve ter sido inicializada
*
* @return o elemento removido.
*/
t_elemento remover(t_fila * fila)
{
t_elemento valor = { "" } ;
if (isVazia(fila))
return valor; // Erro: fila vazia
valor = fila->vetor[fila->inicio];
fila->vetor[fila->inicio].nome[0] = '\0';// zera, opcional
(fila->quant_element)--;
fila->inicio = (fila->inicio + 1) % MAX;
return valor;
}
67
Fila Sequencial
 Implementação:
 Exibição:
/**
* Exibe todos os elementos da fila
*
* @param fila ponteiro para a fila, a fila ja deve ter sido inicializada
*/
void exibir(t_fila * fila) {
int i;
if (isVazia(fila)) {
printf("Fila vazia\n");
return;
}
printf("\nExibindo fila:\n");
printf("inicio: %d\n", fila->inicio);
printf("fim: %d\n", fila->fim);
for (i=0 ; ivetor[i].nome);
}
}
68
Fila Sequencial
 Implementação:
 Exibição ordenada:
/**
* Exibe todos os elementos da fila
*
* @param fila ponteiro para a fila, a fila ja deve ter sido inicializada
*/
void mostraFila(t_fila * fila)
{
if (isVazia(fila)) {
printf("Fila vazia\n");
return;
}
for (i = fila->inicio; i != fila->fim + 1; i = (i + 1) % MAX)
printf("%d\t", fila->vetor[i]);
}
69
Fila Encadeada
 Implementação especial de uma lista
simplesmente encadeada;
 Para remover da fila, implementa-se uma
operação que retira sempre no início;
 Para inserir, implementa-se uma operação
que insere sempre no final;
70
Fila Encadeada
 Possíveis formas de Implementação:
 Lista simplesmente encadeada;
– Desvantagem: Para cada elemento inserido na fila, teremos que 
percorrer todos os nós até encontrar o último. Não é interessante!
 Lista simplesmente encadeada com dois ponteiros;
– Desvantagem: ter dois ponteiros.
 Lista simplesmente encadeada circular;
– Único ponteiro para o final da fila;
 Lista simplesmente encadeada com cabeça especial.
– Precisa-se de um único ponteiro para a cabeça especial, e, essa 
cabeça é que tem o ponteiro para o inicio e o fim.
 Lista duplamente encadeada?
71
Fila Encadeada
 Implementação:
 Lista duplamente encadeada com duas cabeças:
 Lista duplamente encadeada circular:
PRIM ULT
D
72
Fila Encadeada com Cabeça Especial
 Exemplo:
 Características
 Ponteiro para o primeiro nó;
 Ponteiro para o último nó;
 Informação sobre a quantidade de elementos da
lista.
73
Fila Encadeada com Cabeça Especial
 Implementação das operações:
criarFila()
isVazia()
inserir()
remover()
exibir()
esvaziar()
74
Fila Encadeada
 Implementação:
 Estrutura:
// Tipo base dos elementos da lista 
typedef struct elementos {
char nome[50];
} t_elemento;
typedef struct no {
t_elemento dado;
struct no * prox;
} t_no;
typedef struct fila {
t_no* inicio;
int quant_element;
t_no* final;
} t_fila;
75
Fila Encadeada
 Implementação:
 Criação:
/**
* Cria uma fila vazia, ou seja um no cabeca.
* inicializa os ponteiros ini e fim para NULL,
* e seta quant_element para zero.
* 
* @return no cabeca alocado e inicializado
*/
t_fila * criaCabeca ()
{
t_fila * fila = (t_fila*) malloc(sizeof(t_fila));
if (fila) {
fila->inicio = fila->final = NULL;
fila->quant_element=0;
}
return fila;
}
76
Fila Encadeada
 Implementação:
 Criar um nó:
/**
* Cria um novo no, aloca a sua regiao de memoria,
* inicializa o ponteiro prox, e retorna o ponteiro para a pilha criada.
* 
* @return No alocada e inicializada
*/
t_no * criaNo() {
t_no * no = (t_no*) malloc(sizeof(t_no));
// verifica se houve memoria suficiente para alocar
if (no)
no->prox = NULL;
return no;
}
77
Fila Encadeada
 Implementação:
 Verificações:
/**
* Verifica se a fila esta vazia ou nao. Isto so acontece quando ela eh nula
* 
* @param fila ponteiro para a fila
*
* @return Verdadeiro (1) se a fila estiver vazia, ou falso (0) caso contrario.
*/
int isVazia (t_fila * fila)
{
return (fila->quant_element == 0);
}
78
Fila Encadeada
 Implementação:
 Inserir:
/**
* Insere um elemento (valor) no fim da fila.
* 
* @param fila ponteiro para a fila
* @param valor elemento a ser inserido na fila
*
* @return Falso(0) se a fila estiver cheia, caso contrario, retorna Verdadeiro(1).
*/
int inserir (t_fila *fila, t_elemento valor) {
t_no *novo;
novo = criaNo();
if (novo == NULL)
return 0; // Erro: memoria insuficiente
novo->dado = valor;
if (isVazia(fila))
fila->inicio = novo;
else
(fila->final)->prox = novo;
fila->final = novo;
fila->quant_element++;
return 1;
}
79
Fila Encadeada
 Implementação:
 Remover:
/**
* Remove um elemento do inicio da fila.
* 
* @param fila ponteiro para a fila, a fila ja deve ter sido inicializada
*
* @return o elemento removido.
*/
t_elemento remover (t_fila *fila)
{
t_no *aux;
t_elemento valor = { "" } ;
if (isVazia(fila))
return valor; // Erro: fila vazia 
valor = (fila->inicio)->dado;
if (fila->inicio == fila->final)
fila->final = NULL;
aux = fila->inicio;
fila->inicio = (fila->inicio)->prox;
free(aux);
fila->quant_element--;
return valor;
}
Pontos Abordados
• Conceito de Fila
• Tipos Sequencial e Encadeada
• Implementação destas Filas
80
Estrutura de Dados I
Prof. Leandro Melo
CC / 2024.1
Aula 5: Pilhas e Fila