Algoritmos e Estrutura de Dados Volume 3

Prévia do material em texto

Recife, 2010
Algoritmos e 
Estrutura de Dados
Rodrigo de Souza
Hugo Rodrigues
Universidade Federal Rural de Pernambuco
Reitor: Prof. Valmar Corrêa de Andrade
Vice-Reitor: Prof. Reginaldo Barros
Pró-Reitor de Administração: Prof. Francisco Fernando Ramos Carvalho
Pró-Reitor de Extensão: Prof. Paulo Donizeti Siepierski
Pró-Reitor de Pesquisa e Pós-Graduação: Prof. Fernando José Freire
Pró-Reitor de Planejamento: Prof. Rinaldo Luiz Caraciolo Ferreira
Pró-Reitora de Ensino de Graduação: Profª. Maria José de Sena
Coordenação Geral de Ensino a Distância: Profª Marizete Silva Santos
Produção Gráfica e Editorial
Capa e Editoração: Allyson Vila Nova, Rafael Lira, Italo Amorim, Glaucia Micaele e Marcella Almeida
Revisão Ortográfica: Marcelo Melo
Ilustrações: Allyson Vila Nova, Moisés de Souza, Lilian Cabral e Diego Almeida
Coordenação de Produção: Marizete Silva Santos
Sumário
Capítulo 1 – Listas ligadas ...................................................................5
1. Listas lineares .................................................................................5
2. Ponteiros e registros .......................................................................8
3. A definição de lista ligada .............................................................13
4. Outros tipos de lista ......................................................................20
Capítulo 2 – Pilhas ..............................................................................27
1. Definição de pilha .........................................................................27
2. Implementando uma pilha em um vetor .......................................29
3. Implementando uma pilha em uma lista ligada ............................32
Capítulo 3 – Filas ................................................................................39
1. Definição de fila ............................................................................39
2. Implementação de uma fila num vetor ..........................................40
3. Implementação de uma fila numa lista ligada ...............................44
Capítulo 4 – Árvores ...........................................................................50
1. A definição de árvore ....................................................................50
2. Implementação de árvores binárias ..............................................53
3. Percursos em uma árvore ............................................................55
4. Árvores de busca ..........................................................................60
Considerações Finais .........................................................................70
Conheça os Autores ...........................................................................72
5
Algoritmos e Estrutura de Dados
Capítulo 1 – Listas ligadas
Vamos conversar sobre o assunto?
Listas ligadas são estruturas de dados muito fundamentais, e 
mostram-se bastante flexíveis para uma variedade de aplicações. 
Listas ligadas podem ser a maneira mais adequada de armazenamento 
de dados para a manutenção de um conjunto dinâmico cuja 
quantidade de elementos é desconhecida de antemão. Certos tipos 
de listas permitem que inserções e remoções sejam realizadas em 
complexidade constante, ou seja, sem o deslocamento de posições 
de memória, uma vez que a posição do item em questão seja 
conhecida. Como estudamos no módulo anterior, o uso de vetores 
para a representação de um conjunto pode exigir o deslocamento de 
porções de memória para a realização de certas operações.
Neste capítulo vamos introduzir o conceito de lista ligada, estudar 
algumas aplicações e ganhar experiência na sua manipulação através 
de exercícios. Nos capítulos seguintes, listas ligadas (e vetores) serão 
novamente utilizadas para a representação de conjuntos dinâmicos 
onde inserções e remoções obedecem a uma certa disciplina, as 
pilhas e as filas.
Temos certeza de que o material deste capítulo será importante 
para sua atividade de programador ou projetista de algoritmo, e 
esperamos que você o estude com prazer. Bom trabalho!
1. Listas lineares
Começaremos nosso estudo com duas seções de preparação 
para a introdução do conceito de lista ligada. A presente seção discute 
o conceito de lista linear, a próxima trata de registros e ponteiros, 
recursos presentes na maior parte de linguagens de programação e 
que permitem uma implementação eficiente de listas ligadas. Ambas 
as seções podem ser lidas rapidamente. No entanto, é importante 
ter segurança de que os conceitos expostos foram compreendidos. 
O conceito de lista ligada se consolidará naturalmente a partir dessa 
introdução.
Vetores e as próximas estruturas de dados que estudaremos para 
a representação de um conjunto dinâmico - listas ligadas, pilhas e 
6
Algoritmos e Estrutura de Dados
filas - baseiam-se na disposição dos elementos desse conjunto em 
sequência, um após o outro. As operações que desejamos realizar no 
conjunto (buscas, inserções, remoções) correspondem, nesse caso, a 
manipulações dessa sequência. Como já observamos anteriormente, 
a eficiência de uma operação pode variar de estrutura para estrutura 
com que o conjunto é implementado, indo de constante até a execução 
de um número de operações proporcional ao tamanho do conjunto. 
No entanto, em todos os casos a operação realizada na sequência é 
a mesma.
Dessa forma, a fim de definirmos precisamente a estrutura “lista 
ligada”, cabe explicitar primeiro a ideia de “disposição dos elementos 
um após o outro”. Para isso, definimos o conceito de lista linear:
Uma lista linear é uma sequência
a1, a2, ..., an
A propriedade estrutural básica de uma lista linear é a posição relativa de seus 
elementos:
• o primeiro elemento é a1;
• o último é an;
• para 1< k < n, ak é precedido por ak-1 e seguido por ak+1.
Por exemplo, considere a lista linear a seguir:
5, 8, 3, 6, 8, 4
O primeiro elemento dessa lista é o 5, o último é o 4, o elemento que 
precede o 3 é o 8, o elemento que o segue é o 6. Note que elementos 
podem se repetir: em nosso exemplo, o 8 aparece em duas posições, 
a segunda e a quinta. O tamanho dessa lista é 6.
É importante compreender que a ordem dos elementos faz parte da 
definição de uma lista linear. Por exemplo, a lista seguinte é diferente 
da anterior, apesar de representar os mesmos elementos:
3, 4, 8, 5, 8, 6
Como acabamos de mencionar, podemos apresentar um conjunto 
dinâmico como uma lista linear, dispondo os elementos um após o 
outro. Nessa representação, operações no conjunto correspondem a 
certas manipulações na lista. Desejaremos dessa forma:
• acessar o elemento na posição k de uma lista;
7
Algoritmos e Estrutura de Dados
• buscar um elemento em uma lista;
• inserir um elemento antes ou depois da posição k;
• remover o elemento na posição k;
• combinar duas ou mais listas em uma;
• separar uma lista em duas ou mais;
• contar o número de elementos em uma lista.
Em nosso exemplo, a inserção do número 1 após a segunda 
posição produz a lista
5, 8, 1, 3, 6, 8, 4
A remoção do elemento na penúltima posição produz a lista
5, 8, 1, 3, 6, 4
Que tal inventar exemplos para as demais operações?
Entendido o conceito de lista linear, o próximo passo é estudar 
meios para construir e manipular listas em um computador. Para 
introduzir o assunto, um esclarecimento. Você já deve ter notado que 
a definição de lista é muito semelhante à de vetor, e talvez esteja se 
perguntando se há alguma diferença entre ambas. Não confunda:
• A definição de lista linear é abstrata, não depende de 
uma estrutura para sua representação na memória de um 
computador.
• Vetores são estruturas de dados. São uma possibilidade para a 
representação de listas lineares em um computador, mas não a 
única.
Na representaçãoem um vetor, a lista é armazenada em posições 
contíguas de memória. Estudamos essa representação no capítulo 2 
do módulo anterior, bem como as operações de inserção e remoção de 
um elemento. Recorde que essas operações exigem o deslocamento 
de uma parte da memória, e por isso sua complexidade não é 
constante. Podemos dizer que a complexidade dessas operações é 
limitada pelo tamanho da lista.
Listas lineares também podem ser representadas com listas 
ligadas, assunto principal deste capítulo e que introduziremos mais 
abaixo. Implementando-se convenientemente essas listas ligadas, 
inserções e remoções podem ser realizadas em complexidade 
8
Algoritmos e Estrutura de Dados
constante. Curioso para saber como? A razão principal você já pode 
intuir: vetores obedecem à restrição rígida de que os elementos são 
armazenados em posições contíguas de memória; nas listas ligadas, 
essa restrição não existe.
Por outro lado, o uso de listas ligadas exige que os endereços 
de memória dos elementos representados sejam explicitamente 
conhecidos. Por isso, antes de definir a estrutura de lista ligada vamos 
discutir brevemente os mecanismos para a manipulação de endereços 
de memória em linguagens de programação.
2. Ponteiros e registros
Ponteiros e registros são mecanismos comuns a muitas linguagens 
de programação importantes, e proporcionam um meio eficiente para 
a implementação de uma lista linear em um computador. Os termos 
“ponteiro” e “registro” podem variar de linguagem para outra, mas o 
principio é o mesmo. Se você, de sua experiência em programação, 
entende bem a definição e funcionamento desses recursos, essa 
seção servirá apenas para fixar algumas convenções. Senão, é 
importante lê-la com cuidado, buscar mais informações em outras 
referências, e se certificar de ter entendido antes de prosseguir.
Em sua experiência de programação, talvez você já tenha 
trabalhado com ponteiros. Ponteiros são variáveis como outra 
qualquer, ou seja, posições de memória que armazenam um dado 
de um tipo determinado. Mas ponteiros, ao invés de armazenar um 
inteiro, um caractere ou um valor booleano, por exemplo, armazenam 
um endereço de memória. Além da operação de atribuição, a operação 
básica com ponteiros é a obtenção do valor armazenado no endereço 
representado.
Como exemplo, considere a representação pictórica a seguir 
da memória de um computador. Recorde que a memória pode ser 
vista como um longo vetor, onde cada posição é identificada por um 
endereço. Nessa figura, os endereços são escritos à direita. Duas 
variáveis também são representadas nessa figura, a e b:
9
Algoritmos e Estrutura de Dados
A variável a está armazenada na posição 874 da memória, e é 
um ponteiro para outra posição de memória, 1462. Também podemos 
dizer que essa variável é um ponteiro para a variável b, que está 
armazenada na posição 1462 e representa um inteiro, 17.
Registros são tipos de dados complexos, e podem ser entendidos 
como aglomerados de outros tipos de dados. Podemos fazer uma 
analogia com um Banco de Dados, que são coleções de registros. 
Um registro, por sua vez, é composto de uma série de campos, não 
necessariamente do mesmo tipo: nome, endereço, idade, data de 
admissão, etc. De fato, um conjunto dinâmico pode ser visto como 
um Banco de Dados, onde desejamos realizar inserções, buscas e 
remoções de registros. 
A figura a seguir representa um registro de um tipo de dados que 
podemos chamar de pessoa. Esse registro é composto por quatro 
campos ou membros:
• “id”, do tipo inteiro;
• “nome” e “sobrenome”, do tipo cadeias de caracteres;
• “nascimento”, do tipo data.
Temos aqui em um único registro quatro variáveis, de tipos 
diferentes, agrupadas em uma mesma unidade lógica. Essas variáveis 
ocupam posições consecutivas de memória a partir de uma posição 
de base, considerada como o endereço do registro.
10
Algoritmos e Estrutura de Dados
Tenha em mente que registros são tipos de dados legítimos, como 
os inteiros. Assim, podemos declarar e usar variáveis representando 
registros, da mesma forma que o fazemos com uma variável que 
representa um inteiro. Em particular, podemos intercambiar os valores 
entre variáveis que representam registros. Por exemplo, se o registro 
ilustrado acima é representado pela variável p, e q é uma variável do 
mesmo tipo (pessoa), a atribuição
q ← p
copia o conteúdo (ou seja, cada campo individualmente) de p em q. 
Trata-se de uma cópia de uma região de memória.
O que ponteiros e registros têm a ver com listas lineares? Já o 
dissemos no início dessa seção: o uso combinado de ponteiros e 
registros é um recurso poderoso e permite representar eficientemente 
listas lineares e outras estruturas em um computador, além de 
proporcionar meios flexíveis para a manipulação dessas estruturas. 
Essa representação será explicitada na próxima seção, que é dedicada 
à introdução das listas ligadas. Mas você já pode manter em mente os 
seguintes elementos:
• uma lista ligada é uma lista linear de registros;
• cada um desses registros têm, além dos dados representados 
(nome, data de nascimento...), um campo particularmente 
importante, um ponteiro para o próximo item da lista (que é 
outro registro);
• o primeiro elemento da lista é identificado também por um 
ponteiro.
O que é um ponteiro para um registro? É o endereço de base para 
a porção de memória ocupada por esse registro. Todos os campos do 
registro podem ser acessados a partir desse endereço de base com a 
soma de um deslocamento conveniente. Um aspecto importante dos 
ponteiros é a eficiência no intercâmbio dos dados representados nos 
Lembrete
Registros em 
C também são 
chamados de 
estruturas, 
e podem ser 
definidos através 
da palavra 
reservada 
struct. Em 
Pascal, registros 
são definidos 
com a palavra 
reservada record. 
Familiarize-
se com essas 
palavras 
reservadas antes 
de resolver os 
exercícios de 
implementação.
11
Algoritmos e Estrutura de Dados
registros. A atribuição entre ponteiros realiza a cópia de um endereço 
de memória, e não de toda a memória ocupada pelo registro. Assim, 
certas operações com listas podem ser feitas de forma eficiente com 
algumas poucas manipulações de ponteiros.
Java, objetos e coleta de lixo
Você já usou a linguagem Java? Trata-se de uma linguagem orientada a 
objetos, um paradigma de programação bastante em voga atualmente, 
com muita aceitação no mercado. Os objetos criados e destruídos em um 
programa Java são semelhantes aos registros discutidos nessa seção, 
com a diferença de que um objeto pode agrupar funções especiais para a 
manipulação de seus membros. Além disso, em Java, a liberação de memória 
após o uso de um objeto é feita automaticamente, mecanismo conhecido 
como coleta de lixo (garbage collection).Os recursos da linguagem Java são 
especialmente adequados para a implementação de uma série de estruturas 
de dados com naturalidade. Se você não conhece essa linguagem, essa 
disciplina é uma excelente oportunidade de aprender! Estude os exercícios 
deste e do próximo capítulo, e tente implementar suas soluções em Java.
Ponteiros e registros oferecem meios para a manutenção de um 
conjunto cuja quantidade de elementos não é conhecida ou mesmo 
limitada de antemão (evidentemente, desde que esse conjunto não seja 
maior do que a memória disponível). Lembra-se de que com vetores 
estabelecemos um limite para o número de elementos representados? 
Com o uso de ponteiros e registros, podemos reservar quantidades 
adicionais de memória para a inserção de um novo registro. De fato, 
vamos encontrar em muitas linguagens de programação funções 
especiais que solicitam ao sistema operacional alocação de memória 
– é o caso do “malloc” no C e do “new” no Pascal.
Simetricamente, a remoção de um novo elemento deve ser 
acompanhada pela liberaçãode memória, tarefa que dependendo 
da linguagem deve ser gerenciada pelo programador. Por exemplo, 
na linguagem C pode-se liberar memória com a função “free”. Esse 
mecanismo de alocação e liberação de memória ao longo da execução 
do programa é denominado alocação dinâmica (contrariamente à 
alocação estática, onde a quantidade de memória necessária é fixa e 
alocada antes da execução do programa).
Mas nem tudo são flores. Ponteiros são um instrumento 
potencialmente perigoso e devem ser utilizados com atenção. Erros 
de programação que induzem o surgimento de “ponteiros perdidos”, 
ou seja, ponteiros que indicam uma posição de memória indisponível, 
Atenção
Você já viu um 
programa em 
C que parou de 
funcionar com 
a mensagem 
“Segmentation 
Fault”? Trata-se 
de uma tentativa 
de acesso a 
uma posição de 
memória indevida 
– possivelmente 
um ponteiro 
perdido.
12
Algoritmos e Estrutura de Dados
são uma das principais fontes de problemas de execução.
Como tudo isso funciona em Portucal? Como serão os registros e 
ponteiros com que implementaremos listas lineares e outras estruturas 
em nossa linguagem hipotética? Novamente, não vamos nos ater 
em detalhes de implementação, pois não desejamos desviar nossa 
atenção do estudo de propriedades de algoritmos para a manipulação 
de um conjunto de dados; você terá contato direto com ponteiros e 
registros em exercícios de programação. Vamos assumir tacitamente 
que registros são um tipo de dados disponível em Portucal, e que 
podemos acessar os campos de um registro através de colchetes.
Por exemplo, se consideramos em um programa em Portucal 
uma variável p que aponta para o registro com os dados de Donald 
Knuth ilustrado no início dessa seção, podemos acessar os valores 
dos campos “nome”, “sobrenome” e “nascimento” desse registro 
escrevendo nome[p], sobrenome[p], nascimento[p], respectivamente. 
Ou seja:
nome[p] = Donald
sobrenome[p] = Knuth
nascimento[p] = 10/1/1938
Antes de concluir, um último aviso. Tenha em mente que, em 
nosso estudo de algoritmos e estruturas de dados, a natureza dos 
dados representados em um registro não é tão importante. Por 
isso, normalmente consideraremos registros que representam 
simplesmente um número inteiro.
Você está preparado para estudar a estrutura de lista ligada 
e entender como implementá-la. E ficará ainda mais preparado 
pesquisando, antes de começar, como funciona o mecanismo 
de alocação dinâmica de sua linguagem favorita. Faça algumas 
experiências simples de criação e liberação de memória para 
registros. Procure sentir-se seguro com o uso de ponteiros, se não 
tem experiência com esse recurso. Precisando de ajuda ou mais 
informações, consulte as referências ao final dessa seção. Tenha em 
mente que o uso de ponteiros exige uma certa experiência, por isso, 
perseverança, não desanime nas primeiras tentativas.
13
Algoritmos e Estrutura de Dados
3. A definição de lista ligada
O conceito de lista ligada emerge naturalmente dos assuntos 
discutidos nas duas seções anteriores. Encontramos uma boa 
definição no item “Listas encadeadas” do sítio “Projeto de Algoritmos” 
do professor Paulo Feofiloff, http://www.ime.usp.br/~pf/algoritmos/. 
Vamos reproduzí-la:
Uma lista encadeada é uma representação de uma sequência de objetos na 
memória do computador.
Dito de outra forma: uma lista ligada (ou encadeada) é uma lista 
linear representada no computador através de ponteiros, registros, ou 
outro tipo de construção.
Para simplificar, vamos estudar, inicialmente, um tipo de lista 
bastante elementar, composta de uma sequência de registros e onde 
cada registro possui dois campos: info e prox. Seus significados:
• “info”, um número inteiro, é o dado armazenado no registro;
• “prox” é um ponteiro para um registro.
A partir de agora, vamos utilizar o termo “célula” ao invés de 
“registro”. A seguinte representação pictórica de uma célula é muito 
útil:
Essa figura apresenta os dois campos do registro: o valor de info é 
26, e o ponteiro prox é representado por uma flecha.
Para onde aponta essa flecha? Que endereço está armazenado 
nesse ponteiro? Você talvez já tenha adivinhado: estamos 
representando uma lista linear; essa flecha aponta para o próximo 
item dessa lista.
Para ilustrar, vamos considerar um exemplo mais completo. 
Suponha que desejamos representar a seguinte lista de inteiros em 
uma lista ligada:
5, 8, 3, 6, 8, 4
Usando nossa notação pictórica, o resultado é:
14
Algoritmos e Estrutura de Dados
Essa lista ocupa seis regiões de memória, distintas e não 
necessariamente consecutivas.
Note que nenhuma célula é apontada pela última flecha, justamente 
por essa ser a última. O apontador armazenado nessa célula recebe 
um valor especial, representado por uma cruz, que indica que 
nenhum endereço válido é representado, e assim a lista terminou. Na 
linguagem C, uma boa ideia é adotar a constante NULL para esse 
valor especial. Em Portucal, vamos usar o termo “nil”.
É fácil acessar o item posterior a uma célula: seu endereço é 
indicado pelo ponteiro armazenado nessa célula. Usando-se esses 
ponteiros, uma lista pode ser completamente percorrida a partir do 
primeiro elemento (confira o programa em Portucal mais abaixo). Por 
isso, podemos representar uma lista simplesmente por um ponteiro 
para o primeiro elemento. E se a lista está vazia? Uma lista vazia 
é um objeto perfeitamente legítimo. Representamos uma lista vazia 
com um ponteiro cujo valor é a constante “nil”.
Continuando nosso exemplo, suponha que a primeira célula da 
lista seja apontado pela variável L. Podemos indicar essa situação da 
seguinte forma:
A seguinte instrução imprime o campo info da primeira célula:
imprima info[L]
Se desejamos armazenar o endereço da segunda célula em uma 
variável M, podemos escrever:
M ← prox[L]
O resultado da instrução 
imprima info[M]
é assim a impressão do número 8, o segundo elemento da lista. O 
resultado é o mesmo se escrevemos
imprima info[prox[L]]
De forma análoga, a seguinte instrução imprime o inteiro 
armazenado na terceira célula, 3:
imprima info[prox[prox[L]]]
15
Algoritmos e Estrutura de Dados
De fato, prox[L] é um ponteiro para a segunda célula, e prox[prox[L]] 
é precisamente o ponteiro armazenado nessa célula. Estude esses 
exemplos com cuidado, certifique-se de que compreendeu.
O seguinte algoritmo em Portucal percorre uma lista seguindo os 
ponteiros, e a cada célula visitada imprime o campo info:
algoritmo IMPRIME-LISTA (L)
 enquanto L <> nil faça
 imprima info[L]
 L←prox[L]
