Apostila Estrutura de Dados

Prévia do material em texto

CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 1 
 
 
 
 
 
 
 
 
APOSTILA 
 
 
 
 
 
 
 
 
 
ESTRUTURA 
DE DADOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
MANAUS 2013 
 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 2 
 
 
 
 
 
 
 
ABSTRAÇÃO DE DADOS 
 
Um processo é qualquer seqüência finita e ordenada de passos que visa promover 
transformações definidas sobre uma determinada matéria-prima. Se denominamos entrada a 
matéria-prima no seu estado inicial; e saída o que se obtém após as transformações 
realizadas pelo processo, temos o esquema geral a seguir: 
 
 
 
 
 
 
Entrada/saída de um processo 
 
Matéria-prima abstrata: é processamento de dados. 
 
Abstrata: apresenta-se sob a forma de valores. 
 
Processamento realizado pelo computador: 
Entrada: dados colhidos do mundo real externo ao computador; 
Processo: série finita de operações que são realizadas a partir desses dados; 
Saída: transformação sofrida pelos dados através de um processo. 
 
 
 
 
 
 
 
processamento de dados 
 
Exemplo: 
 
 
 
 
 
 
 
 
 
 
 
 
 
ENTRADA 
(Estado Inicial) 
PROCESSAMENTO SAÍDA 
(Estado Final) 
DADOS CONHECIMENTO INFORMAÇÃO 
Raio R de uma 
circunferência 
P = 2 .  . R Perímetro P da 
circunferência 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 3 
 
 
TIPOS ABSTRATOS DE DADOS 
OBJETIVOS DAS ESTRUTURAS DE DADOS 
 
TIPOS DE DADOS (TDS) 
 
Embora os termos "tipos de dados", "estruturas de dados" e "tipos abstratos de dados" sejam 
parecidos, têm significados diferentes. Em linguagens de programação o tipo de dados de 
uma variável define o conjunto de valores que a variável pode assumir. Exemplo: BOOLEAN 
pode assumir valores TRUE ou FALSE. A declaração de uma variável em Pascal especifica 
duas coisas: 
1. Quantidade de bytes reservados para a variável (ex. 2bytes); 
2. Como o dado representado por esses bytes pode ser interpretado. (ex. 2 bytes = 16 bits = 
65536 combinações. Um integer é interpretado de -32767 a 32768 sendo o ponto "zero" 
bem no meio desses dois bytes). 
 
Tipos de Dados: São métodos para interpretar o conteúdo da memória do 
computador. Exemplo de conjunto básico de tipos de dados primitivos (inteiro, real, 
caractere, lógico) oferecidos pelas linguagens de programação; e agrupamentos 
complexos de dados desses tipos primitivos (vetor, registro, ponteiro). 
 
var 
 numero :integer; 
 letra :char; 
 cadeia :string; 
 vetor :array[1..10] of integer; 
 registro :record 
 quebrado :real; 
 logico :boolean; 
end; 
 
TIPOS ABSTRATOS DE DADOS (TADS) 
 
Visão de conceito de Tipo de Dados (perspectivas diferentes): 

 Computador - interpreta bits; 
 Usuário - deseja realizar uma operação (somar dois números) 
 
O conceito de Tipo de Dado divorciado do hardware é chamado TAD. 
 
TAD - formado por um conjunto de valores e uma série de funções que podem ser aplicadas 
sobre estes valores. 
Funções + valores (em conjunto) = modelo matemático empregado para "modelar" e 
solucionar problemas do mundo real: 
 
 Especifica características relevantes dos objetos envolvidos no problema; 
 Especifica forma com que eles se relacionam; e 
 Especifica como podem ser manipulados. 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 4 
 
 
 
TAD não leva em consideração como os valores são representados na memória do 
computador e nem se preocupa com o "tempo" gasto para aplicar as funções sobre tais 
valores. 
Exemplos: 
 
 Listas; 
 Pilhas; 
 Filas; 
 
AS ESTRUTURAS DE DADOS (EDS) 
 
É um método particular de implementar um TAD. A implementação de um TAD escolhe uma 
ED para representá-lo. Cada ED é constituída de tipos básicos (integer, char, real) ou dos 
tipos estruturas (array, record) de uma linguagem. 
 
 
 
 
 
 
 
Implementação: transformação de TAD em um Tipo Concreto de Dados. 
 
OBJETIVO DAS ESTRUTURAS DE DADOS: 

 Teórico: Identificar e desenvolver modelos matemáticos, determinando que classes 
de problemas podem ser resolvidos com o uso deles. 
 Prático: Criar representações concretas dos objetos e desenvolver rotinas capazes 
de atuar sobre essas representações, de acordo com o modelo considerado. 
 
LISTAS LINEARES 
 
É uma estrutura que armazena elementos de forma alinhada, ou seja, com elementos 
dispostos um após o outro, como em uma lista de nomes, peças, valores, pessoas, compras, 
etc. 
 
FUNDAMENTOS 
Uma Lista Linear, é uma coleção L: [a1, a2, ..., an], n>=0, cuja propriedade estrutural baseia-
se apenas na posição relativa dos elementos, que são dispostos linearmente. Se n=0, 
dizemos que a lista L é vazia; caso contrário, são válidas as seguintes propriedades: 

 a1 é o primeiro elemento de L; 
 an é o último elemento de L; 
 ak, a<k<n, é precedido pelo elemento ak-1 e seguido por ak+1 em L. 
 
TAD (Modelo 
Matemático) 
IMPLEMENTAÇÃO TCD (Padrão 
bits, Rotinas) 
a1 a2 a3 ... an 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 5 
 
 
 
 
 
Característica fundamental de uma lista linear é o sentido de ordem unidimensional dos 
elementos que a compõem. Assim, não temos dúvida onde inicia ou termina a lista. Algumas 
operações com listas: 
 
 acessar um elemento qualquer; 
 inserir um elemento numa posição específica; 
 remover um elemento de uma posição específica; 
 combinar duas listas em uma única; 
 particionar uma lista em duas; 
 obter cópias de uma lista; 
 determinar o total de elementos na lista; 
 ordenar os elementos da lista; 
 procurar um determinado elemento na lista; 
 apagar uma lista; 
 outras... 
 
Uma lista com um array, pode ser implementada como uma seqüência de records com 
elementos disponíveis: 
 
 de forma consecutiva - Lista Estática Seqüencial; 
 de forma não consecutiva - Lista Estática Encadeada; 
 
Uma lista pode ser ordenada ou não. Pascal permite construir EDs avançadas - Lista 
Dinâmicas; mais versáteis, utilizando ponteiros e variáveis dinâmicas. 
 
Considerando apenas operações de acesso, inserção e remoção restritas aos extremos das 
listas, temos casos especiais: 
 
 Pilha: inserção, remoção, acesso realizados em um único extremo. Lista LIFO. 
 Fila: inserção num extremo e remoção, acesso no outro extremo. Lista FIFO. 
 
 
ALOCAÇÃO DE MEMÓRIA 
 
Para implementar uma lista linear: como podemos armazenar os elementos da lista dentro do 
computador? Alocar área de memória é responsabilidade do programador e estará em uma 
das quatro categorias abaixo: 
 
 SEQÜENCIAL ENCADEADA 
ESTÁTICA Estática Seqüencial Estática Encadeada 
DINÂMICA Dinâmica Seqüencial Dinâmica Encadeada 
 
 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 6 
 
 
ALOCAÇÃO ESTÁTICA X ALOCAÇÃO DINÂMICA 
 
ALOCAÇÃO ESTÁTICA: 
 
Quantidade total de memória utilizada pelos dados é previamente conhecida e definida de 
modo imutável, no próprio código-fonte do programa. Durante o programa não varia a 
quantidade de memória. 
 
ALOCAÇÃO DINÂMICA: 
 
Programa cria novas variáveis enquanto executa, ou seja, áreas de memórias não declaradas 
no programa passam a existir durante a execução. 
 
 
 
 
 
 
 
 
 
 
Um ponteiro é uma variável que contém o endereço da memória de outra variável ou 
estrutura de dados. 
 
Uma variável dinâmica é a única estrutura de dados do Turbo Pascalque tem de estar 
identificada numa declaração VAR antes de ser utilizada em um programa. O Turbo Pascal 
armazena as variáveis dinnâmicas numa área especial de memória chamada HEAP. 
 
program alocacao; 
type 
 ptr = ^integer; 
var 
 p :ptr; {aloca variável estaticamente} 
begin 
 new(p); {aloca variável dinamicamente} 
 p^ := 12345; 
 writeln(p^); 
