UPE – Caruaru – Sistemas de Informação
Disciplina: Estrutura de Dados e Arquivo
Prof.: Paulemir G. Campos
Pilhas e Filas usando Alocação
Estática e Dinâmica de Memória
11/5/2015
EDA - Prof. Paulemir Campos
1
Pilhas: Introdução

Definição

É uma estrutura de dados
de tamanho variável,
sendo que elementos são
incluídos (empilhados)
e/ou removidos
(desempilhados) apenas
pela extremidade topo.
11/5/2015
EDA - Prof. Paulemir Campos
15
Topo
12
99
54
102
77
Base
2
Pilhas: Introdução


Note que uma pilha é uma estrutura de
dados do tipo FILO (First In Last Out).
Isto porquê o primeiro elemento
empilhado é sempre o último a ser
desempilhado.
11/5/2015
EDA - Prof. Paulemir Campos
3
Pilhas: Introdução

Operações Básicas:





Teste de pilha vazia;
Criação da pilha;
Empilhamento;
Desempilhamento;
Acesso aos elementos da pilha.
11/5/2015
EDA - Prof. Paulemir Campos
4
Pilhas: Introdução

Do ponto de vista da alocação de memória
para esse tipo de estrutura de dados,
podem ser implementadas usando:


Alocação Estática: Em geral através de
arranjo ou vetor;
Alocação Dinâmica: Utilizando ponteiro.
Normalmente com lista simplesmente
encadeada.
11/5/2015
EDA - Prof. Paulemir Campos
5
Pilhas: Alocação Estática

Características:




Teste de Pilha Vazia: Tamanho do Vetor é zero;
Cria-se um vetor de tamanho suficientemente
grande para a finalidade de uso;
Quando um elemento é empilhado o índice do topo
é acrescido em 1;
Quando um elemento é desempilhado (se possível)
o índice do topo é decrescido em 1.
11/5/2015
EDA - Prof. Paulemir Campos
6
Pilhas: Alocação Estática

Características:




Geralmente há uma variável do tipo inteiro
chamada topo, para armazenar o índice do vetor
correspondente ao topo da pilha;
Caso o vetor comece em 1, uma pilha vazia teria
topo=0.
Neste caso, uma pilha estaria vazia se topo=0.
O acesso ao elementos é feito pelo topo, bem como
empilhamentos e desempilhamentos.
11/5/2015
EDA - Prof. Paulemir Campos
7
Pilhas: Alocação Dinâmica

Considere a definição do tipo tPilhaSimples
abaixo:
defina estrutura no {
caracter
ponteiro estrutura no
} tPilhaSimples
11/5/2015
dado
proximo
EDA - Prof. Paulemir Campos
8
Pilhas: Alocação Dinâmica

Criando uma pilha unitária:
ponteiro tPilhaSimples func CriaPilha(caracter novo){
ponteiro tPilhaSimples topo
topo = aloque(tPilhaSimples)
topo->dado = novo
topo->proximo = NULL
retorne topo
}
11/5/2015
EDA - Prof. Paulemir Campos
9
Pilhas: Alocação Dinâmica

Teste de pilha vazia:
booleano func PilhaVazia(ponteiro tPilhaSimples topo){
se (topo == NULL) retorne TRUE
senao retorne FALSE
}
11/5/2015
EDA - Prof. Paulemir Campos
10
Pilhas: Alocação Dinâmica

Empilhando um elemento:
ponteiro tPilhaSimples func Empilha (ponteiro tPilhaSimples topo; caracter novo) {
ponteiro tPilhaSimples novoTopo
novoTopo = aloque(tPilhaSimples)
se (novoTopo == NULL) retorne topo /* Erro durante a alocação dinâmica
de memória */
novoTopo->dado = novo
novoTopo->proximo = topo
retorne novoTopo
}
11/5/2015
EDA - Prof. Paulemir Campos
11
Pilhas: Alocação Dinâmica

Desempilhando um elemento:
ponteiro tPilhaSimples func Desempilha (ponteiro tPilhaSimples topo) {
ponteiro tPilhaSimples novoTopo
se (Topo == NULL) retorne topo /* Pilha vazia */
novoTopo = topo->proximo
desaloque(topo)
retorne novoTopo
}
11/5/2015
EDA - Prof. Paulemir Campos
12
Pilhas: Alocação Dinâmica

Acessando elementos da pilha

Como estamos usando uma lista simplesmente
encadeada podemos acessar todos os elementos
da pilha, apartir do topo, fazendo pequenos
ajustes na função de acesso aos elementos de
uma lista simples para uso com o tipo pilha, sem
ter a necessidade de desempilhá-los.
11/5/2015
EDA - Prof. Paulemir Campos
13
Filas: Introdução

Definição