► Recebe uma lista ligada e imprime seu 
► conteúdo
Vamos estudar esse algoritmo com cuidado. Há um único 
parâmetro, um ponteiro L para uma lista de inteiros. Para simplificar, 
vamos relaxar um pouco nosso discurso, e dizer diretamente que “L 
é uma lista”, ao invés de “L é um ponteiro para uma lista”. Não se 
sabe de antemão quantos elementos a lista L representa, mas essa 
informação não é relevante: a impressão pode ser feita seguindo-se 
os ponteiros, o fim da lista é detectado pela constante “nil”. No corpo 
do laço enquanto, a própria variável L recebe seu sucessor. Isso faz 
com que o endereço do antecessor seja perdido pelo algoritmo, mas 
não externamente ao algoritmo (pois o ponteiro L foi passado por 
valor – recorde as convenções da linguagem Portucal detalhadas no 
primeiro módulo).
Perceba que esse algoritmo é correto mesmo se L representa a 
lista vazia. Nesse caso, o valor de L é “nil”, o primeiro teste realizado 
pelo “enquanto” falha, e o algoritmo termina sem imprimir nada. Já a 
seguinte versão não funciona se L é a lista vazia:
algoritmo IMPRIME-LISTA (L)
 repita
 imprima info[L]
 L←prox[L]
 até que L = nil