end. 
 
 
Na figura anterior, P é a variável estática e 1FFAH é o endereço da variável dinâmica ou 
variável anônima. 
 
Utilizamos os comandos new() e dispose() para alocar e deslocar espaços dinâmicos 
respectivamente. 
 
 
 
Memória usada pelo programa 
 
 
 P: 
 
 1FFAh 
 
 
Memória livre no sistema 
ESTÁTICA DINÂMICA 
1FFAh 12345 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 7 
 
 
 
ALOCAÇÃO SEQÜENCIAL X ALOCAÇÃO ENCADEADA 
 
ALOCAÇÃO SEQÜENCIAL: 
 
Consiste em colocar os elementos de uma lista em células de memória consecutivas, um após 
o outro. 
 
 
 
 
 
 
 
 
 
Vantagem: Acesso rápido a um dado elemento com um simples e rápido cálculo. 
 
Ponto fraco: Ao precisar inserir ou suprimir elementos no meio da lista, será necessário um 
certo esforço para movimentar os elementos de modo a abrir espaço para inserção ou ocupar 
espaço liberado para um elemento removido. 
 
ALOCAÇÃO ENCADEADA: 
 
Ao invés de manter elementos ocupando células consecutivas, nesta alocação os elementos 
podem ocupar quaisquer células (não necessariamente consecutivas) e, para manter essa 
relação de ordem linear, juntamente com cada elemento é armazenado o endereço do 
próximo elemento da lista. 
 
Elementos armazenados em blocos de memória denominados nodos ou nós. 
 
Cada nodo é composto pelo menos por dois campos: 

 Dados; 
 Endereços. 
 
Destaque: 
 
 Endereço do primeiro elemento da lista L; 
 Endereço do elemento fictício que segue o último elemento da lista (NULO, TERRA, 

 
 
 
 
 
 
Célula 
Memória 
 elemento 
A1 1C34h A2 1725h A3  
3FAAh 1C34h 1725h 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 8 
 
 
 
LISTA ESTÁTICA SEQÜENCIAL – LES 
 
Uma lista estática seqüencial é um arranjo de registros onde estão estabelecidos regras de 
precedência entre seus elementos ou é uma coleção ordenada de componentes do mesmo 
tipo. O sucessor de um elemento ocupa posição física subsequente. 
 
Ex: lista telefônica, lista de alunos . 
 
A implementação de operações pode ser feita utilizando array e record, onde o vetor associa o 
elemento a(i) com o índice i (mapeamento seqüencial). 
 
Características de Lista Estática Seqüencial 

 elementos na lista estão ordenados; 
 armazenados fisicamente em posições consecutivas; 
 inserção de um elemento na posição a(i) causa o deslocamento a direita do 
elemento de a(i) ao último; 
 eliminação do elemento a(i) requer o deslocamento à esquerda do a(i+1) ao último; 
 
Mas, absolutamente, uma lista estática seqüencial ou é vazia ou pode ser escrita como ( a(1), 
a(2), a(3), ... a(n) ) onde a(i) são átomos de um mesmo conjunto S. 
 
Além disso, a(1) é o primeiro elemento, a(i) precede a(i+1), e a(n) é o último elemento. 
 
 
A a1 a2 an 
 1 2 n 
 
Assim as propriedades estruturadas da lista permitem responder a questões como: 
 
 qual é o primeiro elemento da lista; 
 qual é o último elemento da lista; 
 quais elementos sucedem um determinado elemento; 
 quantos elementos existem na lista; 
 inserir um elemento na lista; 
 eliminar um elemento da lista. 
 
Conseqüência: As quatros primeiras operações são feitas em tempo constante. Mas, as 
operações de inserção e remoção requererão mais cuidados. 
 
Vantagem: 
 
 acesso direto indexado a qualquer elemento da lista 
 tempo constante para acessar o elemento i - dependerá somente do índice. 
 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 9 
 
 
Desvantagem: 
 movimentação quando eliminado/inserido elemento 
 tamanho máximo pré-estimado 
Quando usar: 
 listas pequenas 
 inserção/remoção no fim da lista 
 tamanho máximo bem definido 
 
ALGORITMOS DE INSERÇÃO E REMOÇÃO EM LES 
ESTRUTURA DE DADOS E OPERAÇÕES BÁSICAS 
DEFINIÇÃO DA ED 
 
Const MAX=100; 
Type 
 Lista = record 
 A:array[1..MAX] of integer; 
 n:0..MAX; 
 End; 
Var 
 L: lista; 
 
Operações simples utilizando Lista Estática Seqüencial a serem definidas nas Units 
 
1) Acesso a um elemento 
Writeln (L.A[i]); 
 
2) Atualização 
L.A[i]:= 'Valor' 
 
3) Tamanho da Lista 
Begin 
tamanho:=L.n; 
End; 
4) Inserção de um elemento na posição i 
Requer o deslocamento à direita dos elementos a(i+1)...a(n) 
Begin 
i:=1; 
 For j:=L.n+1 downto i do 
 L.A[j]:=L.A[j-1]; 
 write (l.n+1,' valor...: '); 
 readln(l.A[i]); 
 L.n:=L.n+1; 
End; 
 
 
5) Remoção do i-ésimo elemento 
Requer o deslocamento à esquerda dos elementos a(i+1)...a(n) 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 10 
 
 
Begin 
 i:=1; 
for j:=i to L.n-1 do 
L.A[j]:=L.A[j+1]; 
L.n:=L.n-1; 
End; 
 
 
ALGORITMOS DE BUSCA EM LES 
 
1) LISTAS SEQUENCIAIS NÃO ORDENADAS 
 
Seja L uma lista linear não ordenada alocada seqüencialmente 
Var 
L: arrray [1..n] of record 
chave: T1; 
info: T2; 
End; 
 
A função busca1 abaixo busca um registro contendo a chave x na lista L, e retorna o índice do 
registro se encontrado, caso contrário retorna zero. 
Function busca1(x); 
Var i: 1..Max; 
Begin 
i := 1; 
busca1 := 0; {elemento não encontrado} 
While i <= Nelem do 
If L[i].chave = x 
 then 
 Begin 
 busca1 := i; 
 i := Nelem + 1; {termina loop} 
 End 
 Else i := i+1; 
End; 
Em busca1( ), para cada elemento dois testes são realizados 
 
1. i <= Nelem 
2. L[i].chave = x. 
Esse processo pode ser melhorado com o uso do seguinte artifício: é criado um novo registro 
no final da lista, chamado de sentinela, que contém a chave procurada. A busca é realizada 
sabendo-se que um registro contendo a chave vai ser encontrado. 
 
Ao final verifica se o registro encontrado é o sentinela. Deste modo o teste duplo para cada 
elemento é evitado. A lista L, neste caso, deve poder conter um registro extra. 
Function busca(x) 
Var i: 1..Max; 
Begin 
L[Nelem+1].chave := x; {insere elemento sentinela} 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 11 
 
 
i := 1; 
While (L[i].chave <> x) do 
i := i+1; 
 {checa se encontrado é o sentinela} 
If (i = Nelem + 1) 
 Then 
 busca := 0 
 Else 
 busca := i; 
End; 
 
2) LISTAS SEQUENCIAIS ORDENADAS 
 
No caso de listas ordenadas, deve-se aproveitar o fato de que nem sempre é necessário 
percorrer a lista toda para concluirmos que elemento não está na lista. 
A versão do algoritmo de busca com sentinela para listas ordenadas é: 
 
Function busca_ord(x) 
Var 
 i: 1..Max; 
Begin 
L[Nelem+1] .chave := x; {insere elemento sentinela} 
i := 1; 
 While (L[i].chave < x) do {compara-se apenas os menores} 
 i := i+1; 
 If (i = Nelem + 1) or i(L[i].chave <> x) 
 Then 
 busca := 0 
 Else 
 busca := i; 
End; 
O fato de se utilizar o recurso da sentinela na busca seqüencial, acima, elimina a necessidade 
de testar, para cada elemento, se o final da lista é alcançado ou não.No caso de listas ordenadas, pode-se apresentar um algoritmo BEM mais eficiente – o qual 
tira MUITO MAIS proveito do fato da lista estar ordenada! 
 
O algoritmo de busca binária tem como idéia básica o fato de que, dada uma posição dentro 
da lista, o elemento procurado vai estar ou antes ou depois desta posição, e, portanto, não se 
precisa procurar dos dois lados. 
Numa dada lista ordenada: 
 Compara-se o elemento procurado com o registro do meio da lista, para saber se o 