É uma estrutura de dados de tamanho
variável, sendo que elementos são incluídos
(enfileirados) pelo fim da fila e removidos
(desenfileirados) pelo início da fila.
15
12
19
51
7
213
INÍCIO
11/5/2015
54
99
88
FIM
EDA - Prof. Paulemir Campos
14
Filas: Introdução


Note que uma fila é uma estrutura de
dados do tipo FIFO (First In First Out).
Isto porquê o primeiro elemento
enfileirado é sempre o primeiro a ser
desenfileirado.
11/5/2015
EDA - Prof. Paulemir Campos
15
Filas: Introdução

Operações Básicas:





Teste de fila vazia;
Criação da fila;
Enfileiramento;
Desenfileiramento;
Acesso aos elementos da fila.
11/5/2015
EDA - Prof. Paulemir Campos
16
Filas: Introdução

Do ponto de vista da alocação de memória
para esse tipo de estrutura de dados,
podem ser implementadas usando:


Alocação Estática: Em geral através de
arranjo ou vetor;
Alocação Dinâmica: Utilizando ponteiro.
Normalmente com lista simplesmente
encadeada.
11/5/2015
EDA - Prof. Paulemir Campos
17
Filas: Alocação Estática

Características:




Teste de Fila Vazia: Índice fim menor que inicio;
Cria-se um vetor de tamanho suficientemente
grande para a finalidade de uso;
Quando um elemento é enfileirado o valor do fim é
igual ao tamanho do vetor;
Quando um elemento é desenfileirado (se possível)
o valor do inicio é acrescido em 1.
11/5/2015
EDA - Prof. Paulemir Campos
18
Filas: Alocação Estática

Características:



Note que, desta forma, posições vão se perdendo
na fila estática.
Um solução, é deslocar o conteúdo do vetor em
uma posição no sentido do índice inicial do vetor.
Assim, como o início será sempre um mesmo valor,
há apenas a necessidade da variável fim.
11/5/2015
EDA - Prof. Paulemir Campos
19
Filas: Alocação Dinâmica

Considere a definição do tipo tFilaSimples
abaixo:
defina estrutura no {
caracter
ponteiro estrutura no
} tFilaSimples
11/5/2015
dado
proximo
EDA - Prof. Paulemir Campos
20
Filas: Alocação Dinâmica

Criando uma fila unitária:
ponteiro tFilaSimples func CriaFila(caracter novo){
ponteiro tFilaSimples inicio
inicio = aloque(tFilaSimples)
inicio->dado = novo
inicio->proximo = NULL
retorne inicio
}
11/5/2015
EDA - Prof. Paulemir Campos
21
Filas: Alocação Dinâmica

Teste de fila vazia:
booleano func FilaVazia(ponteiro tFilaSimples inicio){
se (inicio == NULL) retorne TRUE
senao retorne FALSE
}
11/5/2015
EDA - Prof. Paulemir Campos
22
Filas: Alocação Dinâmica

Enfileirando um elemento:
ponteiro tFilaSimples func Enfileira (ponteiro tFilaSimples inicio; caracter elemento) {
ponteiro tFilaSimples
temp, novo
temp = cabeca /* Considere que inicio não é um ponteiro nulo */
/* Percorre a fila até encontrar o último elemento */
enquanto (temp->proximo != NULL)
temp = temp->proximo
/* Enfileira o novo elemento no fim da fila */
novo = aloque(tFilaSimples)
novo->dado = Elemento
novo->proximo = temp->proximo
temp->proximo = novo
retorne inicio
}
11/5/2015
EDA - Prof. Paulemir Campos
23
Filas: Alocação Dinâmica

Desenfileirando um elemento:
ponteiro tFilaSimples func Desenfileira (ponteiro tFilaSimples inicio) {
ponteiro tFilaSimples novoInicio
se (inicio == NULL) retorne inicio /* Fila vazia */
novoInicio = inicio->proximo
desaloque(inicio)
retorne novoInicio
}
11/5/2015
EDA - Prof. Paulemir Campos
24
Filas: Alocação Dinâmica

Acessando elementos da fila

Como estamos usando uma lista simplesmente
encadeada podemos acessar todos os
elementos da fila, apartir do inicio, fazendo
pequenos ajustes na função de acesso aos
elementos de uma lista simplesmente
encadeada para usar com o tipo fila.
11/5/2015
EDA - Prof. Paulemir Campos
25
Referências


Szwarcfiter, J. L.; Markenzon, L.
Estruturas de Dados e seus
Algoritmos. Rio de Janeiro: LTC, 2a.
ed., 1994.
Veloso, P. et al. Estrutura de Dados.
Rio de Janeiro: Editora Campus, 1996.
11/5/2015
EDA - Prof. Paulemir Campos
26