► Recebe uma lista ligada e imprime seu 
► conteúdo
O problema é que essa versão tentaimprimir o campo info da 
primeira célula mesmo no caso em que a lista é vazia. Essa situação 
pode conduzir a uma falha de execução.
16
Algoritmos e Estrutura de Dados
Às vezes pode ser útil incluir em uma lista uma célula especial 
que aponta para o primeiro elemento da lista, mas que não armazena 
inteiro algum. Essa célula é comumente chamada de cabeça da lista, 
e sua finalidade é simplesmente marcar o início da lista. Nesse caso, 
a lista é representada para um apontador para a cabeça. Nesse tipo 
de lista, a cabeça sempre existe, mesmo que a lista seja vazia, e seu 
endereço nunca muda.
Para ilustrar, segue um algoritmo que imprime uma lista com 
cabeça. O parâmetro L é um ponteiro para a cabeça, e o primeiro 
elemento da lista é prox[L].
algoritmo IMPRIME-LISTA (L)
 L←prox[L]
 enquanto L <> nil faça
 imprima info[L]
 L←prox[L]
► Recebe uma lista com 
► cabeça e imprime seu 
► conteúdo
O uso de uma cabeça não é obrigatório, mas pode facilitar algumas 
situações, pois evita a necessidade de tratar explicitamente o caso 
em que a lista é vazia. Enfatizamos que, se L aponta para uma lista 
sem cabeça vazia, então L é “nil”, enquanto que um apontador para 
uma lista com cabeça nunca é nil (pois a lista sempre terá pelo menos 
a cabeça). Você verificará esse fato por si mesmo lendo o restante 
dessa seção.
A seguir, vamos apresentar algoritmos para busca, inserção e 
remoção em uma lista ligada. Na próxima seção introduziremos outros 
tipos de lista, ainda mais flexíveis para a realização das operações de 
inserção e remoção.
Busca
Suponha que desejamos verificar se um inteiro x pertence a 
uma lista L. Caso pertença, desejamos obter um ponteiro para uma 
célula que armazena esse inteiro (pode haver mais de uma). Se não 
pertence, é natural devolver o valor nil. O seguinte algoritmo realiza 
essa tarefa para uma lista sem cabeça. Escreva uma versão para 
uma lista com cabeça:
17
Algoritmos e Estrutura de Dados
algoritmo BUSCA (L, x)
 enquanto L <> nil E info[L] <> x faça
 L←prox[L]
 devolva L
► Recebe uma lista L e um inteiro x. 
► Devolve um ponteiro para uma 
► célula que armazena x, e nil se 
► uma tal célula não existe
Perceba que a corretude desse algoritmo depende da ordem de 
avaliação do teste no laço enquanto, que em nossas convenções é da 
esquerda para a direita. De fato, é preciso testar se L é diferente de 
nil antes de qualquer tentativa de acesso ao endereço apontado por 
essa variável. Também note que esse algoritmo, bastante conciso, é 
correto caso a entrada seja a lista vazia, e que devolve a primeira 
célula que armazena o valor desejado.
Também podemos resolver o problema de forma recursiva:
algoritmo BUSCA-REC (L, x)
 se L = nil então
 devolva nil
 se info[L] = x então
 devolva L
 devolva BUSCA-REC (prox[L], x)
► Recebe uma lista L e um 
► inteiro x. Devolve um ponteiro 
► para uma célula que armazena 
► x, e nil se tal célula não existe
No pior caso (por exemplo, se o elemento não pertence à lista), 
toda a lista é percorrida. Assim, a complexidade pessimista da busca 
em uma lista de n elementos é proporcional a n. Podemos dizer que 
esse algoritmo é O(n).
Inserção
Considere agora a operação de inserção de um inteiro em uma 
lista L. Vamos supor que esse inteiro está armazenado no campo info 
de uma célula, e que o algoritmo recebe um ponteiro M para essa 
célula. A função do algoritmo é, então, realizar alguma manipulação 
de ponteiros para a inserção da célula M na lista.
Pode parecer que essa suposição é artificial. De fato, podemos 
desejar que nosso algoritmo de inserção receba precisamente o inteiro 
a ser inserido, e não uma célula. Essa consideração não chega a ser 
um problema: a fim de inserir um inteiro, aloca-se espaço em memória 
18
Algoritmos e Estrutura de Dados
para a criação de uma nova célula, atribui-se o inteiro recebido ao 
campo info dessa célula recém-criada, e executa-se o algoritmo para 
a inserção de uma célula que vamos descrever a seguir.
A inserção logo após a célula apontada por L (a primeira célula 
da lista) está ilustrada a seguir. O primeiro passo é fazer com que 
o campo prox de M aponte para o campo prox de L. Em seguida, o 
campo prox de L aponta para M.
Essa estratégia sempre funciona para uma lista com cabeça, e para 
uma lista sem cabeça e que não é vazia. O caso de uma lista vazia é 
mais delicado, deve ser tratado à parte e implica na necessidade de 
administrar outras variáveis que apontam para a mesma lista (toda 
variável que aponta para uma lista vazia onde ocorre uma inserção 
deve receber o endereço da célula inserida). O algoritmo completo de 
inserção, para o caso de uma lista com cabeça, é o seguinte:
algoritmo INSERE (L, M)
 prox[M]←prox[L]
 prox[L]←M
► Recebe uma lista com cabeça L 
► e uma célula M. Insere M no começo da 
►lista.
Tenha em mente que uma inserção será visível para todo apontador 
para a lista L, ou seja, nenhuma inconsistência é introduzida. De fato, 
a célula apontada é a cabeça, que é a mesma antes e depois da 
inserção.
A inserção ocorre em tempo constante, O(1). Recorde que a 
inserção em uma lista representada por um vetor pode exigir a cópia 
de blocos de memória, e não é portanto constante no pior caso.
Remoção
Considere finalmente que desejamos remover uma célula de uma 
lista. Essa operação é menos trivial do que as anteriores devido ao 
fato de que, no tipo de lista que estamos estudando, o elemento 
19
Algoritmos e Estrutura de Dados
anterior à uma célula não pode ser acessado a partir da mesma (pois 
uma célula não possui um apontador para o elemento anterior). Como 
“emendar” as duas partes da lista que restam após a remoção?
Uma solução, que sempre funciona para listas com cabeça, 
consiste em fornecer um ponteiro para a célula anterior àquela que será 
removida (ao invés de um ponteiro para a célula que será removida). 
A figura abaixo ilustra essa solução. Se desejarmos remover a célula 
do meio, o algoritmo recebe um ponteiro para a célula da esquerda. A 
remoção consiste então de uma simples atualização de um ponteiro:
Essa atualização se faz em uma linha:
algoritmo REMOVE (M)
 prox[M]←prox[prox[M]]
► Remove a célula prox[M] de uma 
► lista ligada
Note que a informação do início da lista é irrelevante para essa 
operação.
A remoção de uma célula esconde uma questão: o que fazer com a 
célula removida? Normalmente, o programador tem o dever de liberar 
explicitamente a memória ocupada por essa célula (caso contrário, 
seu programa utilizará regiões de memória). Em uma linguagem com 
coleta de lixo, como o Java, essa liberação é automática.
Uma questão mais elaborada é a remoção de um inteiro do 
conjunto. Nesse caso, uma célula representando esse inteiro deve ser 
localizada e em seguida removida. O algoritmo é uma combinação do 
algoritmo de busca com o algoritmo de remoção visto logo acima. A 
diferença de que a busca deve parar na célula anterior à que será 
removida. Ei-lo:
20
Algoritmos e Estrutura de Dados
algoritmo BUSCA-REMOVE (L, x)
 p←L
 q←prox[L]
 enquanto q <> nil E info[q] <> x faça
 p←q
 q←prox[q]
 se q <> nil então
 prox[p] ←prox[q]