elemento estaria na metade superior ou inferior da lista. 
 Repete-se esse processo até encontrar o elemento ou esgotar a lista. 
 
Function busca_bin(x) 
 Var 
inf, sup, meio: índices; 
 Begin 
inf := 1; 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 12 
 
 
sup := n; 
busca_bin := 0; 
 While inf <= sup do 
 Begin 
 meio := [(inf + sup) div 2]; 
 If L[meio].chave = x 
 then 
 Begin 
 busca_bin := meio; 
 inf := sup + 1; 
 End 
 Else If (L[meio].chave < x) 
 Then 
 inf := meio + 1 
 Else 
 sup := meio -1; 
End; 
End; 
 
CRIAÇÃO DE BIBLIOTECAS 
 
UNITS EM TURBO PASCAL 
 
Uma Unit é uma coleção de constantes, tipos de dados, variáveis, procedimentos e funções. 
Cada Unit é como um programa Pascal separado. Ela é uma biblioteca de declarações que 
permite dividir seu programa e compilá-lo em partes separadas. Ela pode ter um corpo 
principal o qual é chamado antes do seu programa ser iniciado para preparar as 
"inicializações" necessárias. 
 
Todas as declarações em uma Unit estão normalmente relacionadas. Por exemplo, a unit CRT 
contém todas as declarações de rotinas relativas à SCREEN do PC. O Turbo Pascal possui 8 
Units pré-definidas: System, Overlay, Graph, Dos, Crt, Printer... 
 
ESTRUTURA DE UMA UNIT 
 
UNIT <identificador>; {arquivo deve ter mesmo nome.PAS} 
INTERFACE 
uses <lista de units> {opcional} 
 <declarações públicas> {só cabeçalho} 
IMPLEMENTATION 
uses <lista de units> {opcional} 
 <declarações privadas> 
 <implementação de proc. e funções> 
 {corpo das funções e proc.} 
Begin 
 <inicializações> 
End. 
 {ou} 
End. 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 13 
 
 
Exemplo 1: Unit IntLib 
 
Contém duas rotinas simples atuando sobre os inteiros 
 
Unit IntLib; /* INTLIB.PAS */ 
Interface 
Procedure ISwap (var I,J: integer); 
Function IMax(I,J: integer): integer; 
Implementation 
Procedure ISwap; 
Var Temp: integer; 
 Begin 
 Temp:=I; 
 I:=J; 
 J:=Temp; 
 End; 
 Function IMax; 
 Begin 
 If I>J Then 
 IMax:=I 
 Else IMax:=J; 
 End; 
End. 
 
O programa abaixo, localizado em outro arquivo, utiliza esta unit. 
 
Program Test; 
Uses IntLib; 
Var A,B: integer; 
 Begin 
 Write('Dê dois inteiros:'); 
 Readln(A,B); 
 ISwap(A,B); 
 Writeln('A=',A, 'B=',B); 
 Writeln('Máx=', Imax(A,B)); 
 End. 
 
Exemplo 2: Unit circulares - Units podem "utilizar" outras Units estabelecendo referências 
"circulares". Program Circular: usa Unit Display (definida pelo usuário) para imprimir 3 
mensagens na tela em coordenadas dadas. 
 
Program Circular 
Uses 
 Crt, Display; 
Begin 
Clrscr; 
WriteXY(1,1,'upper left corner of screen'); 
WriteXY(100, 100, 'Way off the screen'); 
 WriteXY(81-length('Back to reality'),15-length('Back to reality'); 
End. 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 14 
 
 
LISTA ESTÁTICA ENCADEADA – LEE 
Os elementos da lista são registros com um dos componentes destinado a guardar o endereço 
do registro sucessor. 
 
Vantagens: 
 não requer mais a movimentação de elementos na inserção e eliminação (como na 
lista seqüencial); 
 apenas os ponteiros são alterados (lembre que cada registro pode conter elementos 
muito complexos); 
 
Desvantagens: 
 necessário prever espaço máximo da lista; 
 necessário gerenciar a Dispo. 
 acesso é não indexado, para acessar a(i) temos que percorrer a(1) ... a(i-1) pois o 
endereço de a(i) está disponível apenas em a(i-1); 
 aumento do tempo de execução, o qual é gasto obtenção de espaço de memória; 
 reserva de espaço para a Dispo; 
 tamanho máximo pré-definido. 
 
Quando usar: 
 quando for possível fazer uma boa previsão do espaço utilizado e quando o ganho 
dos movimentos sobre a perda do acesso direto a cada elemento for compensador. 
 
Para evitar reservar espaço e gerenciar a Dispo, podemos utilizar LISTAS ENCADEADAS 
DINÂMICAS. 
 
IMPLEMENTAÇÃO DE OPERAÇÕES – LEE 
 
Supondo apenas um campo de informação do tipo T: 
 
Const N=_____; {número máximo de elementos} 
Type 
 endereco= 0..N; {elementos armazenados nas posições de 
1 a N do array; o valor 0 indica fim da 
lista} 
Type 
 Rec = record 
 info: T 
 lig: endereço; 
 End; 
 
 Lista = record 
 A: array[1..N] of Rec; 
 Prim, Dispo: endereco; 
 End; 
Var 
 L: lista; 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 15 
 
 
1) Qual é o primeiro elemento da lista ? 
Function Primeiro (L: lista): T; 
Begin 
 If L.Prim <> 0 
 Then 
 Primeiro := L.A[L.Prim].info; 
End; 
 
2) Qual é o último ? 
 
Function Ultimo(L: Lista): T; 
Var 
 p: endereco; 
Begin 
 If L.Prim = 0 
 Then 
 {Retorna lista vazia } 
 Else 
 Begin 
 p := L.Prim; 
 While L.A[p].lig <> 0 do 
 p := L.A[p].lig; {L.A[p].info é o último 
elemento} 
 End; 
 Ultimo := L.A[p].info; 
End; 
 
3) Quantos elementos tem a lista ? 
 
Function No_elementos(L: Lista): integer; 
Var 
 Nelem: integer; 
 p: endereco; 
Begin 
 If L.Prim = 0 
 Then 
 Nelem := 0 {lista vazia} 
 Else 
 Begin 
 p := L.Prim; 
 Nelem := 1; 
 While L.A[p].lig <> 0 do 
 Begin 
 Nelem := Nelem + 1; {Nelem contém o Número 
de elementos} 
 p := L.A[p].lig; 
 End; 
 End; 
 No_elementos := Nelem; 
End; 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 16 
 
 
ALGORITMOS PARA INSERÇÃO E ELIMINAÇÃO DE ELEMENTOS 
Na inserção podemos contar com o registro j como sendo disponível, e na eliminação 
podemos contar com o registro j como a ser deixado disponível. 
 
Para inserir ou eliminar um elemento da lista, temos que saber do endereço do predecessor 
(lembre que a busca é guiada pelo conteúdo do registro, no caso de listas ordenadas). Este 
predecessor é quem contém o endereço daquele que será o sucessor do elemento 
inserido/eliminado. 
 
1) Inserção após o registro de endereço k 
Procedure Insere(var L: Lista; k: endereco, valor: T); 
Var 
 j: endereco; 
Begin 
 If L.Dispo <> 0 
 Then {se a Dispo está vazia, não pode inserir!} 
 Begin 
 L.A[j].info := valor; 
 L.A[j].lig := L.A[k].lig; 
 L.A[k].lig:= j; 
 End 
 Else {não pode inserir registro} 
 ... 
End; 
 
2) Eliminação do registro de endereço j precedido por k 
Procedure Remover(var L: Lista; k,j: endereco); 
Begin 
L.A[k].lig := L.A[j].lig; 
End; 
 
3) Casos especiais 
Inserção antes do primeiro elemento 
Procedure Insere_prim(var L: Lista; valor: T); 
Var 
 j: endereco; 
Begin 
 If L.Dispo <> 0 
 Then 
 Begin 
 L.A[j].info:= valor; 
 L.A[j].lig := L.Prim; 
 L.Prim := j; 
 End 
 Else 
 { não pode inserir } 
End; 
 
OBS: No caso da lista estar vazia, Prim passar a apontar o único elemento da lista. 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 17 
 
 
Inserção em lista vazia 
Procedure Insere_ListaVazia(var L: Lista; valor: T); 
Var 
 j: endereco; 
Begin 
 If L.Dispo <> 0 
 Then { lista vazia ou prim = 0 } 
 Begin 
 L.A[j].info:=valor; 
 L.A[j].lig:=0; {null} 
 L.Prim:=j; 
 End; 