► Remove a primeira célula 
► da lista L que armazena x
4. Outros tipos de lista
As listas ligadas que acabamos de descrever são as mais simples 
possíveis, e o caminho é livre para inovações. Você pode inventar 
outros tipos de lista, que se mostrem mais adequados ao problema 
que deseja resolver. Vamos apresentar duas possibilidades populares, 
a lista circular e a duplamente ligada.
Listas circulares
Se fazemos com que o ponteiro da última célula da lista aponte para 
a primeira ao invés de “enterrá-lo”, obtemos uma lista com o aspecto 
de um anel que chamamos de lista circular. Podemosconsiderar listas 
circulares com ou sem cabeça. Eis um exemplo de uma lista circular 
sem cabeça:
Nessa figura, se L é um apontador para a célula qualquer, temos
prox[prox[prox[L]]] = L
Em particular, em uma lista circular que contém apenas uma célula, 
o apontador dessa célula armazena o endereço da mesma.
Em uma lista com cabeça, o apontador da última célula armazena 
o endereço da cabeça. Em uma lista vazia, o apontador da cabeça 
aponta para ela própria.
21
Algoritmos e Estrutura de Dados
Em uma lista circular, é possível visitar todas as células a partir de 
uma célula qualquer (para as listas estudadas anteriormente, isso só 
é possível a partir da primeira célula ou da cabeça). Eis um algoritmo 
que percorre uma lista circular, imprimindo o campo info de cada 
célula. Note que esse algoritmo precisa se recordar de onde partiu:
algoritmo IMPRIME-LISTA (L) 
 se L <> nil então
 M← L
 repita
 imprima info[M]
 M←prox[M]
 até que M = L
► Recebe uma lista circular 
► e imprime seu conteúdo
Inserções e remoções em listas circulares são feitas de forma 
semelhante ao caso das listas estudadas previamente. Na inserção 
em uma lista sem cabeça, é preciso tomar um cuidado adicional no 
caso de inserção em uma lista vazia: o apontador da célula inserida 
deve ser explicitamente definido com o endereço da mesma.
Listas circulares são particularmente convenientes para a operação 
de união de listas, que é uma generalização da operação de inserção 
de uma célula. Por exemplo, a união das listas lineares seguintes
6, 2, 8, 4 e 4, 5, 9
é a seguinte lista de 7 elementos:
6, 2, 8, 4, 4, 5, 9
A operação de união de listas circulares pode ser definida como 
segue: dados ponteiros L e M para listas circulares sem cabeça, 
desejamos inserir M imediatamente após L, obtendo uma nova lista 
circular. O algoritmo devolve um ponteiro para a nova lista.
A união pode ser feita com um simples intercâmbio de ponteiros, 
conforme ilustrado na figura a seguir.
22
Algoritmos e Estrutura de Dados
Eis como se processa essa operação:
algoritmo UNIÃO-LISTA (L, M)
 se L = nil então
 devolva M
 se M = nil então
 devolva L
 X← prox[L]
 prox[L]← prox[M]
 prox[M]← X
 devolva L
► Devolve um ponteiro para a lista circular 
► obtida com a inserção de uma 
►lista circular M após uma lista 
► circular L
Perceba uma característica notável desse algoritmo: a união de 
duas listas é feita com um número constante de operações, ou seja, 
que independe do número de elementos representados. O algoritmo 
também funciona para o caso em que uma das listas ou ambas têm 
apenas um ou mesmo nenhum elemento.
Listas duplamente ligadas
Em uma lista duplamente ligada, cada célula tem dois ponteiros: 
prox, para o próximo elemento, e ant, para o anterior. Um exemplo, 
que também mostra como uma tal lista pode ser ilustrada:
Listas duplamente ligadas também podem ser circulares:
23
Algoritmos e Estrutura de Dados
Conhecer o elemento anterior de cada célula é uma facilidade 
muito útil. Por exemplo, a operação de remoção de uma célula em 
uma lista duplamente ligada é muito mais “limpa” do que a operação 
correspondente para os casos anteriores, pois a remoção pode ser 
feita conhecendo-se um ponteiro para a célula ao invés de um ponteiro 
para a célula anterior.
Por outro lado, toda operação com listas duplamente ligadas exige 
um cuidado adicional na administração dos ponteiros. O caso da 
inserção está ilustrado na figura a seguir. Note que tanto o ponteiro 
para a próxima célula quanto o ponteiro para a anterior devem ser 
atualizados na célula inserida.
Segue a inserção para uma lista duplamente ligada com cabeça 
(circular ou não):
algoritmo INSERE (L, M)
 prox[M]←prox[L]
 prox[L]←M
 ant[M]←L
 ant[prox[M]]←M
► Recebe uma lista duplamente ligada com 
► cabeça L e uma célula M. Insere M no começo 
► da lista.
Eis a operação de remoção, que, como observamos, pode ser feita 
a partir de um ponteiro para a célula a ser removida. Perceba que 
nenhum dado além desse ponteiro é necessário. Recorde também 
que a memória utilizada pela célula removida deve ser liberada após 
a operação.
algoritmo REMOVE (M)
 prox[ant[M]]←prox[M]
 ant[prox[M]]←ant[M]
► Remove uma célula M de uma lista duplamente 
► ligada.
24
Algoritmos e Estrutura de Dados
Para ficar mais claro, que tal desenhar uma figura que ilustra essa 
operação?
Você Sabia?
Você já ouviu falar da linguagem Lisp (seu nome vem de LISt 
Processing)? É uma das mais antigas linguagens de programação 
- foi concebida na década de 1950. Mas é bastante diferente das 
linguagens com que você talvez esteja acostumado, como a C. Tanto 
os dados quanto os programas em Lisp são baseados em listas, que 
podem ser compostas com outras listas para a formação de estruturas 
mais complexas.
A linguagem Lisp é importante em Inteligência Artificial. Se quiser 
aprender Lisp, talvez valha a pena conhecer o célebre editor de textos 
Emacs, onde essa linguagem funciona como uma extraordinária 
ferramenta de extensão.
Conheça Mais
Listas ligadas são um assunto muito fundamental em Computação 
e há uma vasta bibliografia que trata do assunto. Recomendamos em 
particular:
 Wirth, N. Algoritmos e Estruturas de Dados. Rio de Janeiro: 
Ed. Prentice Hall do Brasil, 2002.
 Feofiloff, P. Algoritmos em linguagem C. Ed. Campus/Elsevier. 
2008
Você também encontrará um vasto material na Internet a respeito.
É muito interessante que você compreenda como implementar 
e manipular listas em uma linguagem de programação. Estude em 
particular as linguagens C e Java. Duas referências básicas para 
essas linguagens são as seguintes:
 Kernighan, B, Ritchie, D. C - A Linguagem de Programação 
Padrão ANSI. Ed. Campus/Elsevier. 1989
25
Algoritmos e Estrutura de Dados
 Deitel, H. M., Deitel, P. J. Java: Como Programar. Ed. Prentice-
Hall, 2005
Se você não conhece a linguagem Java, é uma excelente 
oportunidade para aprender. A implementação de classes para 
os diversos tipos de listas vai auxiliá-lo de quebra a entender 
programação orientada a objetos. Nos exercícios propostos a seguir, 
busque implementar suas soluções numa dessa linguagens.
Atividades e Orientações de Estudo
O exercício a seguir vai auxiliá-lo a ganhar experiência com a 
manipulação de listas ligadas. Você pode assumir que em todos os 
casos as listas em questão são com cabeça a menos que o contrário 
seja explicitamente dito. Você encontrará muitos outros exercícios nas 
referências bibliográficas.
Problema 1
Escreva um algoritmo que devolve o elemento mínimo de uma lista. Faça duas 
versões, uma para listas circulares que não têm cabeça, outra para listas que não 
são circulares. Qual a complexidade de seu algoritmo?
Problema 2
Escreva um algoritmo que devolve o último elemento de uma lista (o caso de uma 
lista duplamente ligada é muito elementar; considere que a lista não é duplamente 
ligada).
De forma mais geral, escreva um algoritmo que devolve o k-ésimo elemento de 
uma lista. Qual a complexidade do seu algoritmo?
Problema 3
Escreva um algoritmo que inverte uma lista ligada sem usar espaço auxiliar, ou 
seja, apenas alterando ponteiros. Repita o exercício para uma lista circular e uma 
lista duplamente ligada circular.
Problema 4
Escreva um algoritmo que devolve a soma de uma lista ligada de inteiros.
26
Algoritmos e Estrutura de Dados
Problema 5
Escreva um algoritmo que faz a união de duas listas ligadas não necessariamente 
circulares.
Problema 6
Escreva um algoritmo que busca um inteiro em uma lista em ordem crescente.
Problema 7
Escreva um algoritmo que ordena uma lista de inteiros.
Problema 8
Escreva um algoritmo que recebe uma lista ligada de inteiros em ordem crescente,um inteiro (ou um ponteiro para uma célula representando um inteiro), e insere 
esse inteiro mantendo a ordenação.
Problema 9
Escreva um algoritmo que recebe duas listas de inteiros ordenadas e constrói uma 
nova lista que representa a intercalação das duas sequências. Seu algoritmo não 
usa espaço auxiliar, mas faz isso alterando convenientemente os ponteiros das 
listas. Veja o módulo anterior para uma descrição da operação de intercalação.
Problema 10
Implemente as funções de inserção, remoção, busca e mínimo para um conjunto 
dinâmico de inteiros usando listas ligadas. Programe também uma interface 
simples que exibe o conteúdo do conjunto e apresenta ao usuário um menu 
para a escolha de uma operação. Decida a linguagem de programação com seu 
tutor.
Vamos Revisar?
Estudamos neste capítulo a estrutura de lista ligada, onde 
elementos de um conjunto dinâmico são representados na memória 
de um computador com o auxílio de ponteiros. Estudamos as 
operações de inserção, busca e remoção em listas, bem como suas 
complexidades. Também consideramos dois tipos bastante úteis de 
lista, as listas circulares e as listas duplamente ligadas.
27
Algoritmos e Estrutura de Dados
Capítulo 2 – Pilhas
Vamos conversar sobre o assunto?
Se inserções e remoções podem ser realizadas em apenas uma 
extremidade de uma lista linear, temos uma pilha. O nome dessa 
estrutura de dados é uma analogia com pilhas de pratos ou livros, onde 
só podemos inserir ou retirar um novo item na extremidade superior. 
Também podemos dizer que uma pilha é um conjunto dinâmico onde 
só podemos remover o último elemento inserido.
Qual a utilidade dessa disciplina particular de inserções e 
remoções? Muitas. Encontramos frequentemente problemas em 
Computação que podem ser modelados em uma estrutura de pilha. 
Um exemplo importante é o gerenciamento de memória durante a 
execução de um programa. Quando uma função é chamada, o estado 
da memória (o conjunto das variáveis definidas pelo programa e o ponto 
de execução antes da chamada da função) devem ser armazenados, 
para que a execução retome esse mesmo estado após o término 
da execução da função. E o que acontece se várias funções são 
executadas, cada uma dentro de outra mais externa, como é o caso 
de funções recursivas? Esses estados de memória são empilhados 
e, posteriormente, desempilhados. Essa técnica é tão importante que 
certos processadores possuem registradores normalmente dedicados 
ao gerenciamento de uma estrutura de pilha.
Como vemos, o conceito de pilha é bastante natural. Vamos neste 
capítulo aprender como implementar pilhas em vetores e em listas 
ligadas, e adquirir alguma experiência com essa estrutura através de 
algumas aplicações.
Bom estudo!
1. Definição de pilha
A estrutura de dados pilha é semelhante a uma pilha de pratos ou 
livros. Você não ousará retirar ou enfiar livros no meio de uma pilha, 
a menos que queira correr o risco de um desastre. Há um único local 
seguro para fazer isso: o topo da pilha.
28
Algoritmos e Estrutura de Dados
Em Computação, não empilhamos livros ou pratos, mas sim 
dados. Essa é da definição de pilha: uma lista linear (de inteiros, 
por exemplo) onde inserções e remoções só podem ser realizadas 
em uma extremidade. Dando nomes aos bois, essa extremidade é 
chamada topo, e uma pilha P suporta duas operações básicas:
• EMPILHA (P, x): insere o elemento x na pilha, ou seja, após o 
topo (o novo topo é a posição do elemento inserido);
• DESEMPILHA (P): retira o elemento no topo da pilha (o novo 
topo é o elemento anterior ao retirado).
Perceba que em uma pilha o último elemento a entrar, aquele que 
está na estrutura há menos tempo, é o primeiro a sair. Há uma sigla 
em inglês popular para descrever esse comportamento: dizemos que 
pilhas são estruturas LIFO, de last-in, first-out.
É claro que a operação desempilha só faz sentido se a pilha não 
estiver vazia. O empilhamento a princípio sempre é possível, mas em 
certas implementações um limite para o tamanho da pilha é imposto. É 
o caso de implementação com vetores, que estudaremos na próxima 
seção.
Atenção
Na literatura em 
inglês, pilha é 
“stack”, empilha 
é “push” e 
desempilha é 
“pop”.
29
Algoritmos e Estrutura de Dados
2. Implementando uma pilha em um vetor
Podemos representar uma pilha de no máximo N elementos 
em um vetor P de tamanho N. A cada instante, os elementos são 
armazenados da posição 1 até uma posição t, o topo da pilha. A pilha 
está vazia se t = 0 e cheia se t = N. Eis um vetor que representa uma 
pilha de 5 elementos, e para o qual N = 7:
Algumas operações nessa pilha:
• EMPILHA (P, 73)
• DESEMPILHA (P)
• EMPILHA (P, 52)
• EMPILHA (P, 38)
O que acontece se um novo empilhamento é realizado na última 
pilha do exemplo acima? Ocorre um transbordamento (em inglês, 
overflow). Essa situação é anormal, e em um programa correto não 
30
Algoritmos e Estrutura de Dados
deveria ocorrer nunca. Também é anormal tentar desempilhar de uma 
pilha vazia (situação em inglês conhecida como underflow).
É preciso ficar claro que, mesmo que em um vetor temos acesso 
automático a qualquer posição, não faz sentido espiar os elementos 
de uma pilha abaixo do topo. De fato, só vamos usar uma pilha em 
aplicações onde o único elemento relevante é aquele que está no 
topo – senão, usamos outra estrutura.
Vamos concluir essa seção com código em Portucal para as 
operações empilha e desempilha de uma pilha de inteiros. Também 
importa termos funções para testar se uma pilha está cheia, vazia e 
obter o elemento no topo de uma pilha. Cada uma dessas operações 
é executada em complexidade constante.
Para simplificar, vamos admitir que uma pilha é um registro que 
engloba o vetor, o topo da pilha, e o número máximo de elementos; 
também vamos usar a mesma letra para denotar um ponteiro para 
esse registro e o vetor que armazena a pilha. Assim, para acessar a 
posição do topo e o tamanho de uma pilha P, escrevemos
topo[P], N[P]
e para acessar o elemento no topo escrevemos
P[topo[P]]
Fica claro aqui, mais uma vez, a utilidade do uso de registros (ou estruturas, 
ou classes – depende da linguagem) que encapsulam as propriedades 
relevantes de uma pilha em uma unidade lógica. De fato, quando desejamos 
passar uma pilha para uma função, basta passar um ponteiro para esse 
registro ao invés de três argumentos (um para o vetor, outro para o topo 
e um terceiro para o número máximo de elementos). Muito mais simples, 
claro e seguro.
A partir daqui, habitue-se a pensar em termos de registros, estruturas ou 
classes para implementação de estruturas de dados.
Enfatizamos que o topo será a única posição acessada na pilha 
(como acabamos de comentar, não se deve bisbilhotar o interior de 
uma pilha).
Não vamos incluir nesse código um tratamento explícito para 
a ocorrência de overflow. O caso de underflow na operação de 
desempilhamento pode ser detectado a partir do retorno da função. 
Lembrete
Em programação 
orientada a 
objetos (o 
paradigma 
adotado na 
linguagem Java, 
entre outras) 
as operações 
descritas a 
seguir seriam 
normalmente 
codificadas na 
própria classe 
pilha, e não em 
funções avulsas
31
Algoritmos e Estrutura de Dados
Em uma implementação robusta para aplicações práticas, essas 
situações de exceção, se detectadas, devem resultar em um código 
de erro ou disparar um tratamento adequado.
algoritmo VAZIA (P)
 se topo [P] = 0 então
 devolva V
 senão
 devolva F
► Testa se uma pilha está vazia
algoritmo CHEIA (P)
 se topo [P] = N[P] então
 devolva V
 senão
 devolva F
► Testa se uma pilha está cheia
algoritmo EMPILHA (P, x)
 se NÃO VAZIA (P) então
 topo[P] ←topo[P] + 1
 P[topo[P]]←x
►Empilha um inteiro x em uma pilha P
algoritmo DESEMPILHA(P)
 se NÃO VAZIA (P) então
 x ←P [topo[P]]
 topo[P] ←topo[P] - 1
 devolva P[topo[P]]
 devolva nil
► Desempilha o elemento no topo de uma pilha P 
Um comentário sobre a função DESEMPILHA. Note que não é 
necessário “apagar” o elemento desempilhado do vetor. De fato, o que 
está acima do topo não tem relevância para a pilha, e assim, basta 
32
Algoritmos e Estrutura de Dados
diminuir o topo de uma unidade. Também atente para o fato de que a 
função DESEMPILHA devolve o elemento no topo da pilha, e caso a 
pilha esteja vazia, retorna um valor que permite identificar o erro (nil, 
que é diferente de todo inteiro). O mesmo ocorre na função a seguir:
algoritmo TOPO (P)
 se NÃO VAZIA (P) então
 devolva P[topo[P]]
 devolva nil
► Devolve o elemento no topo de uma pilha P
Nos exercícios propostos deste capítulo, queremos convidá-lo a 
implementar essas funções em uma linguagem de programação.
3. Implementando uma pilha em uma lista 
ligada
Também podemos implementar uma pilha em uma lista ligada 
com cabeça, não necessariamente circular nem duplamente ligada. O 
topo da pilha é o primeiro elemento da lista após a cabeça. A pilha é 
acessada a partir de um ponteiro para a cabeça.
Vejamos um exemplo. A figura abaixo apresenta uma pilha, P, e o 
empilhamento de uma célula. Antes do empilhamento o topo contém 
o número 5. 
A vantagem da representação com uma lista é a inexistência de 
um limite superior para o tamanho da pilha (exceto evidentemente o 
tamanho da memória), graças à alocação dinâmica de espaço. Em 
particular, a função CHEIA descrita na seção anterior não faz sentido 
aqui. Quando a pilha está vazia? Quando o ponteiro da cabeça vale 
nil.
33
Algoritmos e Estrutura de Dados
Segue a descrição das operações fundamentais de uma pilha 
implementada como uma lista. Todas têm complexidade constante.
algoritmo VAZIA (P)
 se prox[P] = nil então
 devolva V
 senão 
 devolva F
► Testa se uma pilha está vazia
algoritmo EMPILHA (P, M)
 prox [M] ←prox [P]
 prox [P] ← M
► Empilha uma célula M em uma pilha P
algoritmo DESEMPILHA (P)
 se NÃO VAZIA (P) então
 M ←prox [P]
 prox [P] ←prox[M]
 devolva M
 devolva nil
► Desempilha o elemento no topo de uma pilha P 
algoritmo TOPO (P)
 se NÃO VAZIA (P) então
 devolva info[prox[P]]
 devolva nil