End; 
Eliminação do primeiro elemento 
Procedure Remove_Primeiro(var L: Lista); 
Var 
 j: endereco; 
Begin 
 j := L.Prim; 
 L.Prim := L.A[L.Prim].lig; 
End; 
LISTA DINÂMICA – LD 
 
As linguagens de programação modernas tornaram possível explicitar não apenas o acesso 
aos dados, mas também aos endereços desses dados. 
 
Isso significa que ficou possível a utilização de ponteiros explicitamente implicando que uma 
distinção notacional deve existir entre os dados e as referências (endereços) desses dados. 
 
A notação introduzida por Wirth, com a introdução de Pascal, é: Type Tp = ^T. Essa 
declaração expressa que valores do tipo Tp são ponteiros para dados do tipo T. Portanto, 
lemos o símbolo ^ como sendo ponteiro para... e na declaração acima lemos Tp é um ponteiro 
para variáveis do tipo T. 
 
O fato de que o tipo dos elementos apontados ser evidente na declaração do ponteiro tem 
importância fundamental. Isso distingue ponteiros de linguagens de alto nível de endereços 
em Assembly. 
 
Valores para ponteiros são gerados quando dados correspondentes a seus tipos são 
alocados/deslocados dinamicamente. Em Pascal, os procedimentos new e dispose existem 
com esse propósito. 
 
Portanto, deixa-se a cargo do programa (via linguagem de programação), e não do 
programador, prover e devolver espaço para inserções e eliminações em tempo de execução. 
 
 Custo: Tempo de execução comprometido. 
 Idéia: O programador declara apenas o tipo de registro que contém um elemento da 
lista, e avisa que a alocação será dinâmica. Sempre que requisitar um registro novo 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 18 
 
 
para a inserção, ou liberar um registro a ser eliminado, o programador lança mão de 
duas rotinas pré-definidas para este fim. 
 
Até agora, quando queríamos guardar muitos dados na memória, usávamos vetores. Só que 
vetores têm limite, ou seja, temos que definir de antemão o número máximo de elementos que 
um vetor pode ter. O que acontece se não tivermos esse limite? Ou seja, o que fazemos se 
esse limite não for definido? Uma alternativa seria criar um vetor imenso, gastando um mundo 
de memória. Mas ainda assim correríamos o risco de estourar o limite do vetor. Então, o que 
fazer? 
A solução ideal seria se pudéssemos, à medida que recebemos algum dado, separar um 
espaço na memória para ele e armazená-lo lá. Ou seja, nosso limite seria dado pela 
quantidade de memória disponível no computador. 
Naturalmente, como separamos um espaço na memória e guardamos um valor lá, temos que, 
de algum modo, saber qual é esse pedaço de memória, ou seja, precisamos de uma espécie 
de endereço que nos leve a esse pedaço para que, futuramente, possamos acessar o que 
guardamos lá ou mesmo guardar algo lá. 
Então como fazemos isso em Pascal? Com ponteiros. Ponteiros nada mais são do que 
variáveis que guardam o endereço de uma região de memória, podendo essa região conter a 
informação que quisermos. 
 
Vejamos como declaramos ponteiros em Pascal: 
 VAR nome_do_ponteir:^tipo_apontado; 
 
Nesse caso, tipo_apontado é qualquer tipo, simples ou definido pelo usuário, do Pascal. Ou 
seja, não posso fazer: 
 VAR ptr : ^ARRAY[1..10] OF integer; 
 
mas posso fazer: 
 TYPE vetor = ARRAY[1..10] OF integer; 
 VAR ptr : ^vetor; 
 
Agora vamos ver como usar um ponteiro. Suponha a declaração: 
 VAR ptr : ^integer; 
 
O que temos aqui? Apenas uma variável, chamada ptr, que é um ponteiro para um inteiro, ou 
seja, ela guarda um endereço de memória onde pode ser armazenado um inteiro. Mas de qual 
pedaço ela tem o endereço? Nenhum. Para efetivamente dar um valor a ptr temos que fazer: 
 new(ptr); 
 
A forma geral do new é 
 New(variável_de_ponteiro); 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 19 
 
 
O que, então, isso faz? Esse comando simplesmente diz ao sistema operacional para que este separe 
um pedaço de memória em que caiba um inteiro (o tipo apontado por ptr), guardando o endereço deste 
pedaço em ptr. E qual é esse endereço? Não sabemos, e nem precisamos saber, pois o Pascal abstrai 
tudo isso. Ou seja, podemos agora usar a variável ptr quase como se fosse um integer comum. Por 
que quase? Veja abaixo: 
 VAR ptr : ^integer; 
 
 BEGIN 
 new(ptr); {separei um pedaço de memória para um 
inteiro} 
 
 ptr^ := 2; {coloquei o valor 2 nesse pedaço de 
memória} 
 
 ptr^ := ptr^ * 3; {faço esse pedaço de memoria 
receber o triplo 
 do que lá havia} 
 END. 
 
Viu como fizemos? "ptr^" pode ser usada como qualquer variável integer. Veja agora o programa 
abaixo: 
type 
 
 tipo=^integer; 
 
 VAR 
 p1 : tipo; 
 p2 : tipo; 
 
 BEGIN 
 clrscr; 
 new(p1); {reservei um pedaço de memoria para um inteiro, 
 fazendo p1 apontar para ele} 
 
 p2 := p1; {fiz p2 apontar para o mesmo pedaço de memoria 
 que p1 aponta} 
 
 p1^ := 4; {coloquei o valor 4 nesse pedaço de memoria} 
 
 writeln(p2^); {escrevi o valor que está no pedaço de 
 memória apontado por p2, ou seja, 4, pois 
 p2 aponta para o mesmo pedaço de memória 
 que p1} 
 
 p2^ := p2^ + 3; {adicionei 3 ao valor que havia no pedaço 
 de memória apontado por p2 e armazenei 
 novamente nesse pedaço o resultado} 
 
 writeln(p1^); {escrevo o conteúdo da memória apontada por 
 p1, ou seja, 7, pois p1 aponta para o mesmo 
 pedaço de memória que p2 aponta} 
 readkey; 
 END. 
 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 20 
 
 
Como isso funciona? Vejamos por partes: 
Quando fizemos new(p1), separamos (ou, como dizemos, alocamos) espaço na memória 
suficiente para um inteiro, guardando o endereço desse espaço em p1, ou seja, fizemos p1 
apontar para lá: 
 
 Ao fazer p2 := p1 (note que não é p2^ := p1^), guardamos uma cópia do endereço que 
estava em p1 em p2. Ou seja, fazemos p2 apontar para a mesma região de memória 
que p1 apontava: 
 
 Ao fazermos p1^ := 4 guardamos 4 nessa região: 
 
 Ao lermos p2^ no write, simplesmente lemos o valor que está na região da memória 
apontada por p2, ou seja, 4. 
 Ao fazermos p2^ := p2^ + 3, pegamos o conteúdo da região de memória apontada por 
p2, somamos 3 a este e armazenamos o resultado de volta nessa mesma região: 
 
 Ao lermos p1^ no write, novamente lemos o valor que está na regiãode memória 
apontada por p1, ou seja, 7, já que esta é a mesma região que é apontada por p2 e que 
foi modificada no passo anterior. 
Então não confunda! Se fazemos 
 p2^ := p1^; 
 
estamos copiando o conteúdo da região de memória apontada por p1 para a região de memória apontada 
por p2. Já se fizermos 
 p2 := p1; 
 
estaremos fazendo p2 apontar para a mesma região de memória apontada por p1. Agora que sabemos 
como carregar valores com ponteiros, como fazemos para "zerar" um ponteiro? Ou seja, para dizer que 
ele não aponta para lugar nenhum? 
 p1 := NIL; 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 21 
 
 
Se não fizermos isso, ele conterá um endereço de memória que pode já ter sido liberada pelo programa, 
ou que pode não pertencer ao programa, o que geraria um erro quando da execução. 
E, por falar em liberar memória, como fazemos se quisermos liberar a memória que reservamos com 
new? 
 Dispose(variável_de_ponteiro); 
 
ou seja 
 Dispose(p1); 
 
Dispose avisa ao sistema operacional que não vamos mais precisar desse pedaço de memória, liberando 
esta. SEMPRE libere a memória que não vai mais usar para não esgotar os recursos da máquina. 
Cuidado com o seguinte erro: 
type 
 tipo=^integer; 