►Devolve o elemento no topo de uma pilha P
Aprenda Praticando
Vamos estudar uma aplicação da estrutura de pilha, desenvolvendo 
uma calculadora para expressões aritméticas em notação posfixa.
Quanto vale a expressão seguinte?
5 – 2 + 4
34
Algoritmos e Estrutura de Dados
Depende da ordem das operações. Se a soma é aplicada primeiro, 
o resultado é -1. Senão, é 7. Para evitar ambiguidades, o uso de 
parênteses é necessário.
 Esse tipo de expressão onde o operador (soma, produto...) é 
escrito entre os operandos (números) é chamado de notação infixa 
(vamos considerar apenas operadores binários, como os aritméticos). 
Não é a única maneira de escrever uma expressão aritmética. Na 
notação posfixa, o operador vem após os operandos.
Eis a soma de 2 e 4 em notação posfixa:
2 4 +
Uma expressão mais complicada:
5 2 4 + -
Como interpretá-la?
• leia a expressão da esquerda para a direita, armazenando os 
números na ordem da leitura;
• tão logo encontre um operador, aplique-o aos dois números 
mais à direita, ou seja, os dois últimos armazenados (em uma 
expressão correta, sempre haverá dois operandos quando um 
operador é encontrado);
• sempre que uma operação é realizada, retire os operandos e 
armazene o resultado. Continue a leitura.
Em nosso exemplo, após a leitura dos números 5, 2 e 4, chegamos 
ao operador de soma. Fazemos então a soma de 2 e 4, que são os 
dois últimos que foram armazenados. O resultado é 6. Após retirar 
os números 2 e 4, armazenamos esse resultado, obtendo a seguinte 
configuração:
5 6
(note que não bisbilhotamos os dados armazenados anteriormente; 
simplesmente eles continuam lá).
Continuando a leitura, encontramos o operador -, que é aplicado 
finalmente a 5 e 6. O resultado é -1. Em notação infixa, acabamos de 
calcular o seguinte:
5 - (2 + 4)
Note que a ordem dos operandos é a mesma nas duas notações.
Lembrete
A notação 
posfixa também 
é chamada de 
notação polonesa 
reversa. Isso 
em homenagem 
ao matemático 
polonês Jan 
Lukasiewicz, 
que inventou na 
década de 1920 a 
notação prefixa: 
o operador é 
escrito antes dos 
operandos.
35
Algoritmos e Estrutura de Dados
A expressão que corresponde a (5 – 2) + 4 é
5 2 – 4 +
Que tal calcular o resultado dessa expressão usando o mesmo 
processo? Também perceba que não foi necessário usar parênteses 
para distinguir entre uma e outra. De fato, uma das vantagens da 
notação posfixa é que ela não admite ambiguidades, dispensando 
assim o uso de parênteses.
Talvez você tenha percebido que podemos usar uma pilha para 
calcular o resultado de uma expressão em notação posfixa. Traduzindo 
as instruções acima:
• leia a expressão da esquerda para a direita;
• encontrando um número, empilhe-o;
• encontrando um operador, desempilhe dois operandos, e 
empilhe o resultado da operações com esses operandos.
Nosso objetivo é descrever esse algoritmo. Estaremos assim 
simulando uma calculadora baseada na notação posfixa.
Antes de começar, vamos fixar algumas convenções. A expressão 
é fornecida pelo usuário item após item, e a leitura continua até a 
entrada de um código de finalização: qualquer valor diferente de um 
operador e um número. Os operadores considerados são +, -, * e /. 
Vamos supor que a expressão é correta e que não ocorre divisão por 
zero.
Para simplificar, vamos supor a existência de uma função que 
testa se uma variável representa um número, chamada NUMERO, e 
de uma função que testa se uma variável representa um operador, 
chamada OPERADOR. Também vamos supor que dispomos de uma 
implementação de pilha e das operações EMPILHA e DESEMPILHA. 
Não é importante se essa pilha é implementada com vetores ou listas 
ligadas. Esse detalhe está escondido de nosso algoritmo.
Lembrete
A notação 
polonesa reversa 
tornou-se 
bastante popular 
na década de 
1960 após ser 
adotada em 
alguns modelos 
de calculadoras 
científicas.
36
Algoritmos e Estrutura de Dados
algoritmo CALCULADORA-POSFIXA (P)
 inicialize P como uma pilha de inteiros vazia
 repita
 leia c
 se NUMERO (c) então
 EMPILHA (P, c)
 senão
 se OPERADOR (c) então
 r = DESEMPILHA (P)
 l = DESEMPILHA (P)
 se c = + então
 EMPILHA(P, l + r) 
 se c = - então 
 EMPILHA (P, l - r) 
 se c = * então 
 EMPILHA (P, l * r) 
 se c = / então
 EMPILHA (P, l / r) 
até que NÃO NUMERO (c) E NÃO OPERADOR (c)
imprima DESEMPILHA (P)
► Imprime o resultado de 
► uma expressão em 
► notação posfixa
Perceba que no começo desse código solicitamos a criação de uma 
pilha vazia. Em uma linguagem como o C e o Pascal, essa instrução 
corresponde à alocação de memória para uma estrutura do tipo pilha. 
Em uma linguagem como o Java, trata-se da criação de um objeto da 
classe pilha.
Agora é com você. Nos exercícios propostos, você terá a 
oportunidade de aplicar a estrutura de pilha para a solução de outros 
problemas igualmente interessantes.
37
Algoritmos e Estrutura de Dados
Atividades e Orientações de Estudo
A principal atividade proposta nesse capítulo é o desenvolvimento 
de soluções baseadas na estrutura de pilha. É muito interessante 
que você tente implementar suas respostas em uma linguagem de 
programação. O primeiro exercício segue esse espírito.
Problema 1
Implemente em C ou Java a estrutura de pilha e as operações correspondentes. 
Escolha entre implementação com vetores ou lista ligada.Em seguida, implemente a calculadora de expressões em notação posfixa usando 
sua pilha. Teste intensivamente sua implementação.
Problema 2
Simule a execução da calculadora posfixa para as seguintes expressões:
5 2 – 4 +
8 6 2 * 4 7 + - *
1 2 3 4 - - -
Problema 3
Escreva um algoritmo que testa se uma expressão envolvendo parênteses e 
colchetes é bem formada. Em uma expressão bem formada, todo parênteses 
aberto deve ser fechado mais à direita. Ademais, tudo o que está entre a abertura 
e o fechamento também é uma expressão bem formada. O mesmo vale para 
colchetes.
Por exemplo, a seguinte expressão é bem formada:
 ( ) ( [ ( ) [ ] ] ( ) ] )
A seguinte não:
 ( [ ) ]
Qual é o maior tamanho que a pilha pode atingir, em função do comprimento da 
expressão? Dê um exemplo de expressão onde esse valor é atingido.
38
Algoritmos e Estrutura de Dados
Problema 4
Escreva um algoritmo que lê uma sequência de caracteres e imprime seu reverso, 
ou seja, a mesma sequência lida da direita para a esquerda.
Problema 5 (Desafio)
Escreva um algoritmo que lê uma expressão aritmética em notação infixa e imprime 
a expressão correspondente em notação posfixa. Suponha que a expressão lida 
é bem-formada e não-ambígua, ou seja, contém parênteses que indicam a ordem 
das operações. Deixe bem claro outras suposições sobre as quais repousa 
sua solução. Dica: use uma pilha de operadores e parênteses; operandos não 
precisam ser empilhados, e são impressos imediatamente (recorde que a ordem 
dos operadores é a mesma em ambos os tipos de expressão).
Conheça Mais
A estrutura de pilha é estudada em detalhes no primeiro volume da 
série The Art of Computer Programming de Donald Knuth:
 Knuth, D. The Art of Computer Programming. Volume 1: 
Fundamental Algorithms. Massachusetts: Addison-Wesley, 
1997.
Vale a pena consultar essa referência. Você encontrará em 
particular exercícios excelentes, alguns bastante desafiadores.
Consulte também
 Feofiloff, P. Algoritmos em linguagem C. Ed. Campus/Elsevier. 
2008
Vamos Revisar?
Estudamos neste capítulo a estrutura de pilha: listas lineares 
onde inserções e remoções só ocorrem em uma das extremidades. 
Descrevemos implementações de uma pilha com vetores e com listas 
ligadas, e estudamos uma aplicação, a avaliação de uma expressão 
aritmética em notação posfixa.
39
Algoritmos e Estrutura de Dados
Capítulo 3 – Filas
Vamos conversar sobre o assunto?
Filas são outro tipo de lista linear com uma importância particular 
em aplicações. Filas modelam muitas situações práticas como 
escalonamento de processos em sistemas operacionais, determinação 
do caminho mínimo em redes e gerenciamento de requisições em 
um ambiente de recursos compartilhados, para citar três exemplos 
tradicionais. Em uma fila, inserções e remoções só ocorrem nas 
extremidades da lista, e em extremidades diferentes. Essa disciplina 
funciona exatamente como uma fila de banco.
Este capítulo segue o mesmo espírito do anterior. Vamos introduzir 
o conceito de fila, as operações fundamentais em uma fila e discutir 
possíveis implementações. No final, você será convidado a se 
familiarizar com essa estrutura através de exercícios. Aproveite bem!
1. Definição de fila
Em uma fila de banco, os clientes entram no final da fila, e saem 
no início. Atende-se primeiro quem esperou mais tempo.
A estrutura de dados fila obedece à mesma política. Uma fila é 
uma lista linear onde elementos só podem ser inseridos em uma 
extremidade, o final da fila, e retirados na outra, a frente da fila. Por 
isso, dizemos que uma fila é uma estrutura FIFO, do inglês First In 
First Out (primeiro a chegar primeiro a sair). Perceba a diferença com 
Atenção
Felizmente, em 
Computação 
ninguém fura a 
fila.
40
Algoritmos e Estrutura de Dados
relação à estrutura de pilha: numa pilha, sai o último que chegou.
Por exemplo, considere a lista linear de inteiros a seguir.
54, 72, 37, 42
Fixemos o final da fila na extremidade à direita. Então a inserção 
de 25 leva à configuração
54, 72, 37, 42, 25
Só um elemento pode ser removido, o 54, que está na frente da 
fila. Sua remoção leva à configuração
72, 37, 42, 25
Vamos em seguida estudar como implementar uma fila e as 
operações de inserção e remoção usando um vetor, e em seguida 
usando uma lista ligada.
2. Implementação de uma fila num vetor
Podemos implementar uma fila em um vetor com o auxílio de duas 
variáveis, frente e final. A fila ocupa uma fatia de posições consecutivas 
do vetor, e essas variáveis indicam os limites dessa fatia. Se o vetor 
tem tamanho n, a fila terá no máximo n – 1 elementos – a razão ficará 
clara ao longo da explicação.
No exemplo a seguir, a frente da fila está na posição 3, e o final na 
posição 6. Perceba que o valor da variável final é uma posição após o 
último elemento da fila – novamente, a razão ficará clara em breve. As 
demais posições do vetor não têm nada a ver com a fila.
Fazendo-se inserções e remoções, a fila caminha ao longo do 
vetor. Por exemplo, se inserimos o elemento 36 na fila e fazemos em 
seguida uma remoção, obtemos
O que ocorre se a variável final atinge a última posição do vetor? 
Lembrete
Em inglês, 
fila é queue, e 
as operações 
de inserção e 
remoção são 
comumente 
chamadas 
de enqueue 
e dequeue, 
respectivamente.
41
Algoritmos e Estrutura de Dados
Em nosso exemplo, chegamos a essa situação se inserimos mais dois 
números na fila, digamos, 26 e 48:
Poderíamos dizer que a fila está cheia. Mas ainda há espaço no 
vetor! A solução para aproveitar esse espaço é voltar ao início do 
vetor, como se a primeira posição fosse a continuação da primeira.
Por exemplo, se inserimos o inteiro 72 na configuração acima, 
obtemos
Em seguida, se inserimos o inteiro 68 obtemos
A fila começa na posição 4, vai até o final do vetor, e volta ao início, 
terminando na primeira posição.
Remoções também obedecem à técnica de voltar ao início. 
Considere a configuração a seguir, onde a frente da fila está na última 
posição do vetor:
A remoção de um elemento leva então à seguinte configuração:
É instrutivo visualizar essa implementação de fila como um anel, 
entortando o vetor de forma a colar a última posição na primeira. 
Esse tipo de estrutura é chamada de vetor circular, ou buffer circular. 
Um vetor circular não tem extremidades, não tem fim, como é o caso 
de um vetor comum. As inserções e remoções fazem com que a fila 
42
Algoritmos e Estrutura de Dados
caminhe ao longo dessa estrutura circular.
Vejamos um exemplo. Considere o vetor a seguir:
O vetor circular correspondente é
Podemos agora explicar o porquê de assumir que o último 
elemento da fila está na posição anterior àquela indicada pela variável 
final. Essa convenção é útil para que possamos detectar se a fila está 
cheia ou vazia. A fila está vazia quando
frente = final
e cheia quando
frente = final + 1 ou frente = 1 e final = N
Se admitimos que a variável final indica a última posição com um 
elemento da fila, não podemos fazer a distinção entre essas duas 
situações (procure se certificar da razão).
Antes de implementarmos as operações de inserção e remoção 
nessa estrutura, cabe uma reflexão sobre como acessar a posição 
seguinte a uma posição k num vetor circular. Vamos supor que o vetor 
tem tamanho N. Se k < N, então a próxima posição é k + 1. O caso 
delicado ocorre quando k = N. Neste caso, a próxima posição não é 
mais k + 1, mas sim a primeira. Assim, podemos descobrir a próxima 
posição com um teste condicional.
Também é possível calcular a próxima posição diretamente, em 
uma única fórmula. A resposta está no uso do resto da divisão inteira, 
43
Algoritmos e Estrutura de Dados
que em Portucal é dado pelo operador mod (consulte a descrição da 
linguagem noprimeiro módulo). Se k < N, então k mod N é igual a k, 
se k = N, então k mod N é igual a 0. Assim, a expressão seguinte 
fornece a próxima posição para qualquer situação:
(k mod N) + 1
Usando essa técnica, também podemos decidir se a fila está cheia 
com um único teste:
frente = (final mod N) + 1
No código a seguir, vamos considerar uma fila como um registro 
(ou uma estrutura, ou um objeto) que além do vetor circular engloba 
as variáveis N (o tamanho do vetor), frente e final. Como fizemos no 
estudo da implementação de pilhas em vetores, não incluiremos um 
tratamento explícito de erros (overflows e underflows).
algoritmo VAZIA (Q)
 se frente[Q] = final[Q] então
 devolva V
 senão
 devolva F
► Testa se uma fila está vazia
algoritmo CHEIA (Q)
 se frente[Q] = (final[Q] MOD N[Q]) + 1 então
 devolva V
 senão
 devolva F
► Testa se uma fila 
► implementada em um 
► vetor circular está cheia
algoritmo ENTRA-FILA (Q, x)
 se NÃO CHEIA (Q) então
 Q[final[Q]] ← x
 final[Q] ← (final[Q] MOD N[Q]) + 1
► Insere um elemento numa fila
44
Algoritmos e Estrutura de Dados
algoritmo SAI-FILA (Q)
 se NÃO VAZIA (Q) então
 x ← Q[frente[Q]]
 frente[Q] ← (frente[Q] MOD N[Q]) + 1
 devolva x
 devolva nil
► Remove um elemento de uma 
► fila
Vamos em seguida discutir a implementação de uma fila com listas 
ligadas.
3. Implementação de uma fila numa lista 
ligada
Podemos implementar uma fila com uma lista com cabeça. O 
primeiro elemento da fila é a célula após a cabeça. Vamos supor que 
essa lista é uma estrutura que engloba dois ponteiros, frente, que 
aponta para a cabeça (e não para o primeiro elemento, que vem após 
a cabeça), e final, que aponta para o último elemento. A fila está vazia 
quando final aponta para a cabeça, ou seja, quando final = frente.
A figura a seguir ilustra uma fila, uma operação de inserção e uma 
remoção.
Confira a seguir as operações de inserção, remoção e teste do vazio 
para essa implementação. Novamente, não vamos nos preocupar 
nesses exemplos com o tratamento de situações de exceção. Todas 
as operações têm complexidade constante.
45
Algoritmos e Estrutura de Dados
algoritmo VAZIA (Q)
 se frente[Q] = final[Q] então
 devolva V
 senão
 devolva F
► Testa se uma fila está vazia
algoritmo ENTRA-FILA (Q, M)
 prox[final[Q]] ← M
 final[Q] ← M
► Insere uma célula, M, numa fila
algoritmo SAI-FILA (Q)
 se NÃO VAZIA (Q) então
 x = prox[frente[Q]]
 se prox[frente[Q]] = final[Q] então
 final[Q] = frente[Q]
 prox[frente[Q]] ← prox[x]
 devolva x
 devolva nil
► Remove um elemento de uma 
► fila
Como já mencionamos, a memória ocupada por uma célula 
removida deve ser devolvida ao sistema. Note que a remoção de 
um elemento exige um tratamento especial para o caso de uma fila 
com um único elemento (o ponteiro final deve receber o endereço da 
cabeça).
Há outras maneiras de se implementar uma fila. Nos exercícios, 
você será convidado a estudar uma alternativa.
Aprenda Praticando
Vamos nos aquecer no uso de filas com um exercício que envolverá 
também a estrutura de pilha. Além da experiência com as operações 
dessas estruturas, esse exemplo discute uma solução para um 
46
Algoritmos e Estrutura de Dados
problema, enunciado no parágrafo a seguir. Que tal tentar soluciona-
lo antes de ler o restante da seção?
Nosso objetivo é implementar uma fila utilizando duas pilhas. Ou 
seja, só dispomos dessas pilhas como meio de armazenamento, e 
desejamos manipulá-las de forma a reproduzir o comportamento de 
uma fila. Do ponto de vista do usuário, essa implementação ficará 
escondida, as operações de inserção obedecerão à política que define 
uma fila.
Vamos implementar a solução descrita no volume 1 (Fundamental 
Algorithms) da coleção “The Art of Computer Programming”, de D. 
Knuth (Seção 2.2.1, Exercício 14). Chamemos as pilhas de R e S. A 
solução consiste em enxergar a fila começando no topo de R, indo 
até a base, e em seguida continuando da base de S até o topo de S. 
A frente da fila é o topo de R, o final o topo de S. Inserções na fila são 
empilhamentos em S, remoções são desempilhamentos em R.
A figura a seguir ilustra essa situação, para uma fila Q que 
armazena os inteiros
53, 71, 64, 34, 17
Há uma situação que exige um tratamento especial, o caso em 
que a pilha R fica vazia após uma remoção. Nesse caso, todos os 
elementos de S são imediatamente desempilhados e empilhados em 
R, na ordem. Se S também está vazia, situação que corresponde à 
fila vazia, a próxima inserção deve ser um empilhamento diretamente 
em R, ao invés de S. Note que, para testar se a fila está vazia, basta 
testar se R está vazia.
Segue a implementação dessa solução. Vamos considerar que 
uma fila é uma estrutura que comporta duas pilhas, R e S, acessíveis 
com as construções R[Q] e S[Q]. 
47
Algoritmos e Estrutura de Dados
algoritmo VAZIA (Q)
 se VAZIA[R[Q]] então
 devolva V
 senão
 devolva F
► Testa se uma fila implementada com duas 
► pilhas está vazia
algoritmo ENTRA-FILA (Q, x) 
 se VAZIA[R[Q]] então
 EMPILHA (R[Q], x)
 senão
 EMPILHA (S[Q], x)
► Insere x em uma fila implementada 
► em duas pilhas
algoritmo SAI-FILA (Q)
 se NÃO VAZIA (Q) então
 x ← DESEMPILHA (R[Q])
 se VAZIA (R[Q]) então
► Remove um elemento 
► de uma fila
 enquanto NÃO VAZIA (S[Q]) faça
 EMPILHA (R[Q], DESEMPILHA (S[Q]))
 devolva x
 devolva nil