VAR p1 : tipo; 
 p2 : tipo; 
 
 BEGIN 
 new(p1); 
 
 p2 := p1; 
 
 p1^ := 4; 
 
 Dispose(p2); 
 
 writeln(p1^) 
 END. 
 
isso pode gerar um erro, pois já liberei a memória apontada por p2, que é a mesma apontada por p1 
Vale também lembrar que, ao final do programa, se você não liberou a memória usada, o computador a 
libera para você. Ainda assim é uma boa prática limpar seu lixo. 
E se agora quisermos um ponteiro para um tipo mais complexo, como registro? 
 TYPE 
 Tipo1=real; 
 Tipo2=integer; 
 Reg = RECORD 
 cp1 : tipo1; 
 cp2 : tipo2; 
 cp3 : ARRAY[1..10] of char 
 END; 
 
 VAR p : ^reg; 
 
 BEGIN 
 New(p); 
 END. 
 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 22 
 
 
Pronto! Aloquei espaço para o meu registro. Ou seja, na memória foi reservado espaço suficiente para guardar os 3 campos 
do nosso registro. E como acessamos ou mudamos o valor desses campos? 
TYPE 
 Tipo1=real; 
 Tipo2=integer; 
 Reg = RECORD 
 cp1 : tipo1; 
 cp2 : tipo2; 
 cp3 : ARRAY[1..10] of char 
 END; 
 VAR p : ^reg; 
 i : integer; 
 
 BEGIN 
 new(p); 
 p^.cp1 := 3.12; 
 p^.cp2 := Round(p^.cp1); {guardei 3} 
 
 FOR i:=1 TO 10 DO 
 p^.cp3[i] := Chr(Ord('a') + i); 
 
 writeln(p^.cpq,' - ', p^.cp2,' - 
',p^.cp3[5]); 
 
 Dispose(p) 
 END. 
 
Ou seja, agimos como se "p^" fosse o nome do registro. E se em vez de registro quisermos lidar com um vetor? 
TYPE 
 pvet=^vet; 
 vet = ARRAY[1..10] of integer; 
 
 VAR p : pvet; 
 
 BEGIN 
 clrscr; 
 new(p); 
 
 p^[1] := 4; 
 p^[2] := 10; 
 p^[3] := p^[1] + p^[2]; 
 writeln(p^[1],' + ',p^[2],' = 
',p^[3]); 
 Dispose(p); 
 writeln(p^[3]); 
 readkey; 
 END. 
 
Novamente, agimos como se "p^" fosse o nome do vetor. 
Com ponteiros, as operações permitidas são = e <>. Assim ,não posso fazer +, - etc. Ou seja, as únicas 
operações que posso usar com ponteiros são: 
 p1 = p2 -> True se ambos apontam para a mesma região de memória 
 p1 <> p2 -> True se ambos apontam para regiões diferentes 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 23 
 
 
Agora que já vimos o que são ponteiros, vamos aprender, na próxima seção, a usá-los. 
 
ESTRUTURA DE DADOS (ED) E OPERAÇÕES LD 
 
LISTA DINÂMICA ENCADEADA 
 
Suponha que queremos ler uma lista de dados. Até aí tudo bem. Agora suponha que não 
conhecemos o número total de dados. Como fazemos então? 
Seria desejável seguir o seguinte algoritmo: 
 inicialmente a lista está vazia 
 enquanto o usuário não manda parar de ler 
 leio um dado 
 coloco este dado na lista 
 
assim fica fácil não? Mas como fazer isso em Pascal? Usando ponteiros. Como? Com uma 
lista encadeada. O que, então, é uma lsita encadeada? 
Uma lista encadeada é uma lista onde cada elemento - chamado de nó - contém um valor e 
um ponteiro para o elemento seguinte. Assim, sabendo onde está o primeiro elemento da lista, 
podemos chegar a qualquer outro elemento. Há vários tipos de listas encadeadas: 
 Simples: 
 
 
O sinal de aterramento significa que este ponteiro é NIL, ou seja, não aponta para lugar 
nenhum. 
 Circular: 
 
 
 
 
 
 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 24 
 
 
 Duplamente encadeada: 
 
e muitas outras mais. O limitante é apenas sua imaginação. Aqui iremos usar somente listas 
simples. Mas e qual as vantagens e desvantagens de cada uma? Listas duplamente 
encadeadas são fáceis de se percorrer, mas ocupam mais espaço na memória. Note que 
nessas eu posso, a partir de um elemento, voltar na lista, percorrê-la de trás para frente, pois 
tenho ponteiros que medizem onde estão o próximo elemento e o anterior. 
As circulares simples são fáceis de percorrer e não ocupam muita memória. Mas se o número 
de elementos for grande, vai se comportar quase como uma lista simples. Qual lista é a 
melhor? Depende do problema a ser resolvido.,p> Agora vamos definir operações básicas em 
listas: 
 Criação de uma lista 
 Inclusão de um elemento na lista 
 Exclusão de um elemento da lista 
 Esvaziamento da lista 
 Contagem do número de elementos da lista 
 Inclusão de um elemento na posição i 
 Exclusão do iº elemento na lista 
 Busca da posição do primeiro elemento de valor x 
 Exclusão do primeiro elemento de valor x 
 etc 
Vamos ver então como criar uma lista encadeada. Nos exemplos que seguem estaremos 
usando a lista encadeada simples, conforme foi apresentada acima. 
Antes de mais nada, vamos definir nossa lista: 
 TYPE tipo = real; 
 p_no = ^no; 
 no = RECORD 
 valor : tipo; 
 prox : p_no 
 END; 
 
Agora vamos definir o procedimento de criação da lista. 
 PROCEDURE Cria(VAR cabeca : p_no); 
 BEGIN 
 cabeca := NIL 
 END; 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 25 
 
 
Pronto! O que fizemos com isso? Dissemos que a lista está vazia ao darmos um valor "nada" 
à cabeça desta. Se não fizermos isso, a cabeça pode conter lixo indesejável. 
Agora vamos incluir um elemento na lista. A questão é: onde? Você decide. Pode ser no 
início, pode ser no meio (caso você queira ordenar a lista enquanto a constrói) e pode ser no 
fim. Nesse caso, vamos por no fim. Então, como faremos? 
Suponha que temos a seguinte lista: 
 
Vamos, então, colocar um elemento em seu final 
 Alocamos o espaço para o novo elemento, fazendo q apontar para ele, e o 
abastecemos com valor 
 
 Usamos um ponteiro auxiliar, p, para apontar para a cabeça da lista 
 
 Percorremos a lista com p até que este aponte para o último elemento 
 
 Fazemos o próximo elemento de p (que agora aponta para o fim da lista) ser q, ou seja, 
fazemos q ser o novo fim da lista 
 
E se a lista estiver inicialmente vazia? Então 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 26 
 
 
 Alocamos o espaço para o novo elemento e o abastecemos com valor Fazemos a cabeça da lista ser esse novo elemento 
 
 
 
 
 
 
 
Assim, o procedimento fica: 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 27 
 
 
 PROCEDURE Inclui(VAR cabeca : p_no; elemento : tipo); 
 VAR q : p_no; {o novo elemento} 
 p : p_no; {auxiliar} 
 BEGIN 
 {aloco espaço para o novo elemento} 
 New(q); 
 
 {abasteço os valores nesse} 
 q^.valor := elemento; 
 q^.prox := NIL; 
 
 {vejo onde coloco q na lista} 
 IF cabeca <> NIL THEN 
 BEGIN 
 {a lista não estava vazia} 
 p := cabeca; 
 
 {vou até o fim da lista} 
 WHILE p^.prox <> NIL DO p := p^.prox; 
 
 {agora p é o último elemento, pois p^.prox = NIL} 
 
 {faço o próximo elemento de p ser q, ou seja, q é o 
novo fim} 
 p^.prox := q 
 END 
 ELSE {a lista está vazia. Faço q ser a cabeça} 
 cabeca := q 
 END; 
 
Vamos agora excluir um elemento da lista. Novamente, qual? Você escolhe! Vamos tomar 
como política a exclusão do primeiro elemento da lista. Como faremos isso? 
Suponha a lista: 
 
Vamos, então, retirar um elemento de seu início: 
 Primeiro fazemos p apontar para o início da lista: 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 28 
 
 
 Depois fazemos a cabeça apontar para o segundo elemento: 
 
 Eliminamos agora o elemento apontado por p 
 
E o procedimento fica: 
 PROCEDURE Exclui(VAR cabeca : p_no; VAR 
valor:tipo); 
 VAR p : p_no; {auxiliar} 
 BEGIN 
 IF cabeca <> NIL THEN 
 BEGIN 
 {a lista não está vazia} 
 p := cabeca; 
 
 {faço a cabeça apontar para o próximo} 
 cabeca := cabeca^.prox; 
 
 {retorno o valor que está em p} 
 valor := p^.valor; 
 
 {mato o elemento apontado por p} 
 Dispose(p); 
 END 
 {else a lista está vazia, não há o que tirar} 
 END; 
 
Suponha que queremos simplesmente matar a lista inteira, como fazemos isso? Da mesma 
forma que excluímos um elemento, só que não devolvemos valor algum: 
 Coloco um ponteiro p na cabeça da lista 
 Enquanto p não for nil 
o Faço a cabeça apontar para o próximo de p 
o Mato p 
o Faço p apontar para a cabeça 
O procedimento fica: 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 29 
 
 
 PROCEDURE Limpa(VAR cabeca : p_no); 
 VAR p : p_no; {auxiliar} 
 BEGIN 
 p := cabeca; 
 
 WHILE p <> NIL DO 
 BEGIN 
 cab := p^.prox; 
 Dispose(p); 
 p := cab 
 END 
 END; 
 
E como fazemos para contar os elementos de uma lista? Basta criar um contador e percorrer 
a lista incrementando o contador: 
 Coloco um ponteiro p na cabeça da lista e zero o contador cont 
 Enquanto p não for nil 
o Incremento cont 
o Faço p apontar para o próximo elemento 
Ou seja: 
 FUNCTION NumEl(cabeca : p_no) : integer; 
 VAR p : p_no; {auxiliar} 
 BEGIN 
 p := cabeca; 
 NumEl := 0; 
 
 WHILE p <> NIL DO 
 BEGIN 
 p := p^.prox; 
 NumEl := NumEl + 1 
 END 
 END; 
 
Agora, usando algumas das funções acima, vamos incluir um novo nó na posição i da nossa 
lista. Como faremos isso? Suponha a seguinte lista 
 
 Primeiro fazemos p apontar para o início da lista: 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 30 
 
 
 Em seguida movemos p até o elemento anterior à posição em que queremos incluir 
(suponha que queremos incluir na 3ª posição): 
 
 Criamos, então, espaço para o novo elemento, fazendo q apontar para ele: 
 
 Fazemos, então, o próximo elemento de q ser o próximo de p: 
 
 E o próximo elemento de p ser q: 
 
pronto! Incluímos na posição i = 3. 
E se quisermos incluir na última posição? Funciona? Claro! Pois pararei com p no último 
elemento. 
E se a lista estiver vazia? Nesse caso, basta criar o elemento e fazer a cabeça apontar para 
ele (veja abaixo como incluir na primeira posição). Note que nesse caso, o único i aceitável é 
1. 
E se a posição pedida for 1? Esse é um caso um pouco mais complicado, pois não há como 
parar um elemento antes, o que indica que nosso algoritmo falha. Como fazer, então? 
 Primeiro criamos espaço para o novo elemento, fazendo q apontar para ele: 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 31 
 
 
 
 Fazemos, então, o próximo elemento de q ser a cabeça: 
 
 E a cabeça apontar para q: 
 
 
 
 
 
Pronto! Incluímos na primeira posição. 
 Vamos agora ao procedimento: 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 32 
 
 
 PROCEDURE IncluiEmPos(VAR cabeca:p_no;valor:tipo;posicao:integer); 
 VAR p : p_no; {auxiliar} 
 q : p_no; {o novo elemento} 
 i : integer; {contador do FOR} 
 BEGIN 
 {testo se a posição é válida} 
 IF (posicao <= (NumEl(cabeca) + 1)) AND (posicao > 0) THEN 
 BEGIN 
 {é uma posição válida. O +1 é porque se tem 5 elementos 
 posso por na posição 6, por exemplo (embora não na 7)} 
 
 {crio o novo elemento} 
 new(q); 
 q^.valor := valor; 
 q^.prox := NIL; 
 
 IF posicao=1 THEN {quero na primeira posição} 
 BEGIN 
 {se a lista estiver vazia, não há problema aqui} 
 
 {faço o próximo de q ser a cabeça} 
 q^.prox := cabeca; 
 
 {faço a cabeça ser q} 
 cabeca := q 
 END 
 ELSE BEGIN {é outra posição} 
 {note que aqui a lista jamais estará vazia, senão 
 NumEl retornaria 0 e posição > 1} 
 
 {faço p apontar para a cabeça} 
 p := cabeca; 
 
 {movo p até o elemento anterior à posição. Como p já 
 está em 1, movo posicao-2 posições} 
 FOR i:=1 TO posicao-2 DO 
 p := p^.prox; 
 
 {agora p aponta para o elemento anterior} 
 
 {faço o próximo de q ser o próximo de p} 
 q^.prox := p^.prox; 
 
 {faço o próximo de p ser q} 
 p^.prox := q 
 END 
 END 
 {ELSE não faz nada!} 
 END; 
 
 
 
 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 33 
 
 
Ótimo! Vamos agora excluir um elemento da posição i. Suponha a seguinte lista: 
 
 Primeiro fazemos p apontar para o início da lista: 
 
 Em seguida movemos p até o elemento anterior à posição do elemento que queremos 
excluir (suponha que queremos excluir da 3ª posição): 
 
 Marcamos a posição a ser excluída com um ponteiro q: 
 
 Fazemos, então, o próximo elemento de p ser o próximo de q: 
 
 Eliminamos q: 
 
pronto! Excluímos o nó da posição i = 3. 
E se a lista estiver vazia? Nesse caso, Nada poderá ser excluído. 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 34 
 
 
E se a posição pedida for 1? Esse, novamente, é um caso um pouco mais complicado, pois não há 
como parar um elemento antes, o que indica que nosso algoritmo falha. Como fazer, então? Basta 
seguir o algoritmo dado acima para retirar um elemento do início da lista. 
Vamos, então, à função que retira o 1º elemento da lista. Essa função retorna o valor que estava nesse 
elemento: 
 FUNCTION TiraDaPos(VAR cabeca:p_no;posicao:integer):tipo; 
 VAR p : p_no; {auxiliar} 
 q : p_no; {auxiliar} 
 i : integer; {contador do FOR} 
 BEGIN 
 {testo se a posição é válida} 
 IF (posicao <= NumEl(cabeca)) AND (posicao > 0) THENBEGIN 
 {é uma posição válida. Note que se a lista estiver vazia 
 nada é feito, pois posicao >=1, o que é > 0} 
 
 {faço p apontar para a cabeça} 
 p := cabeca; 
 
 IF posicao=1 THEN {quero na primeira posição} 
 BEGIN 
 {faço a cabeça ser o segundo elemento} 
 cabeca := cabeca^.prox; 
 
 {dou o valor de retorno} 
 TiraDaPos := p^.valor; 
 
 {mato o nó} 
 Dispose(p) 
 END 
 ELSE BEGIN {é outra posição} 
 {movo p até o elemento anterior à posição. Como p já 
 está em 1, movo posicao-2 posições} 
 FOR i:=1 TO posicao-2 DO 
 p := p^.prox; 
 
 {agora p aponta para o elemento anterior} 
 
 {faço o próximo de p ser q} 
 q := p^.prox; 
 
 {faço o próximo de p ser o próximo de q} 
 p^.prox := q^.prox; 
 
 {retorno o valor de q} 
 TiraDaPos := q^.valor; 
 
 {mato o nó apontado por q} 
 Dispose(q) 
 END 
 END 
 END; 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 35 
 
 
Agora vamos ver como buscar a posição do primeiro elemento que contenha o valor x na 
nossa lista. Para tal, o procedimento é simples: 
 Coloco um ponteiro p na cabeça da lista e crio um contador, inicializando-o com 1. 
 Enquanto p não for NIL e não encontrei o valor vou incrementando p e o contador. 
 Se encontrei o valor, retorno o valor do contador, senão, retorno 0. 
Vamos, então, à função: 
 FUNCTION Pos(cabeca:p_no; elemento:tipo):integer; 
 VAR p : p_no; {auxiliar} 
 BEGIN 
 {inicializo o contador} 
 Pos := 1; 
 
 {aponto p para a cabeça da lista} 
 p := cabeça; 
 
 WHILE (p <> NIL) AND (p^.valor <> elemento) DO 
 BEGIN 
 p := p^.prox; 
 Pos := Pos+1 
 END; 
 
 IF p = NIL THEN Pos := 0 
 {o else é automático, pos terá o valor certo} 
 END; 
 
E para excluir o primeiro elemento de valor x? Basta 
 Buscar a posição do primeiro elemento de valor x 
 Excluir o elemento nessa posição 
Ou seja: 
 PROCEDURE ExcluiX(VAR cabeca:p_no; elemento:tipo); 
 VAR el : tipo; {o elemento a ser excluído, é auxiliar} 
 BEGIN 
 el := TiraDaPos(cabeca,Pos(cabeca,elemento)) 
 {excluí, el jogo fora} 
 END; 
 
 
 
 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 36 
 
 
PILHAS 
 
Uma PILHA é um tipo especial de LISTA LINEAR em que todas as operações de inserção e 
remoção são realizadas numa mesma extremidade, denominada TOPO. 
 
Cada vez que um novo elemento deve ser inserido na pilha, ele é colocado no topo; e em 
qualquer momento, apenas aquele posicionado no topo da pilha pode ser removido. Devido a 
esse tipo de acesso, os elementos são sempre removidos numa ordem inversa àquela em que 
foram inseridos, de modo que o último elemento que entra é exatamente o primeiro que sai. 
Por isso essas listas são denominadas LIFO (last-in/first-out). 
 
Uma LISTA LIFO, é uma coleção que pode aumentar ou diminuir durante a sua existência. 
Pilha é sinônimo de Lista LIFO. 
 
Exemplo: Pilha de pratos. 
Uma pilha suporta três operações básicas, tradicionalmente denominadas como: 
 
 Topo: Acessa o elemento posicionado no topo da pilha; 
 Push: Insere um novo elemento no topo da pilha (Insere); 
 Pop: Remove um elemento do topo da pilha (Retira ou Elimina). 
 
Sendo P uma pilha e x um elemento qualquer, a operação push(P,x) aumenta o tamanho da 
pilha P, acrescentando o elemento x no seu topo. A operação Pop(P) faz com que a pilha 
diminua, removendo e retornando o elemento no seu topo. Das três operações básicas, a 
única que não altera o estado da pilha é Top(P); ela simplesmente retorna uma cópia do 
elemento existente no topo da pilha, sem removêlo. 
 
OPERAÇÃO ESTADO DA PILHA RESULTADO 
--- P: [ ] --- 
Push (P,a) P: [a] --- 
Push (P,b) P: [b,a] --- 
Push (P,c) P: [c,b,a] --- 
Pop (P) P: [b,a] c 
Pop (P) P: [a] b 
Push (P,d) P: [d,a] --- 
Top (P) P: [d,a] d 
 
Tomando como exemplo um porta guardanapos, existem as operações push (empurre). Ao 
inserir um elemento, os outros são empurrados para baixo e o último elemento é mantido no 
topo da pilha, daí o nome push-down. Analogamente ao remover um elemento, é como se os 
demais pressionassem por baixo até que ele “saltasse”, pop-up (saltar para cima). 
 
Notação Linear de uma Pilha: 
 
P: [an, an-1, ..., a2, a1] 
 
Notação gráfica: 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 37 
 
 
an Final 
an-1 
... 
a2 
a1 Começo 
 
Exemplo limitações físicas de uma pilha (chão, mesa, prato, teto, altura da parede) 
 
Precisamos então de mais três operações essenciais para manipular pilhas: 
 
 Init: Inicializa a pilha no estado “vazia”; 
 IsEmpty: verifica se a pilha está vazia; 
 IsFull: verifica se a pilha está cheia. 
 
Init(P), IsEmpty(P), IsFull(P). 
Exemplos do uso de pilhas: 
 
1. Programa para converter de decimal para binário. 
2. Chamadas e retornos de rotinas em um programa, cujo papel da pilha é fundamental 
no controle do programa. 
 
 
PILHAS COM ALOCAÇÃO ESTÁTICA: 
 
ESTRUTURA DE DADOS 
const 
MAX = 50; {qtd elementos} 
type 
elem = char; 
pilha = record 
 topo :integer; 
 memo :array[1..MAX] of elem; 
 end; 
var 
p :pilha; 
 
ALGORITMOS PARA MANIPULAÇÃO 
 
INICIALIZANDO A PILHA 
 
procedure init(var p:pilha); 
begin 
p.topo := 0; 
end; 
 
VERIFICANDO LIMITES (VAZIA OU CHEIA) 
 
Function EstaVazia(p:pilha):boolean; 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 38 
 
 
Begin 
If p.topo = 0 
 then 
 EstaVazia := true 
 Else 
 EstaVazia := false; 
end; 
 
Function EstaVazia(p:pilha):boolean; 
Begin 
EstaVazia := (p.topo=0) 
End; 
 
Function EstaCheia(p:pilha):boolean; 
Begin 
If p.topo = MAX 
 then 
 EstaCheia := true 
 Else 
EstaCheia := false; 
end; 
 
function EstaCheia(p:pilha):boolean; 
begin 
EstaCheia := (p.topo=MAX) 
end; 
 
EMPILHANDO UM ELEMENTO 
 
procedure push(var p:pilha); x:elem); 
begin 
if (not EstaCheia(p) 
 then 
begin 
p.topo := p.topo+1; 
p.memo[p.topo] := x; 
end 
 else 
writeln('Estouro de pilha!'); 
end; 
 
DESEMPILHANDO UM ELEMENTO 
 
function pop(var p:pilha):elem; 
begin 
if not EstaVazia(p) 
 then 
 begin 
 pop := p.memo[p.topo]; 
 p.topo := p.topo-1; 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 39 
 
 
 end; 
 else 
 writeln('Pilha vazia'); 
end; 
 
OBTENDO O VALOR DO TOPO 
 
function top(p:pilha):elem; 
begin 
if not EstaVazia(p) 
 then 
 top := p.memo[p.topo]; 
 else 
 writeln('Pilha vazia!); 
end; 
 
Pilha de Alocação Dinâmica 
 
Pense numa pilha de livros. É assim que ela funciona. Se queremos por mais um livro na 
pilha, onde colocamos? No topo! E se queremos tirar um livro, de onde tiramos? Do topo. 
Então, como temos visto, uma pilha nada mais é do que uma lista encadeada que tem como 
característica o fato de que, se queremos incluir um elemento na lista, temos de incluí-lo no 
início desta, e se queremos tirar um elemento da lista, tiramos do início desta. 
Dessa forma, uma pilha tem as seguintes funções: 
 Criação da pilha (como nas listas acima) 
 Empilhamento (quando coloco um elemento no topo da pilha, ou seja, no início da lista) 
 Desempilhamento (quando tiro um elemento do topo da pilha, ou seja, do início da lista) 
Note que não há como eu tirar um elemento do meio da pilha. 
É como nossa pilha de livros, para retirar um livro do meio, tenho que desempilhar todos os 
que estãoacima. Da mesma forma, para tirar um dado do meio da pilha, tenho que 
desempilhar os que estão antes dele. Vejamos, agora, funções para criação, empilhamento e 
desempilhamento: 
 TYPE tipo = real; 
 p_pilha = ^pilha; 
 pilha = RECORD 
 dado : tipo; 
 prox : p_pilha 
 END; 
 
 VAR topo : p_pilha; 
 
 PROCEDURE IniciaPilha(VAR topo : p_pilha); 
 BEGIN 
 topo := NIL 
 END; 
 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 40 
 
 
 PROCEDURE Empilha(VAR topo : p_pilha; dado : tipo); 
 VAR p : p_pilha; {auxiliar} 
 BEGIN 
 {crio o novo elemento e dou valor a ele} 
 new(p); 
 p^.valor := dado; 
 
 {faço ele apontar para o topo da pilha} 
 p^.prox := topo; 
 
 {faço o topo apontar para ele} 
 topo := p 
 END; 
 
 FUNCTION Desempilha(VAR topo : p_pilha) : tipo; 
 VAR p : p_pilha; {auxiliar} 
 BEGIN 
 {faço p apontar para o topo} 
 p := topo; 
 
 {retorno o valor de p} 
 Desempilha := p^.valor; 
 
 {baixo o topo, para o segundo elemento} 
 topo := topo^.prox; 
 
 {elimino p} 
 Dispose(p) 
 END; 
 
 
 
FILAS 
 
Uma FILA é um tipo especial de LISTA LINEAR em que as inserções são realizadas num 
extremo, ficando as remoções restritas ao outro. O extremo onde os elementos são inseridos 
é denominado final e, aquele de onde são removidos é denominado começo da fila. 
 
A cada inserção, um novo elemento é colocado no final da fila. O elemento que aguarda mais 
tempo na fila, o do começo, é o removido por primeiro. A ordem de saída corresponde 
diretamente à ordem de entrada, ou seja, os primeiros que entram são os primeiros que saem. 
Graças a isso, as filas são denominadas listas FIFO (First-In/First- Out). 
 
Exemplo bastante comum: balcão de atendimento, onde pessoas formam fila para 
aguardarem atendimento. Não devemos considerar pessoas que furam a fila, pois o tipo 
abstrato de dados não suporta inserção nem remoção no meio da lista. 
 
 
 Começo Final 
 ▼ ▼ 
Sai ◄ є є є є є є є є є є ◄ Entra 
 
Fila em inglês, significa queue. Duas operações básicas que uma fila suporta são: 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 41 
 
 
 
 Enqueue: insere um elemento no final da fila; 
 Dequeue: remove um elemento do começo da fila. 
 
Sendo F uma fila e x um elemento qualquer, a operação Enqueue(F,x) aumenta o tamanho 
da fila F, acrescentando x ao seu final. A operação dequeue(F) faz a fila diminuir, já que 
remove e retorna o elemento posicionado no começo. 
 
OPERAÇÃO ESTADO DA FILA RESULTADO 
--- F: [ ] --- 
Enqueue(F,a) F: [a] --- 
Enqueue(F,b) F: [a,b] --- 
Enqueue(F,c) F: [a,b,c] --- 
Enqueue(F,d) F: [a,b,c,d] --- 
Dequeue(F) F: [b,c,d] a 
Dequeue(F) F: [c,d] b 
Enqueue(F,e) F: [c,d,e] --- 
Enqueue(F,f) F: [c,d,e,f] --- 
Enqueue(F, Dequeue(F)) F: [d,e,f] c 
 F: [d,e,f,c] --- 
Dequeue(F) F: [e,f,c] d 
Dequeue(F) F: [f,c] e 
Dequeue(F) F: [c] f 
 
 
 
 
 
Notação Linear de uma Fila: 
 
F: [a1, a2..., an-1, an] 
 
Notação gráfica: 
 
 
 
 
 
 
Precisamos então de mais operações essenciais para manipular filas: 
 Init: Inicializa a fila no estado “vazia”; 
 Vazia: verifica se a fila está vazia; 
 Cheia: verifica se a fila está cheia; (quando for estática!). 
 
Init(F), Vazia(F), Cheia(F). 
 
Tipo de Alocação: 

Começo 
a1 a2 ... an-1 an 
Final 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 42 
 
 
 Estática: utilizamos com estruturas de registro com vetor para armazenar os 
elementos da fila; 
 Dinâmica: utilizamos com estruturas de ponteiros para registros com elemento e 
endereço de ligação do tipo ponteiro. 
 
Exemplos do uso de filas: 
 Escalonamento de “JOBs”. Fila de processos aguardando os recursos do Sistema 
Operacional. 
 
 
FILA COM ALOCAÇÃO ESTÁTICA 
 unit filaest; {arquivo ‘filaest.pas’} 
INTERFACE 
const 
MAX = 50; 
type 
elem = char; 
fila = record 
 comeco :integer; 
 final :integer; 
 memo :array[1..MAX] of elem; 
 end; 
procedure init(var f:fila); 
function vazia(f:fila):boolean; 
function cheia(f:fila):boolean; 
function prim (f: fila): elem; 
procedure enqueue(var f:fila; x:elem); 
function dequeue(var f:fila):elem; 
IMPLEMENTATION 
procedure init(var f:fila); 
begin 
f.comeco := 1; 
f.final := 1; 
end; 
function vazia(f:fila):boolean; 
begin 
vazia := (f.comeco = f.final); 
end; 
function cheia(f:fila):boolean; 
begin 
cheia := (f.final>MAX); 
end; 
function prim (f: fila): elem; 
Begin 
prim := f.memo[f.comeco]; 
End; 
procedure enqueue(var f:fila; x:elem); 
begin 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 43 
 
 
if not cheia(f) 
 then 
 begin 
 f.memo[f.final] := x; 
 f.final := f.final+1; 
 end 
 else 
writeln('Fila cheia!'); 
end; 
function dequeue(var f:fila):elem; 
begin 
if not vazia(f) 
 then 
 begin 
 dequeue := f.memo[f.comeco]; 
 f.comeco := f.comeco+1; 
 end 
 else 
 writeln('Fila vazia!'); 
end; 
begin 
end. 
 
EXEMPLO DO PROGRAMA PRINCIPAL QUE UTILIZA A BIBLIOTECA: 
 
program fila_tst; 
uses crt,filaest; 
var 
minhafila:fila; 
elemento :elem; 
c :char; 
begin 
clrscr; 
init(minhafila); 
write('digite elemento: '); 
readln(elemento); 
while (elemento<>' ') do 
begin 
enqueue(minhafila,elemento); 
write('digite elemento: '); 
readln(elemento); 
end; 
while not vazia(minhafila) do 
begin 
elemento := dequeue(minhafila); 
write(elemento); 
end; 
writeln(‘pressione uma tecla...’); 
c := readkey; 
end. 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 44 
 
 
FILA COM ALOCAÇÃO DINÂMICA 
 
PROGRAMA PRINCIPAL UTILIZANDO A BIBLIOTECA: 
program fila_tst; 
uses crt,fdinlib; 
var 
minhafila :fila; 
elemento :elem; 
c :char; 
begin 
clrscr; 
init(minhafila); 
write('digite elemento: '); 
readln(elemento); 
while (elemento<>' ') do 
begin 
enqueue(minhafila,elemento); 
write('digite elemento: '); 
readln(elemento); 
end; 
 while not vazia(minhafila) do 
begin 
elemento := dequeue(minhafila); 
write(elemento); 
end; 
writeln(‘pressione uma tecla...’); 
c := readkey; 
end. 
 
BIBLIOTECA DE FILA DINÂMICA: 
 
unit fdinlib; {fdinlib.pas} 
INTERFACE 
type 
elem = char; 
p_no = ^reg_no; 
reg_no = record 
valor :elem; 
prox :p_no; 
end; 
 
fila = record 
comeco :p_no; 
final :p_no; 
end; 
procedure init (var f: fila); 
function vazia (f:fila): boolean; 
function prim (f:fila): elem; 
procedure enqueue (var f:fila; x: elem); 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 45 
 
 
function dequeue (var f: fila): elem; 
IMPLEMENTATION 
procedure init (var f: fila); 
Begin 
f.comeco := nil; 
f.final := nil; 
End; 
function vazia (f:fila): boolean; 
Begin 
vazia := ( f.comeco = nil) and (f.final = nil); 
End; 
function prim (f:fila): elem; 
Begin 
prim := f.comeco^.valor; 
End; 
procedure enqueue (var f:fila; x: elem); 
var 
pont :p_no; 
Begin 
if vazia(f) 
 then 
 begin 
 new(pont); 
 f.final := pont; 
 f.final^.valor := x; 
 f.final^.prox := nil; 
 f.comeco := f.final; 
 end 
 else 
 begin 
 new(pont); 
 f.final^.prox := pont; 
 pont^.valor := x; 
 pont^.prox := nil; 
 f.final := pont; 
 end; 
End; 
function dequeue (var f: fila): elem; 
var 
pont:p_no; 
Begin 
if not vazia(f) 
 then 
 begin 
 dequeue := f.comeco^.valor; 
 if f.comeco^.prox = nil 
 then 
 begin 
 dispose(f.comeco); 
 f.comeco := nil; 
CENTRO EDUCACIONAL FUCAPI 
CURSO TÉCNICO – INFORMÁTICA 
APOSTILA – ESTRUTURA DE DADOS 
 
ESTRUTURA DE DADOS – PÁGINA 46 
 
 
 f.final := nil; 
 end 
 else 
 begin 
 pont := f.comeco^.prox; 
 dispose(f.comeco); 
 f.comeco := pont; 
 end; 
 end 
 else 
 writeln('Fila Vazia!'); 
End; 
begin 
end. 
 
 
 
 
 
 
 
Referências: 
 
 
Algoritmos e Estrutura de Dados 
Wirth, Niklaus 
LTC 
 
Estrutura de Dados e Algoritmos 
Preiss, Bruno R. 
Campus 
 
Lógica de Programação e Estrutura de Dados 
Sandra Puga & Gerson Rissetti 
Prentice-hall 
 
Algoritmos e Programação de Computadores 
Norton Trevisan Roman