Uma nota sobre a eficiência dessa solução. A complexidade de 
uma inserção é constante, mas a de uma remoção, no pior caso, não 
é: o pior caso ocorre quando a pilha R fica vazia, o que implica em 
uma cópia dos elementos de S em R.
Por outro lado, se contamos o número médio de operações 
realizadas ao longo de uma sequência de inserções e remoções, 
vamos nos deparar com um comportamento interessante: esse valor 
não depende do número de elementos. A razão é que cada elemento é 
empilhado no máximo duas vezes, e desempilhado também no máximo 
duas vezes (duas em cada pilha). Essa contagem de operações ao 
longo do tempo é chamada de complexidade amortizada. Podemos 
dizer que a complexidade amortizada das operações de inserção e 
remoção em nossa implementação é constante.
48
Algoritmos e Estrutura de Dados
Conheça Mais
As mesmas referências citadas no capítulo anterior servem como 
fonte de consulta sobre filas. Encontraremos outros detalhes de 
implementação, aplicações e exercícios no primeiro volume da série 
The Art of Computer Programming de Donald Knuth:
 Knuth, D. The Art of Computer Programming. Volume 1: 
Fundamental Algorithms. Massachusetts: Addison-Wesley, 
1997.
O mesmo comentário vale para
 Feofiloff, P. Algoritmos em linguagem C. Ed. Campus/Elsevier. 
2008
As estruturas de pilha e fila são muito tradicionais. Além das 
referências mencionadas nesse módulo, qualquer livro sobre 
Estruturas de Dados trata do assunto. Claro que a qualidade e 
profundidade do tratamento pode variar.
Atividades e Orientações de Estudo
Propomos abaixo uma lista de exercícios que segue o mesmo 
espírito daqueles propostos em nosso estudo sobre pilhas. Novamente, 
é muito interessante que você tente implementar suas respostas em 
uma linguagem de programação.
Problema 1
Implemente em uma linguagem de programação “real” uma fila e as operações 
discutidas neste capítulo. Você pode escolher entre implementação sequencial ou 
ligada. Teste intensivamente sua implementação com sequências interessantes 
de inserções e remoções.
Problema 2
Escreva uma função que calcula em complexidade constante (sem percorrer a 
estrutura) o tamanho de uma fila implementada num vetor circular.
49
Algoritmos e Estrutura de Dados
Problema 3
Considere uma implementação de filas emuma lista ligada circular onde não 
dispomos de um ponteiro para o último elemento. Descreva como a operação 
de inserção pode ser realizada em complexidade constante, ou seja, sem uma 
busca pelo último elemento. Você tem o direito de criar uma nova célula para 
representar a cabeça.
Problema 4
Uma fila dupla ou deque (do inglês double end queue) é uma lista onde tanto 
inserções quanto remoções são permitidas em ambas as extremidades. Descreva 
uma implementação de um deque, incluindo suas operações fundamentais.
Problema 5
Mostre como uma pilha pode ser implementada usando duas filas. Discuta a 
eficiência de sua solução.
Problema 6
Descreva um algoritmo que recebe duas filas e devolve outra fila consistindo 
da segunda concatenada no final da primeira. Você só tem o direito de usar as 
operações de inserção e remoção disponíveis (ou seja, você não tem acesso à 
implementação dessas filas – não pode mexer nos ponteiros da lista ligada ou nas 
posições do vetor onde as mesmas vivem). Você pode modificar as filas durante 
a realização da operação, mas ao final elas devem ser iguais às recebidas.
Vamos Revisar?
Estudamos neste capítulo a estrutura de fila, listas lineares onde 
inserções ocorrem em uma extremidade e remoções em outra. 
Descrevemos implementações dessa estrutura em vetores circulares 
e em listas ligadas.
50
Algoritmos e Estrutura de Dados
Capítulo 4 – Árvores
Vamos conversar sobre o assunto?
Neste último capítulo, estudaremos uma nova estrutura de dados 
para a representação de um conjunto dinâmico, as árvores. Como 
acontece com as demais, o conceito de árvore é fundamental em 
Computação e suas aplicações aparecem em muitos domínios, indo 
do corriqueiro ao avançado. Já observou a estrutura do sistema 
de arquivos no seu computador? A organização hierárquica dos 
diretórios lembra uma árvore e seus ramos. Árvores são úteis 
para o armazenamento de dados em bancos de dados e para a 
representação da estrutura sintática de um programa durante o 
processo de compilação, para citar dois exemplos importantes.
Nosso objetivo será introduzir o conceito de árvore (e mais 
especificamente de árvore de busca), três métodos de visita dos 
nós de uma árvore, e algoritmos para inserção, busca e remoção de 
elementos. Constataremos que a eficiência dessas operações no pior 
caso empata com o uso de listas ligadas, mas pode ser muito melhor 
se forem realizadas tomando-se certos cuidados.
Bom estudo!
1. A definição de árvore
Muitas estruturas comuns na Ciência da Computação possuem 
uma estrutura hierárquica, formada por um elemento de origem, que 
podemos chamar de raiz, e ramificações para elementos em níveis 
mais internos. Tais estruturas são o que chamamos de árvores. Eis uma 
representação típica de uma árvore de diretórios num computador:
51
Algoritmos e Estrutura de Dados
A raiz dessa árvore é a pasta na parte superior e representa o 
diretório mais externo, ou seja, aquele a partir do qual a árvore é 
construída. Os subdiretórios dentro desse diretório mais externo 
são desenhados imediatamente abaixo, e são também árvores, que 
representam diretórios mais internos. Dizemos que essas últimas 
são subárvores da árvore original. Que tal verificar uma árvore de 
diretórios por si mesmo em algum computador?
Árvores também são úteis para modelar a estrutura de documentos 
XML e atributos compostos em bancos de dados. A figura a seguir 
apresenta um exemplo. A raiz é o atributo livro, que é composto de 
três subatributos: ISBN, título e autores. O atributo autores, por sua 
vez, tem dois subatributos, ambos chamados de autor.
Segue um exemplo mais simples, uma árvore que representa um 
conjunto de inteiros. Trata-se do tipo de dados que vamos considerar 
nesse texto.
52
Algoritmos e Estrutura de Dados
Analisando esses exemplos com atenção, constatamos que árvores 
são estruturas recursivas, ou seja, são formadas por subestruturas 
do mesmo tipo, mas menores. Esse fato aparece explicitamente na 
definição formal de árvore, que apresentamos a seguir:
Uma árvore é uma coleção de elementos chamados nós, onde se distingue um 
nó chamado raiz, e onde cada nó pode estar associado a zero ou mais nós 
chamados filhos. Formalmente, uma árvore é definida recursivamente como 
segue:
• um único nó é uma árvore; esse nó também é a raiz da árvore;
• se r é um nó e t1, t2, ..., tn são árvores cujas raízes são r1, r2, ..., rn, respectivamente, 
então a união de r com t1, t2, ..., tn, definindo-se como filhos de r os nós 
r1, r2, ..., rn, é uma árvore cuja raiz é r.
Nessa definição, t1, t2, ..., tn são subárvores da árvore enraizada 
em r; toda subárvore de alguém em t1, t2, ..., tn idem. Fixemos outros 
termos técnicos úteis:
• os nós que não possuem nenhum filho são chamados de 
folhas;
• se r é filho de s, dizemos que s é o pai de r;
• cada nó está em um nível: a raiz no nível 0, os filhos da raiz no 
nível 1, etc.;
• a altura de uma árvore é o máximo dos níveis de seus nós.
Nos exemplos a seguir, a raiz é colorida em cinza escuro, seus 
filhos em cinza claro e as folhas são os nós pretos. O número de nós 
da árvore é representado por n, e a altura por h.
53
Algoritmos e Estrutura de Dados
A árvore t1 é formada por um único nó, que é ao mesmo tempo 
a raiz e uma folha. Também note que t3 nada mais é do que uma 
lista linear. De fato, poderíamos dizer que a estrutura de árvore é uma 
generalização das listas, permitindo que cada célula tenha mais de 
um sucessor.
Às vezes é útil incluir na definição a árvore vazia, ou árvore que 
não possui nenhum nó.
Em certas aplicações convém considerar árvores cujos nós têm 
um número limitado de filhos. Em particular, uma árvore binária é tal 
que todo nó tem no máximo dois filhos. No exemplo anterior, t1 e t3 
são árvores binárias, enquanto que t2 não. Desse ponto em diante, 
nosso estudo concentra-se em árvores binárias; mais informações 
sobre outros tipos de árvores podem ser encontradas nas referências 
bibliográficas. Essas árvores têm uma importância particular na 
Computação, que você mesmo poderá constatar durante a leitura.
 Vamos a seguir apresentar uma possível implementação de 
árvores binárias em computadores (outro método será proposto nos 
exercícios). Depois, aprofundaremos nosso estudo de árvores binárias 
discutindo métodos para a visita dos nós de uma árvore, e finalmente 
a representação de um conjunto dinâmico em uma árvore.
2. Implementação de árvores binárias
Em uma árvore binária é conveniente ordenar os filhos de cada 
nó em filho esquerdo e filho direito. Com essa convenção, podemos 
implementar uma árvore usando registros e ponteiros, de forma 
semelhante à implementação de listas ligadas apresentada no 
primeiro capítulo. Mais precisamente, cada nó da árvore é um registro 
composto de um campo info, nesse texto sempre um inteiro, e de dois 
ponteiros, esq e dir, que armazenam os endereços dos filhos desse 
nó. Representamos um tal registro como segue:
info
esq dir
Em um nó que não tem um dos filhos, o ponteiro correspondente 
vale nil. Em particular, em uma folha ambos os ponteiros valem nil. 
Em Portucal acessamos esses campos, como de hábito, usando 
Lembrete
As árvores em 
Computação 
crescem 
invertidas: a raiz 
fica em cima, as 
folhas embaixo. 
(Folclore)
54
Algoritmos e Estrutura de Dados
colchetes: se r é um registro, escrevemos
info[r], esq[r], dir[r]
Encontramos abaixo a implementação da árvore representando um 
conjunto de inteiros ilustrada no início desse capítulo. Nessa figura, o 
ponteiro r armazena o endereço do registro correspondente à raiz. 
É hábito relaxar um pouco o discurso e dizer, ao invés da sentença 
precisa “r é um ponteiro para a raiz”, que r é a árvore de fato. Essa 
convenção é coerente: para passar uma árvore a uma função, basta 
passar