UNIMAR EAD - Livro completo Estrutura de dados

Prévia do material em texto

ESTRUTURA DE DADOS
Prof. Me. VALDIR AMANCIO PEREIRA JUNIOR
Reitor
Márcio Mesquita Serva
Vice-reitora
Profª. Regina Lúcia Ottaiano Losasso Serva
Pró-Reitor Acadêmico
Prof. José Roberto Marques de Castro
Pró-reitora de Pesquisa, Pós-graduação e Ação Comunitária
Profª. Drª. Fernanda Mesquita Serva
Pró-reitor Administrativo
Marco Antonio Teixeira
Direção do Núcleo de Educação a Distância
Paulo Pardo
Coordenadora Pedagógica do Curso
Ana Lívia Cazane
Designer Educacional
Juliana Spadoto
Edição de Arte, Diagramação, Design Gráfico
B42 Design
*Todos os gráficos, tabelas e esquemas são creditados à autoria, salvo quando indicada a referência. Informamos
que é de inteira responsabilidade da autoria a emissão de conceitos.
Nenhuma parte desta publicação poderá ser reproduzida por qualquer meio ou forma sem autorização. A 
violação dos direitos autorais é crime estabelecido pela Lei n.º 9.610/98 e punido pelo artigo 184 do Código Penal.
Universidade de Marília 
Avenida Hygino Muzzy Filho, 1001 
CEP 17.525–902- Marília-SP
Imagens, ícones e capa: ©envato, ©pexels, ©pixabay, ©Twenty20 e ©wikimedia
G915b Sobrenome, Nome autor
Titulo Disciplina [livro eletrônico] / Nome completo autor. - 
Marília: Unimar, 2020.
PDF (XXX p.) : il. color.
ISBN XXX-XX-XXXXX-XX-X
1. palavra 2. palavra 3. palavra 4. palavra 5. palavra 6.
palavra 7. palavra 8. palavra I. Título.
CDD – 610.6952017
Introdução
O objetivo dos conteúdos sobre estruturas de dados é compreender como podemos
lidar com dados dentro dos modelos, técnicas e tecnologias relacionadas à
programação de computadores, especificamente com a linguagem de Programação de
programação Python.
Faremos desde uma revisão sobre o Python e suas estruturas básicas para podermos
lidar melhor com os dados, como entrada e saída de dados, estruturas condicionais,
estruturas de controle, além, é claro, de estudar os tipos de dados que podemos
utilizar ou até mesmo criar, como é o caso dos tipos de dados abstratos que vão
proporcionar flexibilidade e poder às técnicas e estruturas de dados que vamos
aprender.
Outros objetivos da disciplina são entender coleções de dados, desde as nativas da
linguagem Python até as coleções que podemos criar seguindo as diretrizes das
diversas estruturas de dados como listas, listas encadeadas e listas ordenadas, pilhas,
filas, matrizes e deques. Estudaremos também técnicas como a recursividade,
buscando entender melhor como podemos melhorar as soluções com mais poder e
elegância em nossos algoritmos, assim como métodos e busca e ordenação de dados,
que desempenham um papel impar na solução e otimização de algoritmos, e no final,
mas não menos importante, vamos estudar sobre a estrutura de árvores de dados. 
3
005 Aula 01:
025 Aula 02:
032 Aula 03:
042 Aula 04:
047 Aula 05:
055 Aula 06:
064 Aula 07:
070 Aula 08:
076 Aula 09:
081 Aula 10:
087 Aula 11:
093 Aula 12:
098 Aula 13:
105 Aula 14:
109 Aula 15:
114 Aula 16:
Introdução ao Python e Estruturas Básicas 
Tipos de Dados: Primitivos e Abstratos 
Coleções de Dados em Python 
Listas Lineares 
Listas Lineares Desordenadas 
Listas Lineares Ordenadas 
Pilhas 
Filas 
Deque 
Matrizes 
Recursividade 
Métodos de Ordenação I 
Métodos de Ordenação II 
Métodos de Busca: Sequencial 
Métodos de Busca: Binária 
Árvore
01
Introdução ao Python 
e Estruturas Básicas
A Linguagem de Programação
Python
A linguagem de programação Python teve sua origem próxima do início da década de
1990 e foi idealizada pelo matemático Guido Van Rossum. O Python foi elaborado
como uma linguagem de scripts, inicialmente para o sistema operacional Amoeba, e
entrou como uma evolução de outra linguagem de programação que era voltada para
físicos, engenheiros e outras profissões ligadas à matemática ou que houvesse
necessidade de processamento de dados, a linguagem ABC (SILVA, 2018).
Uma curiosidade sobre o Python é que seu idealizador deu este nome para a
linguagem, pois gostava muito do grupo de comédia britânico Monty Python. Isto o
levou a ideia de criar uma linguagem que possibilitasse o aprendizado de
programação mais simples e leve, como eram os filmes e programas humorísticos do
grupo. Outra curiosidade é que o criador queria evitar que a linguagem fosse
associada à cobra píton, porém, em 1996 a editora O’Reilly, com a autorização de Van
Rossum, publicou o livro Programming Python, que levava uma cobra píton (python, em
inglês) na capa de seu primeiro livro de programação Python. Desde então, o Python é
associado diretamente ao réptil em questão. 
Capa do livro Programming Python
6
O grupo britânico de humor Monty Phyton no filme “Em Busca do Cálice Sagrado”, de
1975
Fonte: Disponível aqui
O Python foi idealizado para proporcionar uma maior facilidade de ensino da
programação, possuindo assim uma menor curva de aprendizagem para profissionais
de outras linguagens e principalmente leigos, contando para isso com uma ótima
legibilidade, o que possibilita o desenvolvimento de software através de um código de
fácil leitura e compreensão, proporcionando uma manutenção no software
igualmente fácil e rápido quanto à sua criação (PYSCIENCE-BRASIL, 2019).
As principais características do Python são:
Linguagem de programação de alto nível.
Gratuita e Open Source.
Orientada a objetos.
Sintaxe simples, limpa, legível e elegante. 
Outros pontos importantes sobre o Python a serem ressaltados são que a utilização
de caracteres especiais é bem reduzida, fazendo assim com que o código escrito se
aproxime muito da sintaxe de um código escrito em uma linguagem estruturada
7
https://br.ign.com/monty-python/79491/news/terry-jones-fundador-de-monty-python-morre-aos-77-anos
como um pseudocódigo ou até mesmo do Português ou Inglês. É uma linguagem de
desenvolvimento e execução multiplataforma, ou seja, é possível trabalhar em
diversos sistemas operacionais e arquiteturas diferentes (SILVA, 2018).
O Python ainda conta com uma vasta biblioteca de classes, método e funções que
podem ser utilizados. Um dos fatores mais importantes e que afeta diretamente o
momento de desenvolvimento com Python é que a linguagem não utiliza caracteres
especiais para definir os blocos de código, e a estruturação dos blocos de código é
totalmente feita por meio de endentação (PYSCIENCE-BRASIL, 2019).
Hoje, o Python já está presente nativamente em diversos sistemas operacionais,
principalmente em distribuições Linux, como Ubuntu, Debian, Fedora e também em
sistemas OS X. Além de ser adotada de soluções de diversas empresas mundialmente
conhecidas tais como Google, YouTube, Disney, Globo.com e até mesmo a Nasa.
Acesse o link: Disponível aqui
No site oficial do Python, é possível ter acesso a diversos guias para
iniciantes em programação, detalhes sobre a linguagem, documentação,
informação sobre eventos e diversas outras informações.
Instalação e Ambiente
Como visto anteriormente, a linguagem Python é multiplataforma, ou seja, pode ser
desenvolvida e aplicada em diversos sistemas operacionais. Assim, é possível ser feita
sua instalação em diversos ambientes como Windows, distribuições Linux e OS X.
Hoje, existem variações do Python quer permitem ser executadas em sistemas
embarcados, ampliando a capacidade de aplicações da linguagem.
8
http://www.python.org/
Imagem 3 – Página de download do Python.
Fonte: Disponível aqui
A instalação do Python vai variar conforme o sistema operacional, e quando se trata
do Linux e OS X, a instalação é feita por meio de comandos através do terminal, o
bash. Quando se trata do Windows, conta com o auxílio de um instalador com
interface gráfica que guia os passos das instalações.
Para acesso à documentação, instruções de instalação e o download do instalador,
basta acessar o site oficial da linguagem e procurar pelo link de download ou acessar
diretamente: https://www.python.org/downloads/. Ao acessar a página, é possível ver
qual a última versão disponível para download e quais sistemas operacionais é
possível fazer a instalação (como demonstrada a Imagem3).
Ainda na página de download, é disponibilizada uma tabela com o histórico de
versões do Python, sua data de lançamento e até quando tem suporte, fator relevante
ao decidir qual versão irá aplicar em um projeto, sempre dando preferência para a
última versão (“latest version”), mas que atenda às necessidades das dependências do
projeto. A Imagem 4 traz um exemplo de tabela de versão, com data de lançamento e
até quando a versão do Python tem suporte.
Importante notar que o todo o site oficial da linguagem é em inglês, porém, é de fácil
compreensão, e você ainda pode utilizar ferramentas e plug-ins para traduzir o
conteúdo.
9
https://www.python.org/downloads/
https://www.python.org/downloads/
Imagem 4 – Exemplo de tabela de versões do Python.
Fonte: Disponível aqui
Windows Linux OS X
Para não errar na hora de instalar o Python e começar a desenvolver, existe
uma comunidade brasileira da linguagem que desenvolveu um passo a
passo bem detalhado para Windows, Linux e OS X. Além de dar dicas de
eventos, algumas páginas com tutoriais, wikis e dicas de desenvolvimento.
Para conferir a página de instalação:
Com o seu Python já instalado e devidamente configurado, também é necessária uma
IDE (Integrated Development Environment ou Ambiente de Desenvolvimento Integrado)
que permite a você escrever os algoritmos em Python e também realizar sua
execução e testes necessários. Existe uma gama enorme de opções de IDEs e
ferramentas para a linguagem, entre gratuitas pagas, open source e proprietárias.
Algumas oferecem um ambiente robusto, possibilitando até mesmo a gestão de
dependências e bancos de dados, enquanto outras oferecem apenas o editor de
código e algumas facilidades (SILVA, 2018).
10
https://www.python.org/downloads/
https://python.org.br/instalacao-windows/
https://python.org.br/instalacao-linux/
https://python.org.br/instalacao-mac/
Dentre as principais, pode-se citar: IDLE, PyCharm, PyCharm Community, Sublime,
Atom, Visual Studio Code e Vim. O PyCharm e PyCharm Community (versão gratuita)
são os mais robustos e que oferecem mais possibilidades de ferramentas
complementares, porém, em todos é possível fazer o principal: escrever e alterar
algoritmos.
Você pode encontrar mais detalhes de cada uma dessas IDEs e outras com mais
detalhes e os respectivos links para download na página da comunidade Python
Brasil: https://python.org.br/ferramentas/. Com o Python instalado e o ambiente
pronto para as primeiras linhas de código, vamos começar a entender como o Python
lida com os dados, e depois entender e construir estruturas de dados.
Estruturas do Python
Nesta seção, vamos ver as principais estruturas do Python que são capazes de
manipular dados, definindo fluxos de execução e controle, passando pelos
operadores aritméticos, entrada e saída, comandos condicionais e iterativos.
Atribuição e Operadores Aritméticos
Operadores são símbolos e caracteres especiais utilizados para determinadas ações
sobre os dados de um programa, em que tais dados estão armazenados em variáveis,
como nas demais linguagens de programação. O primeiro operador e o mais simples
da linguagem Python é o operador de atribuição, que atua diretamente para atribuir
algum valor para determinada variável. O símbolo utilizado para esse operador nos
algoritmo é o “igual” ( = ). Vale o destaque que o operador = sobrescreve informações,
ou seja, ele apaga o que já existe dentro da variável e escreve o novo dado atribuído
(PERKOVIC, 2016).
E lembre-se sempre da sintaxe básica de atribuição, variável que receberá o valor à
esquerda do operador e o valor à direita do operador, como demonstrado na Imagem
5. 
11
https://python.org.br/ferramentas/
Imagem 5 – Sintaxe da operação de atribuição.
Fonte: Próprio autor.
Referente à sintaxe da operação de atribuição, a parte que se refere ao valor que será
armazenado pode ser um dado constante ou fixo, mas também pode ser um dado
resultante de uma operação, como, por exemplo, as operações aritméticas. Dentro do
Python existem quatro operadores aritméticos básicos: soma, subtração,
multiplicação e divisão, que são representados pelos símbolos: +, -, * e /,
respectivamente (MENEZES, 2019).
Atenção ao uso de operadores aritméticos: eles seguem as mesmas regras
da matemática, inclusive o uso de parênteses e a ordem de interpretação.
A Imagem 6 a seguir traz exemplos dos operadores aritméticos aplicados com Python
e já utilizando o operador de atribuição, ou seja, o valor é calculado e então
armazenado em uma variável. Para exibir o valor resultando da operação aritmética e
que está na variável, é utilizado o comando print, que será apresentado na próxima
seção e se trata de um comando de saída.
12
Imagem 6 – Exemplo de operadores aritméticos básicos com Python
Fonte: autor.
>>> soma = 1 + 2
>>> print(soma)
3
>>> subtracao = 10 - 4
>>> print(subtracao)
6
>>> multiplicacao = 8 * 3
>>> print(multiplicacao)
24
>>> divisao = 15/2
>>> print(divisao)
7.5
Existem ainda alguns operadores especiais como de potenciação, módulo ou resto e
parte inteira da divisão, utilizando-se os seguintes símbolos: potenciação (**), módulo
(%) e parte inteira da divisão (//). A Imagem 7 traz alguns exemplos da aplicação
destes operadores especiais.
13
Imagem 7 – Exemplo de operadores aritméticos especiais com Python.
Fonte: autor.
>>> potencia = 2**3
>>> print(potencia)
8
>>> resto = 10 % 3
>>> print(resto)
1
>>> resto1 = 10 % 2
>>> print(resto1)
0
>>> parteInteira = 15 // 2
>>> print(parteInteira)
7
Comandos de Entrada e Saída
Comando de saída de dados
Uma parte importante quando lidamos com todas as linguagens de programação é a
forma como acontece a interação entre o usuário e o computador, ou seja, uma
linguagem deve ser capaz de conter comandos que possam receber e apresentar
dados e resultados ao usuário. Isto ocorre através de comandos de entrada e saída.
No Python, tais ações são realizadas pelos comandos print (saída) e input (entrada).
Nesta seção, ambos serão apresentados, junto com detalhes e exemplos (SILVA,
2018).
14
Imagem 8 – Exemplo com o comando print com “Hello World”.
O comando print() responsável pela saída de dados do algoritmo desenvolvido em
Python é um método padrão da linguagem, e conta com alguns recursos para
representar as informações e dados. Esta função imprime mensagens específicas em
uma saída padrão como, por exemplo, o console ou terminal, tela do computador e
celular. A saída ou mensagem apresentada pode ser uma string (conjunto de
caracteres) ou outros objetos, como variáveis e constantes (PERKOVIC, 2016).
A sintaxe do print() é:
print(objects, sep=separator, end=end, file=sys.stdout, flush=False)
Em um primeiro momento, pode parecer algo complexo por causa dos parâmetros
padrões, porém, eles fazem parte da construção do método e serão aplicados em
alguns momentos, apenas quando necessários.
Fique atento! A partir da versão do Python 3, no comando print() é
obrigatório o uso de parênteses.
As Imagens 8, 9 e 10 trazem exemplos do uso do comando print() e seus parâmetros e
já demonstra como concatenar valores de variáveis com string. Lembrando que
concatenar é a junção de duas ou mais strings, criando uma única mensagem a partir
de vários elementos. Assim, fique atento ao tipo do dado que está utilizando. No
Python, é possível concatenar strings, variáveis, constantes e alguns objetos, entre
outros.
>>> print('Hello World!')
Hello World!
Fonte: autor.
15
Imagem 9 – Exemplo com print e concatenação.
Fonte: autor.
Imagem 10 – Exemplo com print e dados fixos.
Fonte: autor.
>>> preco = 4.50
>>> quanitade = 3
>>> total = preco * quantidade
>>> print('Total da compra: $R$', total, ' a vista')
Total da compra: R$13.50 a vista
>>> nome = "Maria"
>>> idade = 19
>>> print('Olá ', nome, ', você tem ', idade, ' anos')
Olá Maria, você tem 19 anos
Comando de Entrada de Dados
Junto à saída de dados processados, a entrada de dados é igualmente importante,
principalmente para garantir a interação do algoritmo e softwarecom o usuário.
Quando se refere à entrada de dados, podemos pensar em diversos métodos de
entrada, e qualquer interação com o dispositivo pode ser considerada uma entrada:
teclado, mouse, tela sensíveis ao toque e até mesmo gestos ou movimentos
(MENEZES, 2019).
16
Na linguagem Python, aplica-se a função input(), comando que permite ler dados a
partir de uma entrada padrão. Para as soluções desta disciplina, será o teclado, pois
os algoritmos serão executados via terminal de comandos. Ao ser executado pelo
fluxo do algoritmo, o input bloqueia o fluxo de execução padrão do algoritmo e
aguarda até que o usuário digite um valor no terminal ou local que está sendo
executado. Por padrão, o valor lido é armazenado em uma variável e será uma string
(PERKOVIC, 2016).
A sintaxe do input() é:
variavel = input(prompt)
O parâmetro é opcional e imprime uma mensagem (string) na tela.
As Imagens 11 e 12 trazem exemplos da aplicação do comando input(), solicitando que
o usuário informe alguns dados – lembrando que o terminal ficará travado (fluxo
interrompido) até que seja pressionada a tecla “Enter”, então, o conteúdo é
armazenado na variável informada, e depois disso o programa segue normalmente a
execução.
A partir desse momento, vamos construir nossos algoritmos em um editor
de código de sua preferência e então executando o código via terminal para
executar o seu código salve em um arquivo com a extensão .py. Então,
navegue até o diretório em que foi salvo e execute o comando conforme a
versão.
Python 3: 
python3 nome_do_arquivo.py
Python 2: 
python nome_do_arquivo.py
Todos os exemplos desenvolvidos neste material serão com o Python 3.
17
Imagem 11 – Exemplo com input com uma variável.
Fonte: autor.
Imagem 12 – Exemplo com input com duas variáveis.
Fonte: autor.
Imagem 13 – Exemplo com input com casting.
Fonte: autor.
nome = input("Informe o seu nome: ")
print('Olá ' + nome + ', tudo bem?')
nome = input("Informe o seu nome: ")
sobrenome = input("Informe o seu sobrenome: ")
print('Olá ' + nome + ' ' + sobrenome +', tudo bem?')
Sabemos que o valor padrão lido e armazenado pela função input() é sempre uma
string, porém, isso pode gerar diversos problemas, pois não existe apenas um tipo de
dado, mas existem dados que são inteiros, float, booleanos e outros. O Python traz
uma forma de solucionar este problema com a conversão de tipos de dados ou
casting. Para fazer o casting, existem funções para cada tipo de dado: usar int() faz a
conversão para inteiro, float() faz a conversão para decimal com vírgula e str() faz
conversão para string (PERKOVIC, 2016).
Para fazer casting de um input, basta usar a função desejada antes do comando input,
e a Imagem 13 traz um exemplo de casting para inteiro.
distancia = int(input("Informe a distância em metros: "))
print(distancia)
18
Imagem 14 – Exemplos de casting
Fonte: autor.
Fique atento ao fazer o casting para inteiro ou float, pois para concatenas no
print é necessário utilizar a função str() pois usar o símbolo “+” para
concatenar será confundida com a operação aritmética de soma.
A Imagem 14 traz um exemplo de casting em que também é feita a concatenação de
diferentes tipos de dados.
nome = input("Inform seu nome: ")
#faz casting de string para int, pois idade é inteiro
idade = int(input("Informe sua idade: "))
#faz casting de string para float, pois altura é ponto flutuante
altura = float(input("Informe sua altura(metros): "))
print('Olá ' + nome)
#faz casting de int e float para string
print('Você tem ' + str(idade) + ' anos')
print('E sua é ' + str(altura) + ' metros.')
19
Imagem 15 – Estrutura do comando if simples
Fonte: autor.
Comandos Condicionais
Outra estrutura essencial, assim como em outras linguagens de programação, são os
comandos condicionais. Tais comandos permitem selecionar partes do nosso código
que serão executadas ou não, dependendo de testes e condições criadas. Por
exemplo, restringir um acesso ao software conforme a idade do usuário, se ele tiver
mais de 18 anos pode acessar, caso contrário, seu acesso é bloqueado (MENEZES,
2019).
Seguindo a linha de outras linguagens os comandos em Python são escritos em inglês,
logo os comandos “se” e “senão”, são escritos como “if” e “else” respectivamente. Com
o uso desses comandos no Python podemos facilmente definir quais blocos de código
serão executados, alterando o fluxo de processamento (SILVA, 2018).
Ainda existe o comando elif, que é justamente o “senão se” que permite criar uma
estrutura composta para testar mais condições em uma única estrutura. As imagens
15 e 16 trazem as possíveis sintaxes do Python para o if simples e composto.
if condição lógica:
   #bloco de código
   #esse bloco sére executado quando a
   #confição for verdadeira
else:
   #bloco de código
   #esse bloco sére executado quando a
   #confição for falsa
20
Imagem 16 – Estrutura do comando if composto
Fonte: autor.
if condição lógica 1:
   #bloco de código
   #esse bloco sére executado quando a
   #confição for verdadeira
elif condição lógica 2:
   #bloco de código
   #esse bloco sére executado quando a
   #segunda confição for verdadeira
else:
   #bloco de código
   #esse bloco sére executado quando
   #nenhumadas confições for verdadeira
21
Imagem 17 – Solução com if para definir faixa etária
Fonte: autor.
Um cenário real que podemos pensar para treinar a lógica com comando
condicionais é definir a faixa etária de pessoas conforme idade – lembrando
que a faixa etária pode variar conforme o domínio. A Imagem 17 traz um
exemplo de uma possível solução para esse cenário, e vale ressaltar que a
lógica da solução pode variar de pessoa para pessoa, mas existem boas
práticas.
idade = int(input("Informe a idade: "))
#definir faixa etária
if idade >= 60:
   print("Idoso")
elif idade >= 20:
   print("Adulto")
elif idade >= 13:
   print("Jovem")
else:
   print("Criança")
22
Imagem 18 – Solução com if para definir faixa etária.
Fonte: autor.
Comandos Iterativos
Além dos comandos condicionais, entrada e saída, operadores lógicos e aritméticos,
podemos ainda criar estrutura iterativas em nossos algoritmos com Python, tais
estruturas permitem controlar a forma de execução de alguns blocos de código,
conseguindo controlar quantas vezes um bloco será executado, ou seja, uma
repetição ou loop (MENEZES, 2019).
Dentro da linguagem Python, existem dois principais comandos que podemos
trabalhar para criar uma estrutura de repetição controlada, conseguindo assim fazer
repetir diversas vezes um único bloco de código conforme uma condição definida: o
comando while e o comando for. A Imagem 18 demonstra a sintaxe e estrutura para
construir o while e o for, lembrando que são estruturas separadas (PERKOVIC, 2016).
Aplicando ambos os comandos de iteração, eles podem ser combinados ou
agrupados, gerando assim uma estrutura com diferentes fluxos de execução, por
exemplo, um while dentro de outro while ou um for. Porém essa é uma prática que
devemos ter cuidado, uma vez que pode gerar loops infinitos e travar a execução de
uma máquina ou servidor, gerando imprevistos e custos desnecessários.
while condição:
   #bloco de código
for variável in objeto iterável:
   #bloco de código
23
Imagem 19 – Solução com if para definir faixa etária.
Fonte: autor.
Vamos imaginar uma lista com quatro alunos de uma turma de inglês, e
estes alunos precisam saber qual é a sua nota final baseado em três notas,
prova, participação e trabalho. A prova vale 5, a participação vale 4 e o
trabalho 1. Vamos criar um algoritmo com loop para calcular as notas?
A Imagem 19 traz uma possível solução ao problema, já utilizando de uma
lista em Python e também da estrutura for para repetição.
alunos = ["Vitória", "Carlos", "Renata"]
for nome in alunos:
   print("Aluno: " + nome)
   nProva = float(input("Nota da prova: "))
   nParticipacao = float(input("Nota de participação: "))
   nTrabalho = float(input("Nota do trabalho: "))
   media = (nProva * 0.5) + (nParticipacao * 0.4)+
(nTrabalho * 0.1)
   print("A nota final foi: " + str(media) + "\n")
24
Acesse os links: Disponível aqui Disponível aqui
Algumas dicas sempre importantes:
Os blocos de código são definidos por endentação
Comandos como if, else, elif, while e for sempre tem “:” antes do
próximo bloco de código
Consulte sempre a documentação do Python.
25
https://www.python.org/doc/
https://python.org.br/introducao/
02
Tipos de Dados: 
Primitivos e Abstratos
Ao começar a estudar a forma como podemos lidar, entender e manipular dados
dentro da programação de computadores, algoritmos e software, é importante
entender como os dados vão se comportar ou qual a sua natureza, já vimos que
podemos ler dados do usuário, processar de alguma forma tais dados e também
apresentar dados ao usuário (GUIMARÃES, 1984).
Porém, ai encontramos uma possível limitação que precisamos fazer a conversão de
tipo dos dados ou casting, pois o Python sempre lê dados como string e então
precisamos converter caso seja um inteiro ou float. Nesta aula, vamos compreender
um pouco melhor os diversos tipos de dados do Python e como podemos trabalhar
com eles (PERKOVIC, 2016).
Tipos de Dados Primitivos ou
Nativos
Sempre que vamos desenvolver qualquer solução com programação, pensamos em
quais iremos trabalhar e formas como podemos trabalhar tais dados, ou seja, iremos
precisar de variáveis para armazenar esses dados, como por exemplo: nome, idade,
altura, sexo, peso, data de nascimento, nacionalidade, entre diversos outros dados
(GUIMARÃES, 1984).
Porém, cada um desses dados é de um tipo diferente, logo, cada variável também tem
um único tipo. Olhando atentamente aos exemplos, como um nome é composto? Ele
contém letras em determinada sequência que lhe dão um significado, mas pode
representar a sua idade? Um texto também? Uma sequência de letras? Nesse caso o
mais recomendado para a idade é um número. Podemos ir muito além, saldo
bancário, distância de uma viagem, cores, cada cenário tem diversas variáveis.
Já sabemos então que temos diferentes tipos de dados para cada domínio, mas como
vamos trabalhar com eles? O Python é uma linguagem que respeita tais tipos, porém
não é fortemente tipada, como é o Java, ou seja, não precisamos falar qual o tipo
dessa variável, basta associar um valor e a mesma irá assumir esse tipo.
27
De forma geral, as linguagens de programação seguem alguns tipos de dados
primitivos, como inteiro, texto, real, etc. A linguagem Python segmenta seus dados em
dois grandes grupos: dados atômicos e dados coletivos, e cada um desses grupos
contém mais tipos de dados (PERKOVIC, 2016). 
Um dado atômico, independente da linguagem de programação é um dado
único, atômico está relacionado à menor unidade possível, por exemplo,
uma variável do tipo inteiro que contém apenas um único valor, é uma
variável atômica.
Já um dado coletivo, ou do tipo coletivo, faz referência direta a uma
coletânea de valores, ou seja, um agrupamento de dados em um único
espaço. Um exemplo são os vetores ou arrays, que dependendo da
linguagem, cria uma coleção de diversos dados em uma única variável,
sendo que cada dado interno pode ser de um tipo atômico diferente.
Neste momento, vamos focar nos dados atômicos primitivos, em entender os tipos de
dados e variáveis. De forma geral, existem 4 tipos primitivos de dados, porém cada
linguagem de programação pode criar variações e subdivisões desse tipos, mas de
modo geral os tipos primitivos de dados são (PERKOVIC, 2016; SZWARCFITER, 2017):
Inteiro: faz referência aos conjuntos dos números inteiros da matemática, ou
seja, valores negativos e positivos sem casa decimal.
Real: está relacionado aos valores reais da matemática, também chamados de
ponto flutuante, contemplam números negativos e positivos com casa decimal.
Lógico: são valores booleanos, podendo assumir apenas dois estados,
VERDADEIRO ou FALSE. Na computação pode ser representado por apenas um
bit, sendo o bit 1 para verdadeiro e 0 para falso.
Texto: refere-se a qualquer sequência de um ou mais caracteres utilizando os
valores do tipo “texto” entre “ ” (aspas duplas). 
28
Imagem 2 – Tipo de dados atômicos em Python e função type.
Fonte: autor.
A linguagem Python incorpora esses tipos genéricos, mas com algumas variações de
nomenclatura, assim temos os tipos: int (inteiro), float (real), string (texto) e boolean
(lógico). Como o Python não tem tipagem forte, ou seja, não consegui saber qual o
tipo da variável pela sua declaração, temos a função type() para revelar qual o tipo do
dado. Um detalhe importante, como a linguagem é orientada a objeto, os tipos de
dados são tratados como classes. A Imagem 2 traz um exemplo de variáveis e seu
tipos, aplicando a função type() (PERKOVIC, 2016).
>>> nome = "João"
>>> idade = 20
>>> saldo = 3260.89
>>> sexo = 'M'
>>> logico = True
>>> type(nome)
<class 'str'>
>>> type(idade)
<class 'int'>
>>> type(saldo)
<class 'float'>
>>> type(sexo)
<class 'str'>
>>> type(logico)
<class 'bool'>
29
Fique sempre atento ao retorno em qual tipo de dado do Python melhor se
enquadra na situação que irá resolver. Um valor de saldo de conta bancária
fica bem expresso como uma string? Ou fica melhor como float? A resposta é
com float, pois em um saldo bancário você precisa fazer operações de
crédito e débito e com um dado do tipo float você pode fazer operações
aritméticas.
Tipos de Dados Abstratos ou
Customizados
Até agora vimos os dados primitivos ou nativos, que estão intimamente ligados à
estrutura e construção de um dado, não se preocupando ao o que é dado ou sua
representação. Vimos diversos exemplos de nome, idade, altura, saldo e outros,
porém são dados isolados e que representam um único valor.
E se for necessário criar um tipo de dado mais amplo e que se adeque melhor ao
cenário que estamos programando, é necessária a aplicação do conceito de Tipos de
Dados Abstratos (TAD) que é justamente a capacidade de encapsular os tipos
primitivos e criar um tipo maior. Podemos pensar em diversos tipos de dados
abstratos, como a maioria dos objetos (SZWARCFITER, 2017; GUIMARÃES, 1984).
O TAD é criação de um bloco bem estruturado de dados e um conjunto de ações e
métodos preparados para a manipulação de tal bloco de dados. Os dados são
chamados de atributos e as operações de Interface do TAD. Tal conceito surgiu junto a
programação estruturada, mas contribuiu para o surgimento do paradigma orientado
a objetos (GUIMARÃES, 1984).
30
Por exemplo, como podemos desenvolvedor uma solução para lidar com um caixa
econômico ou ATM, cada pessoa tem sua conta e pode realizar ações, uma conta tem
saldo, mas a conta pertence a uma pessoa. Neste caso, podemos criar um tipo
abstrato “pessoa”, que pode ter diversas características tais como nome, número da
conta, data da última movimentação e, dessa forma, ainda podemos ter diversas
pessoas de maneira isolada e que podem até ter ações programadas, como realizar
um saque, depositar, solicitar comprovante, entre outras.
A implementação de tipos de dados abstratos está diretamente relacionado a lidar
com a estrutura de dados, pois fará o uso de coleções de tipos de dados primitivos.
Existem diferentes maneiras de implementar um tipo de dado abstrato, utilizando da
linguagem Python, podemos utilizar classes, dicionário e até mesmo listas para
representar e manipular os dados (SZWARCFITER, 2017; PERKOVIC, 2016).
A Imagem 3 traz o exemplo de implementação de um TAD utilizando classes com
Python que representa uma conta bancária, com atributos de tipo primitivo e algumas
ações para ver o saldo e fazer um saque, de forma bem simples, apenas para
apresentar um exemplo de construção. Essa construção permite mais flexibilidade ao
desenvolvedor e cria uma interface com o usuário para que ele não note possíveis
mudanças na estrutura de uma forma muito brusca ou que possa gerar problemas.
Pode-se observar, no final do exemplo, que existe a criação de uma variável do tipo
Conta (TAD criado) e logo em seguida é utilizado o comando type() para verificar o tipo
e o retornoé o tipo Conta, como esperado. 
31
Imagem 3 – Representação de uma estrutura de tipo de dados abstrata com
classe em Python.
Fonte: autor.
class Conta:
   saldo = 0
   numero = '00000-00'
   cliente = 1
   def total(self):
       return self.saldo
   def saque(self, valor):
       return self.saldo - valor
>>> conta1 = Conta()
>>> type(conta1)
<class '__main__.Conta'>
32
03
Coleções de Dados 
em Python
Olá a todos!
Além da possibilidade de trabalhar com dados nativos e abstratos, diversas
linguagens de programação oferecem a possibilidade de trabalhar com coleções de
dados, e uma coleção nada de mais é que um agrupamento de dados, que podem
ser do mesmo tipo ou não. Assim, conseguimos criar conjuntos ou coleções de
diversas formas, bem como uma coleção pode ser tida como uma estrutura de dados
SZWARCFITER e MARKENZON, 2017; GUIMARÃES, 1984; PERKOVIC, 2016; (MILLER e
RANUM, 2013).
Podem-se achar referências e citações de coleções como vetores, arrays, listas,
conjuntos, dicionários, entre outros, pois esse termo pode variar conforme a
linguagem de programação utilizada (SZWARCFITER e MARKENZON, 2017;
GUIMARÃES, 1984). 
34
Imagem 2 – Iteração com variável string como conjunto.
Fonte: autor.
Vimos que textos ou string são listados como tipos de dados primitivos e
atômicos, ou seja, todo o conteúdo está contido em uma variável. Porém,
como o Python trata seus tipos primitivos também como classes e uma
string é considerada um conjunto de caracteres, alguns métodos e técnicas
para lidar com conjuntos de dados pode ser aplicados em um string.
Por exemplo, é possível fazer uma iteração com loop utilizando while em
uma variável do tipo string. A Imagem 2 traz um exemplo de código fazendo
uma iteração em uma string.
texto = "paralelepipedo"
i = 0
while i < len(texto):
   print(texto[i])
   i+=1
A linguagem Python segmenta as coleções de duas formas: coleções ordenadas e
coleções não ordenadas.
Como ordenadas, são categorizadas em listas (tipo list), strings (tipo str) e tuplas (tipo
tuple). As não ordenadas são: conjuntos (tipo set) e dicionário (tipo dict) – lembrando
que toda iteração entre os elementos de uma coleção inicia na posição 0 por padrão.
35
Imagem 3 – Relação entre elementos e posições em uma coleção.
Fonte: Próprio autor.
A Imagem 3 traz uma relação entre elementos e a posição referente, relação esta que
deve ser clara para não haver erros na iteração (PERKOVIC, 2016; MILLER e RANUM,
2013).
Podemos definir assim que as posições de uma coleção são dadas pelo tamanho da
coleção -1, para descobrir o tamanho, ou número de elementos, de uma coleção
podemos utilizar a função len() do Python.
Lista
Listas em Python são coleções ordenadas de zero ou mais referências a tipos de
dados ou objetos. A estrutura para construção de uma lista em Python é
relativamente simples, cuja delimitação é feita por colchetes e os elementos são
separados por vírgulas. Uma lista pode ser heterogênea, ou seja, os dados e objetos
presentes dentro da lista podem ser de diferentes tipos ou classes. Além disso, uma
estrutura de lista pode ser atribuída em uma variável.
A Imagem 4 traz alguns comandos com listas (PERKOVIC, 2016; MILLER e RANUM,
2013). 
36
Imagem 4 – Comando com listas em Python.
Fonte: autor.
>>> [1, 2.5, 10, 5, "Teste", True]
[1, 2.5, 10, 5, "Teste", True]
>>> lista1 = [1, 2.5, 10, 5, "Teste", True]
>>> lista1
[1, 2.5, 10, 5, "Teste", True]
>>> len(lista1)
6
A Tabela 1 traz uma relação de comandos referentes ao Python e podem ser
aplicados em listas. O conceito de uma coleção que vimos e que tem a posição de 0
até o número de elementos -1 é útil aqui para aplicar o fatiamento ou indexação.
37
Tabela 1 – Operações para Listas em Python
Fonte: Próprio autor.
Operações para Listas em Python
Nome Operador Descrição
Indexação [ ] Acessa um elemento da lista
Concatenação + Combina duas listas
Repetição * Concatena N vezes a lista
Pertinência In Valida se um elemento pertence à lista
Comprimento len() Retorna o total de elementos da lista
Fatiamento [ : ] Extrai parte de uma lista
A Imagem 5 traz um exemplo de aplicação das operações com lista em Python, e a
Tabela 2 traz a relação de métodos relacionados a listas.
38
Imagem 5 – Operações com lista em Python.
Fonte: autor.
>>> lista2 = [1, 2, 3, 4, 5]
>>> lista2
[1, 2, 3, 4, 5]
>>> lista2[0]
1
>>> lista3 = [6, 7, 8]
>>> lista2 + lista3
[1, 2, 3, 4, 5, 6, 7, 8]
>>> 0 in lista2
False
>>> 1 in lista2
True
>>> lista2[0:1]
[1]
>>> lista2[1:4]
[2, 3, 4]
39
Tabela 2 – Métodos para Listas em Python
Fonte: Próprio autor.
Métodos para Listas em Python
Nome Uso Descrição
append list.append(elemento) Adiciona um novo item ao final de uma lista
insert list.insert(i, elemento)
Insere um elemento em uma posição
específica
pop list.pop()
Remove e retorna o último elemento de uma
lista
pop list.pop(i)
Remove e retorna um elemento específico
de uma lista
sort list.sort() Ordena uma lista
reverse list.reverse()
Modifica uma lista, invertendo a ordem dos
itens
del del list[i] Exclui o elemento em uma posição específica
index list.index(elemento)
Retorna o índice da primeira ocorrência de
um elemento
count list.count(elemento)
Retorna o número de ocorrências de um
elemento
remove list.remove(item)
Remove a primeira ocorrência de um
elemento
40
Imagem 6 – Operações com tupla em Python.
Fonte: autor.
Tupla
As listas se parecem em diversos fatores com as listas em Python: são coleções de
dados e permitem dados heterogêneos. Mas a grande diferença é que as tuplas são
imutáveis, ou seja, não é possível incluir ou excluir elementos presentes em uma tupla
– entretanto, é possível aplicar as operações de lista, como indexação, fatiamento ou
pertinência (PERKOVIC, 2016; MILLER e RANUM, 2013).
A construção da tupla também se aproxima das listas. Os elementos são separados
por vírgulas, mas é delimitada por parênteses. A Imagem 6 traz o exemplo de
construção de uma tupla e operações. 
>>> tupla = (1, 3, 5.2, True, "Texto")
>>> tupla
(1, 3, 5.2, True, "Texto")
>>> tupla[1]
2
>>> tupla[3]
True
>>> 5.2 in tupla
True
>>> tupla[1:3]
(3, 5.2)
41
Imagem 7 – Criação de um dicionário com Python.
Fonte: autor.
Dicionário
A estrutura de dicionário é uma coleção desordenada de elementos. A associação dos
elementos de uma lista é feita por pares associados em que cada par é composto por
uma chave e um valor. Cada chave-valor é separada por vírgulas e delimitada por
chaves. A Imagem 7 traz um exemplo de criação de um dicionário em Python,
apresentando a relação de moradores por cidade, onde a chave é o nome da cidade e
o valor o total da população (PERKOVIC, 2016; MILLER e RANUM, 2013).
>>> populacao = {"São Paulo":12180000, "Rio de Janeiro":6320000,
"Florianópolis":477798}
>>> populacao
{'São Paulo':12180000, 'Rio de Janeiro':6320000,
'Florianópolis':477798}
É possível manipular dicionários acessando os valores por meio da chave relacionada
a cada valor ou adicionar um novo elemento através de um novo par chave-valor. A
forma de acesso remete a listas e tuplas, porém, ao invés de usar a posição ou índices
do elemento que se deseja acessar, vamos utilizar o valor da chave, para adicionar um
valor também é semelhante.   A Imagem 8 traz algumas manipulações com uma
dicionário.
42
Imagem 8 – Criação de um dicionário com Python.
Fonte: autor.
>>> print(populacao['São Paulo'])
12180000
>>> populacao['Belo Horizonte'] = 1433000
>>> print(populacao)
{'São Paulo':12180000, 'Rio de Janeiro':6320000,
'Florianópolis':477798, 'Belo Horizonte' = 1433000}
>>> print(len(populacao))
4
>>> for p in populacao:
       print(p, " tem ", populacao[p], " habitantes")
São Paulo tem 12180000 habitantes
Rio de Janeiro tem 6320000 habitantes
Florianópolis tem 477798 habitantes
Belo Horizonte tem 1433000 habitantes
As Tabelas 3 e 4 trazem uma relação de operadores e métodos capazes de serem
aplicados em dicionários. É importante notar que os métodos keys, values e items
retornamobjetos que contêm o resultado de interesse.
43
Tabela 3 – Operações para Dicionários em Python
Fonte: Próprio autor.
Operações para Listas em Python
Nome Uso Descrição
Indexação  dicio[ ] Acessa um elemento do dicionário
Pertinência
chave in
dicio
Valida se um elemento pertence à lista, retorna
True ou False
Exclusão
del
dicio[chave]
Remove parte de uma lista
Tabela 4 – Métodos para Listas em Python
Fonte: Próprio autor.
Operações para Listas em Python
Nome Uso Descrição
keys dicio.keys() Retorna todas as chaves de um dicionário
values dicio.values() Retorna todos os valores de um dicionário
items dicio.items() Retorna os elementos chave-valor de um dicionário
get dicio.get(chave) Retorna o valor de uma chave ou None se não achar
get dicio.get(chave) Retorna o valor de uma chave ou alt se não achar
44
04
Listas Lineares
Olá novamente!
Nativamente, a linguagem Python já oferece formas de trabalhar coleções de dados
como as Listas, Dicionários e Tuplas, mas conforme a necessidade e complexidade da
aplicação desenvolvida, usar tais soluções não se tornam suficientes e é necessário
desenvolver uma estrutura de dados nova para suportar a representação e a
manipulação dos dados (MILLER e RANUM, 2013).
Surgem as listas ligadas ou listas encadeadas como solução para construir coleções
de dados em que cada elemento mantém um posicionamento relativo aos demais,
conseguindo navegar através de métodos pelos elementos e também garantir
determinada ordenação e controle (SZWARCFITER e MARKENZON, 2017; MILLER e
RANUM, 2013).
Ainda dentro das listas ligadas, temos as listas ordenadas e desordenadas, em que
os elementos são ou não organizados conforme são inseridos na lista, e mesmo
sendo próximas, são implementações totalmente distintas, pois agora a estrutura de
dados será criada praticamente do zero (SZWARCFITER e MARKENZON, 2017;
GUIMARÃES, 1984).
Outras estruturas de dados também lineares que ganham espaço são as pilhas, filas e
deques. Cada uma delas tem seu funcionamento muito bem definido, porém, ainda
trabalham com a relação e disposição em um ambiente em que todos os elementos
se relacionam e estão interligados. 
46
Para sempre lembrar a evolução das Listas, Tuplas e Dicionários nativos do
Python para as listas lineares que podemos implementar, é só lembrar das
ações possíveis com cada elemento, ou seja, o que um elemento de uma
lista simples pode fazer? Se ele for um tipo primitivo (texto, inteiro, float ou
booleano), não vai conseguir fazer muita coisa, apenas algumas operações.
Se ele for um tipo abstrato, como, por exemplo, uma classe, vai conseguir
executar os métodos dessa classe que ele pertence.
Porém, ao construir uma estrutura linear como as listas encadeadas, filas e
pilhas, é possível criar métodos e atributos para cada elemento,
independentemente de seu conteúdo e que vão interagir com os demais
elementos da estrutura. Um bom exemplo é a Lista Ordenada Encadeada,
que ordenada a lista assim que o elemento é inserido.
Quando falamos que os objetos e elementos de uma estrutura linear estão
interligados e se relacionam, é algo concreto, pois cada nó criado para armazenar um
valor faz referência direta aos dois elementos vizinhos, criando uma forma de
corrente e garantindo a estabilidade da estrutura (SZWARCFITER e MARKENZON,
2017; GUIMARÃES, 1984).
A Imagem 2 traz a representação gráfica do que seria um nó de um elemento em uma
estrutura linear, fazendo referência aos seus nós próximos.
47
Imagem 2 – Exemplo de nó em uma estrutura de dados linear.
Fonte: Próprio autor.
Como estas estruturas são construídas pelos próprios desenvolvedores ou
comunidade para atender as necessidades de um cenário ou domínio, também existe
a necessidade de criar métodos ou ações de controle para garantir o funcionamento
perfeito da estrutura. 
E aí surgem alguns questionamento tais como: qual é o nó final e o nó inicial? Qual a
melhor maneira de navegar entre os nós? Existe a possibilidade de fazer uma busca
entre todos os elementos? Se todos os nós têm referência, como fazer uma exclusão
sem perder a referência?
Esses questionamentos são solucionados de diferentes formas conforme a proposta
de cada uma das estruturas. Por exemplo, quanto à pilha e fila, a pilha é conhecida
como LIFO (Last-In First-Out) por causa da forma como escreve e recupera os
elementos inseridos na pilha, e a fila é conhecida como FIFO (First-In First-Out), pois já
trata o processamento dos nós de uma forma diferente, mas ainda linear.
A Imagem 3 traz uma representação genérica das estrutura de dados lineares, onde
cada elemento mantém um relacionamento com os nós próximos e tem métodos
implementados.
48
Imagem 3 – Representação de uma estrutura linear.
Fonte: Próprio autor.
As próximas aulas serão dedicas a aprofundar de forma individual cada uma das
estruturas citadas aqui, passando por conceitos e detalhes da implementação, em
que iremos desenvolver cada uma delas.
49
05
Listas Lineares 
Desordenadas
Como vimos, as estruturas de dados de listas lineares podem ser implementadas de
diversas formas conforme os objetivos e a necessidade. A primeira estrutura cuja
implementação veremos com mais detalhes são as Listas Lineares Desordenadas,
onde a sua estrutura permite a inclusão, busca e remoção de elementos e nós sem a
necessidade de acontecer a ordenação dos elementos (SZWARCFITER e MARKENZON,
2017; MILLER e RANUM, 2013; GUIMARÃES, 1984).
Assim como nas demais estruturas de listas e dicionários em Python, existem algumas
operações possíveis sobre uma lista desordenada. A Tabela 1 apresenta a relação de
operações e sua descrição (MILLER e RANUM, 2013).
Para conseguir implementar uma lista desordenada, precisamos nos lembrar do
conceito de lista ligada, onde os elementos mantêm um posicionamento relativo aos
demais elementos da lista, ou seja, um nó faz referência a outro nó. Essa estrutura
permite trabalhar com uma capacidade de memória maior, pois não necessariamente
todo o conteúdo estará alocado em um único endereço de memória. 
51
Tabela 1 – Operações para Listas Desordenadas em Python
Fonte: Próprio autor.
Operador Descrição
List() Cria uma nova lista vazia.
add(elemento) Insere um novo elemento na lista.
remove(elemento) Remove um elemento da lista e altera a referência dos nós.
search(elemento)
Procura um elemento na lista, precisa informar qual
elemento e retorna True ou False.
isEmpty() Valida se a lista está vazia, retorna True ou False.
size() Extrai parte de uma lista.
append(elemento)
Insere um novo elemento no final da lista, tornando o final
da lista.
index(elemento) Retorna a posição referente a um elemento da lista.
insert(posição,
elemento)
Insere um novo emento na lista em uma determinada
posição.
pop()
Remove e retorna o último elemento da lista, tendo que a
lista deve ter no mínimo um elemento.
pop(posição)
Remove e retorna o elemento em uma determinada
posição.
Para implementar uma estrutura de lista desordenada, precisamos de dois itens bem
definidos: o nó, que representa cada elemento que compõe a lista, e a lista
desordenada, que é justamente a coleção de nós criados que respeitam uma relação.
Tanto o nó quanto a lista têm ações e dados bem definidos, sendo que para cada nó,
52
Imagem 2 – Classe Node em Python.
Fonte: autor.
precisamos ter um valor representado por um campo de dados, ou seja, um local
onde poderemos escrever o valor do elemento. Além disso, deve ter uma referência
direta ao próximo nó da lista, enquanto a lista desordenada precisa ter uma
referência de onde é o início da lista e a implementação das operações listadas na
Tabela 1 (SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013).
Para criar nossa Lista Desordenada Ligada em Python, vamos começar criando duas
classes: a classe Node e a classe UnorderedList. A classe Node irá conter o campo de
dados e a referência do próximo nó, enquanto a classe UnorderedList será a
responsável pela coleção de nós.
A Imagem 2 traz o código a ser implementado para a classe Node,ao analisar o
código é possível notar que tem dois atributos o “data” e o “next”, onde o “data” irá
conter realmente o valor do elemento e o “next” faz referência ao próximo nó. As
funções “setData()” e “getData()” são responsáveis por manipular os dados do nó,
inserindo e lendo, respectivamente, o dado de cada nó.
class Node:
   def __init__(self,element):
       self.data = element
       self.next = None
   def getData(self):
       return self.data
   def getNext(self):
       return self.next
   def setData(self,newdata):
       self.data = newdata
   def setNext(self,newnext):
       self.next = newnext
53
Imagem 3 – Representação gráfica instância da classe Node.
Fonte: Próprio autor.
Imagem 4 – Classe UnorderedList em Python.
Ao analisar a Imagem 2, vemos o método __init__ que é o construtor, ou seja, é
executado cada vez que um novo nó for criado. Nesse método, é informando o
parâmetro “element” que é o dado em si que estará presente representado no nó.
Outro detalhe importante nesse método é o atributo next, que faz referência ao
próximo nó, e neste caso, é criada uma referência vazia ou None.
A Imagem 3 é uma representação gráfica de um nó criado pela nossa classe Node.
Podemos ver a instância de Node, representada pelo círculo, e está contida em uma
variável. O atributo next faz referência a algo nulo (None).
Com a nossa classe Node criada, precisamos criar a classe que irá definir a lista em si e
controlar os nós, tornando possíveis as operações e referências aos nós. Para isso,
iremos criar a classe UnorderedList, no momento criada no mesmo arquivo que a
classe Node. A Imagem 4 traz o código que implementa a classe em questão.
class UnorderedList:
   def __init__(self):
       self.head = None
   def isEmpty(self):
       return self.head == None
   def add(self,element):
54
       temp = Node(element)
       temp.setNext(self.head)
       self.head = temp
   def size(self):
       current = self.head
       count = 0
       while current != None:
           count = count + 1
           current = current.getNext()
       return count
   def search(self,element):
       current = self.head
       found = False
       while current != None and not found:
           if current.getData() == element:
               found = True
           else:
               current = current.getNext()
       return found
   def remove(self,element):
       current = self.head
       previous = None
       found = False
       while not found:
           if current.getData() == element:
               found = True
           else:
               previous = current
               current = current.getNext()
       if previous == None:
           self.head = current.getNext()
       else:
55
Fonte: autor.
Imagem 5 – Método isEmpty na classe UnorderedList.
Fonte: Próprio autor.
Imagem 6 – Método add na classe UnorderedList.
Fonte: Próprio autor.
           previous.setNext(current.getNext())
Ao analisar a Imagem 4, o primeiro ponto de atenção é no método construtor (__init__)
que já cria um atributo para definirmos o nó inicial da nossa lista. Esse ponto define
se a lista está vazia ou não. O método isEmpty() retorna se a lista está vazia ou não,
mostrado com detalhe na Imagem 5. Esse método compara o atributo head da lista,
se este estiver None, significada que a lista está vazia.
def isEmpty(self):
   return self.head == None
Para fazer a inserção de um novo nó na lista, existe o método add, que irá criar um
novo nó com o valor do elemento passado por parâmetro. Importante notar o local
da lista onde será inserido o novo nó, sem esquecer que estamos trabalhos com uma
estrutura de lista ligada, logo, sempre inserimos um novo nó pela ponta da lista.
Nesse caso, será necessário o atributo head da lista, colocando como referência o
novo nó criado. A Imagem 6 demonstra com detalhes o método add.
def add(self,element):
   temp = Node(element)
   temp.setNext(self.head)
   self.head = temp
56
Imagem 7 – Método remove na classe UnorderedList.
Fonte: autor.
Outro método importante e que merece atenção para analisar as ações necessárias é
o remove(). Para o seu funcionamento perfeito, é necessário fazer uma busca para
identificar qual elemento será removido. Novamente, por ser uma lista encadeada, a
cada alteração realizada na estrutura é necessário atualizar a referência entre os nós
para que não ocorram erros ou se percam dados. Assim, o nó antecessor ao
removido fará referência ao posterior.
A Imagem 7 traz o método remove por completo. Repare que existe uma estrutura de
repetição while para iterar entre os nós presentes na lista e caso o elemento desejado
seja encontrado, será feita a remoção do nó e a alteração das referências. Caso o nó
seja o primeiro da fila, então o nó head será alocado para fazer referência ao nó
posterior ao que está sendo removido.
def remove(self,element):
   current = self.head
   previous = None
   found = False
   while not found:
       if current.getData() == element:
           found = True
       else:
           previous = current
           current = current.getNext()
   if previous == None:
       self.head = current.getNext()
   else:
       previous.setNext(current.getNext())
57
06
Listas Lineares 
Ordenadas
O primeiro passo ao se pensar no desenvolvimento de uma lista ligada é entender
que cada elemento ou nó é relativo aos seus nós vizinho, antecessor e posterior. Caso
seja o primeiro nó, é apenas o posterior. Porém, imaginemos que precisamos inserir
um novo nó em nossa lista, mas o funcionamento normal das Listas e Dicionários em
Python é inserir o elemento no final da lista, sem se preocupar com a ordem naquele
momento (SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013; GUIMARÃES,
1984).
Vamos supor uma lista de idade que sempre deve apresentar do mais novo para o
mais velho. Imediatamente após ser modificada, entra o papel da lista ordenada,
onde a ordenação é tipicamente ascendente ou descendente – isso supondo que já
esteja definida qual é a operação de comparação que vai definir isso.
Podemos relacionar algumas operações para Lista Ordenadas que são próximas às
demais listas, como: 
59
Tabela 1 – Operações para Listas Desordenadas em Python
Fonte: Próprio autor.
Operador Descrição
OrderedList() Cria uma nova lista ordenada vazia.
add(elemento)
Insere um novo nó na lista, certificando-se de que a ordem
é preservada.
remove(elemento) Remove o nó da lista. Supõe que o elemento esteja na lista.
search(elemento)
Procura o elemento na lista. Retorna um booleano (bool);
True se o item está na lista ou False se falhar.
isEmpty()
Testa se a lista está vazia. Retorna um booleano (bool); True
se a lista está vazia e False caso a lista não esteja vazia.
size() Retorna o número de nós na lista. Retorna um inteiro.
index(elemento) Retorna a posição de um elemento na lista.
pop()
Remove e retorna o último elemento da lista, tendo que a
lista deve ter no mínimo um elemento.
pop(posição)
Remove e retorna o elemento em uma determinada
posição.
60
Imagem 2 – Exemplo de Lista Ligada Ordenada
Fonte: Próprio autor.
A implementação das listas ordenadas e não ordenadas compartilha diversas
operações, pois a base do funcionamento das listas lineares é a mesma. Para a
implementação de listas ordenadas, é importante lembrar ainda as posições relativas,
onde um nó faz referência a outro nó, criando um encadeamento dos elementos, que
é essencial para manutenção e sucesso da estrutura (SZWARCFITER e MARKENZON,
2017; MILLER e RANUM, 2013).
A Imagem 2 apresenta um exemplo de Lista Ligada Ordenada já com nós
representados.
Para a implementação de listas ordenadas, também vamos criar duas classes uma
Node para representar cada nó da nossa lista e outra classe para a lista em si, nesse
caso, a classe OrderedList.
A classe Node utilizada para lista ordenada é a mesma utilizada para lista
desordenada, pois a base das listas lineares ligadas, o nó, apresenta o mesmofuncionamento e sempre contém um valor e faz referência a outro nó. O que muda é
como a lista itera e representa os elementos.
A Imagem 3 apresenta a classe Node desenvolvida para ser aplicada com listas
ordenadas.
61
Imagem 3 – Classe Node em Python – Lista Ordenadas.
Fonte: autor.
class Node:
   def __init__(self,element):
       self.data = element
       self.next = None
   def getData(self):
       return self.data
   def getNext(self):
       return self.next
   def setData(self,newdata):
       self.data = newdata
   def setNext(self,newnext):
       self.next = newnext
Assim como a classe Node pode ser compartilhada entre estrutura de listas ordenadas
e não ordenadas, algumas operações da lista em si podem ser compartilhas também,
neste caso, os métodos isEmpty() e size(). Ambas as funções continuam se
comportando da mesma forma, pois não precisam se preocupar com como a lista
está organizada.
O método remove, mesmo que realize iterações dentro da lista para encontrar o nó a
ser removido, pode também ser aproveitado na classe de listas ordenadas, pois neste
caso a ordenação diferente não vai impossibilitar a busca. Por outro lado, pode até
ser mais rápida a execução. Dessa forma, apenas os métodos search() e add()
necessitam de alterações para ter o devido funcionamento.
62
Imagem 4 – Método search – Lista Ordenadas.
Fonte: autor.
A alteração no método search() é necessária, pois sabendo que a lista é ordenada,
podemos otimizar sua execução, e a cada nó testado validamos se o valor é menor
que o valor presente no caso. E caso seja, isso quer dizer que já foram testadas todas
as possibilidades de sucesso e o valor não foi encontrado, assim não precisamos
percorrer a lista inteira.
Por exemplo, se quisemos encontrar o valor 11 na lista da Imagem 2, quando o
algoritmo testar o nó que tem o valor 9, ele vai ver que o valor é diferente, porém, 11
ainda é maior que 9, então ele testa o próximo nó, com valor 13. O valor não é o que
queríamos, mas 11 é menor que 13, e como a lista é ordenada, quer dizer que existe
11 em mais nenhum nó da lista, já interrompendo a busca.
A Imagem 4 demonstra como ficou a implementação deste método com as alterações
citadas.
def search(self,element):
   current = self.head
   found = False
   stop = False
   while current != None and not found and not stop:
       if current.getData() == element:
           found = True
       else:
           if current.getData() > element:
               stop = True
           else:
               current = current.getNext()
 
   return found
63
Imagem 5 – Método add – Lista Ordenadas.
Todavia, o método que sofre a maior alteração para a implementação de listas
ordenadas ligadas é o método de inclusão de novos nós e elementos, pois o ele já
deve inserir o novo valor em uma posição que já esteja ordenada. Para isso, é
necessário criar uma iteração dentro da lista para buscar o local onde o nó se encaixa,
ou seja, onde o seu antecessor é menor que o novo elemento e o posterior seja maior
que o novo elemento também.
Para isso, é utilizada uma estrutura similar ao método search que iremos iterar dentro
da lista até encontrar a melhor posição. Caso não a encontre, o novo é inserido no
final da lista, pois indicada ser o elemento com maior valor. Porém, caso seja
encontrado um intervalo que o mesmo será inserido, deve-se identificar onde foi o nó
da busca e fazer as alterações necessárias. A Imagem 5 demonstra como ficou o
método add com as alterações.
Com essas alterações feitas na classe, temos pronta a implementação da estrutura de
Lista Ligada Ordenada, utilizando das classes Node e OrderedList. A Imagem 6
demonstra como ficou a implementação da classe OrderedList.
def add(self,element):
       current = self.head
       previous = None
       stop = False
       while current != None and not stop:
           if current.getData() > element:
               stop = True
           else:
               previous = current
               current = current.getNext()
       temp = Node(element)
       if previous == None:
           temp.setNext(self.head)
           self.head = temp
64
Fonte: autor.
Imagem 6 – Classe OrderedList.
       else:
           temp.setNext(current)
           previous.setNext(temp)
class OrderedList:
   def __init__(self):
       self.head = None
   def search(self,element):
       current = self.head
       found = False
       stop = False
       while current != None and not found and not stop:
           if current.getData() == element:
               found = True
           else:
               if current.getData() > element:
                   stop = True
               else:
                   current = current.getNext()
       return found
   def add(self,element):
       current = self.head
       previous = None
       stop = False
       while current != None and not stop:
           if current.getData() > element:
65
Fonte: autor.
               stop = True
           else:
               previous = current
               current = current.getNext()
       temp = Node(element)
       if previous == None:
           temp.setNext(self.head)
           self.head = temp
       else:
           temp.setNext(current)
           previous.setNext(temp)
 
   def isEmpty(self):
       return self.head == None
 
   def size(self):
       current = self.head
       count = 0
       while current != None:
           count = count + 1
           current = current.getNext()
       return count
66
07
Pilhas
Uma pilha, ou no inglês stack, assim como as demais listas lineares vistas até o
momento, é uma coleção de itens, neste caso de maneira ordenada. Sua principal
diferença com as demais é que a inserção de novos itens e a remoção de itens já
existentes ocorrem sempre na mesma extremidade ou fila, onde tal ponto é
normalmente chamado de topo, enquanto a outra extremidade é conhecida como
base (SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013; GUIMARÃES,
1984).
Ao analisar uma pilha, sempre que se notarem os elementos mais próximos da
extremidade base, quer dizer que são itens que estão na pilha há mais tempo. Assim,
o elemento que estiver mais próximo do topo ou no topo, quer dizer que foi inserido
na pilha mais recentemente ou foi o último inserido, logo, deixará a pilha antes.
Sempre o último inserido será o primeiro a ser removido, e esse conceito é tido como
LIFO (last-in firt-out) (SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013;
GUIMARÃES, 1984).
Podemos observar diversas pilhas implementadas no mundo real, ao nosso
redor, quando vamos a um restaurante self-service, por exemplo. Precisamos
pegar a bandeja para nos servir, e há uma pilha de bandejas, em que os
clientes sempre vão retirar a que está mais em cima e as bandejas novas
que chegarem serão utilizadas primeiro. Podemos também pensar em uma
pilha de pratos, livros, roupas na gaveta do armário e outros cenários, mas é
um conceito importante de sempre ter em mente, pois ele aparece em
diversas aplicações computacionais.
Observando bem o comportamento das pilhas, podemos notar um que é   muito
importante para as aplicações computacionais, em que a ordem que os elementos
são removidos da pilha é o inverso da ordem de inserção, e assim são aplicadas para
68
Imagem 2 – Comportamento de uma pilha de dados.
Fonte: Adaptado de Miller e Ranum, 2013.
a inversão ou reversão de processos. A Imagem 2 demonstra como seria a ordem de
chegada e saída de uma pilha (SZWARCFITER e MARKENZON, 2017; MILLER e RANUM,
2013).
Você consegue pensar em alguma aplicação das pilhas no seu dia a dia com
o uso do celular com computador? Uma aplicação que usamos quase
diariamente é o botão voltar do navegador ou de qualquer outro app, em
que se vai criando uma pilha das páginas que navegamos, e toda vez que o
“voltar página” é chamado, ele tira o último elemento da pilha – neste caso, a
página – e apresenta no navegador novamente. Quanto maisantiga a
página, mais na base da pilha está e mais vai demorar a sair.
69
Para implementar uma pilha em Python, podemos relacionar algumas operações que
devem ser contempladas, assim, a Tabela 1 apresenta as possíveis operações sobre
uma pilha.
Tabela 1 – Operações para Pilhas em Python
Fonte: Próprio autor.
Operador Descrição
Stack() Cria uma nova pilha vazia.
push(elemento) Insere um novo elemento na pilha.
pop() Remove o elemento no topo da pilha e retorna o elemento.
peek()
Retorna o elemento no topo da pilha, mas não remove da
pilha.
isEmpty()
Testa se a pilha está vazia. Retorna um booleano (bool); True
se a pilha está vazia e False caso não esteja vazia.
size() Retorna o número de elementos na pilha. Retorna um inteiro.
Vamos dar início à implementação da nossa própria pilha em Python. Como já vimos,
o Python conta com diversos recursos que podem facilitar o desenvolvimento de
novas estruturas de dados e tipos de dados abstratos. Assim, para desenvolver a
nossa pilha, vamos criar uma nova classe com nome de Stack e utilizar uma lista
nativa de Python como base. Tendo isso, vamos escrever as operações que vimos na
Tabela 1 como métodos da nossa nova classe.
Ainda contamos com alguns métodos nativos para listas que podem nos auxiliar na
nossa pilha, como o append() e o pop(). Só temos que ficar atentos qual das
extremidades da lista vamos utilizar como topo e qual será a base. Na nossa
implementação, vamos assumir que o final da lista terá o elemento do topo, ou seja,
aquele mais recente na pilha, assim podemos usar o append() junto à operação de
push e o pop().
70
Imagem 3 – Classe Stack para implementação de pilhas em Python.
Fonte: autor.
A Imagem 3 traz o código da classe Stack, ou seja, nossa implementação de pilha.
Nota-se que no método construtor existe a declaração de uma variável elements que é
uma lista Python vazia, e os demais métodos como push e pop utilizam os métodos
Python a partir desta variável elements.
class Stack:
    def __init__(self):
        self.elements = []
 
    def isEmpty(self):
        return self.elements == []
 
    def push(self, item):
        self.elements.append(item)
 
    def pop(self):
        return self.elements.pop()
 
    def peek(self):
        return self.elements[len(self.elements)-1]
 
    def size(self):
        return len(self.elements)
A Imagem 4 traz uma execução da pilha criada por nós, utilizando como exemplo o
cenário de entrada e saída que utilizamos na Figura 2 para demonstrar o
funcionamento de uma pilha.
71
Imagem 4 – Exemplo de execução de uma pilha.
Fonte: autor.
>>> pilha = Stack ()
>>> print (pilha.isEmpty())
True
>>> pilha.push(10)
>>> pilha.push(20)
>>> pilha.push(pilha.peek())
20
>>> pilha.push(True)
>>> print(pilha.size())
3
>>> print(pilha.isEmpty())
False
>>> pilha.push("AB")
>>> print(pilha.pop())
AB
>>> print (pilha.pop())
True
>>> print (pilha.size())
2
72
08
Filas
A fila, ou queue em inglês, é uma coleção de itens de maneira ordenada, cujo
funcionamento normal se aproxima da estrutura de pilha. Porém, sua principal
diferença em relação à pilha é que a inserção de novos elementos na estrutura
acontece em uma extremidade, normalmente no “fim” (rear), enquanto a remoção
dos elementos ocorre do outro lado da fila, o “início” (front) (SZWARCFITER e
MARKENZON, 2017; MILLER e RANUM, 2013; GUIMARÃES, 1984).
Diferentemente da pilha em que o último elemento inserido na estrutura é o primeiro
a sair, nas filas o elemento inserido no fim da fila faz todo o caminho, respeitando a
ordem de chegada até que seja o próximo elemento a ser removido.
Assim, o elemento que estiver há mais tempo na fila está mais próximo de sair, logo, o
primeiro a entrar é o primeiro a sair, conceito tido como FIFO (first-in firt-out). A
estrutura de uma fila é bem definida e restritiva, pois tem apenas uma forma de
entrada e uma forma de saída, e não é permitido furar a fila ou sair antes de ter
esperado o tempo ou ordem correta (SZWARCFITER e MARKENZON, 2017; MILLER e
RANUM, 2013; GUIMARÃES, 1984). 
Assim como podemos encontrar pilhas ao nosso redor no mundo, a fila está
tão presente quanto. Os exemplos são inúmeros: filas de cinema e
restaurante, lista de chamada da faculdade e até mesmo calendários ou
listas de afazeres. Pensando dentro da Tecnologia da Informação, temos
diversos cenários possíveis, como o escalonamento de tarefas de um
processador (scheduling) ou uma impressora, que gerencia a fila de
impressões por ordem de chegada.
A Imagem 2 traz um representação gráfica de como a fila gerencia seus elementos e
como seguem o fluxo do fim até o início.
74
Imagem 2 – Comportamento de uma fila de dados.
Fonte: Adaptado de Miller e Ranum, 2013.
A estrutura de dados é também um tipo de dado abstrato que conta com estrutura e
operações bem definidas e que permitem organizar o fluxo de elementos inseridos e
removidos. É importante lembrar sempre do fluxo dentro da fila para definir as
operações. Os novos elementos são inseridos no fim da fila (assim como no mundo
real) e são removidos no início da fila (MILLER e RANUM, 2013).
Tendo isso claro, a Tabela 1 relaciona e define as operações necessárias para a
construção de uma estrutura de dados de fila.
Tabela 1 – Operações para filas em Python
Fonte: Próprio autor.
Operador Descrição
Queue() Cria uma nova fila vazia.
enqueue(elemento) Insere um novo elemento no final da fila.
dequeue()
Remove o elemento do início da fila. Retorna um elemento
e altera a fila.
isEmpty()
Testa se a fila está vazia. Retorna um booleano (bool); True
se a fila está vazia e False caso não esteja vazia.
size()
Retorna o número de elementos na fila. Retorna um
inteiro.
75
Vamos dar início à implementação da nossa própria fila em Python. Como já vimos, o
Python conta com diversos recursos que podem facilitar o desenvolvimento de novas
estruturas de dados e tipos de dados abstratos. Para desenvolver a nossa fila, vamos
criar uma nova classe com nome de Queue e novamente utilizar uma lista nativa de
Python como base, assim como fizemos com a pilha. Tendo isso, vamos escrever as
operações que vimos na Tabela 1 como métodos da nossa nova classe.
Ainda contamos com alguns métodos nativos para listas que podem nos auxiliar na
nossa fila, tais como o insert() e o pop(). Só temos que ficar atentos qual das
extremidades da lista utilizar como fim e qual será o início. Na nossa implementação,
vamos assumir que o fim da fila está na posição 0 da lista, e desta maneira, podemos
usar a função insert(), nativa do Python, para adicionar elementos novos no final da
fila.
Também iremos aplicar a função pop() para remover os elementos no início da fila, e
atente-se bem: o fim da nossa fila será na posição 0 da lista (início da lista) e o nosso
início da fila, onde os elementos serão retirados, é o fim da lista (último elemento da
lista).
A Imagem 3 traz o código da classe Queue, ou seja, na nossa implementação de fila,
nota-se que no método construtor existe a declaração de uma variável elements, que é
uma lista Python vazia, e os demais métodos como insert e pop utilizam os métodos
Python a partir desta variável elements.
76
Imagem 3 – Classe Queue para implementação de filas em Python.
Fonte: autor.
class Queue:
   def __init__(self):
       self.elements = []
   def isEmpty(self):
       return self.elements == []
   def enqueue(self, item):
       self.elements.insert(0,item)
   def dequeue(self):
       return self.elements.pop()
   def size(self):
       return len(self.elements)
A Imagem 4 traz uma execução da fila criada por nós, utilizando como exemplo o
cenário de entrada e saída que utilizamos na Figura 2 para demonstrar o
funcionamento de uma fila.
77
Imagem 4 – Exemplo de execução de uma fila.
Fonte: autor.
>>> from Queue import Queue
>>> fila = Queue()
>>> fila.enqueue(10)
>>> fila.enqueue(20)
>>> print(fila.size())
2
>>> fila.enqueue(True)
>>> print(fila.size())
3
>>> print(fila.isEmpty())
False
>>> fila.enqueue("AB")>>> fila.dequeue()
10
>>> fila.dequeue()
20
>>> print(fila.size())
2
78
09
Deque
Imagem 2 – Comportamento de um deque de dados.
Fonte: Adaptado de Miller e Ranum, 2013.
A estrutura de dados deque, ou também fila de duas extremidades, assim como as
estrutura de dados que vimos, é uma coleção de dados ordenada de elementos. A
estrutura de construção de um deque se aproxima da fila, porém com algumas
diferenças que fazem diferença nas suas funcionalidades.
Assim como a pilha e a fila, um deque possui duas extremidades, em que uma é o
início (front) e outra é o fim (rear). Os elementos continuam com posições referentes
dentro da estrutura. Porém, diferentemente das filas, o deque tem uma natureza
menos restritiva de inclusão e exclusão de elementos, assim, novos elementos podem
ser incluídos e excluídos no início ou no fim da estrutura (SZWARCFITER e
MARKENZON, 2017; MILLER e RANUM, 2013).
O deque se caracteriza como uma estrutura híbrida, ou seja, pode assumir as
capacidades de pilhas e filas, dependendo de como for executada – isso em uma
única estrutura. É importante ressaltar, todavia, que mesmo que o deque possa
assumir o comportamento de pilhas e filas, um deque não é necessário à ordenação
LIFO ou FIFO como a fila e a pilha. A principal responsabilidade da estrutura é
promover o uso consistente das operações de inclusão e exclusão de elementos
(MILLER e RANUM, 2013).
A Imagem 2 traz uma representação gráfica de como o deque gerencia seus
elementos e como é possível fazer as ações de inclusão e exclusão do fim ou no início
da estrutura. 
A estrutura de dados é também um tipo de dado abstrato, contando com estrutura e
operações bem definidas que permitem organizar o fluxo de elementos inseridos e
removidos. É importante lembrar sempre do fluxo dentro da fila para definir as
operações, e os novos elementos podem ser alterados nas duas pontas, ou seja,
pode-se incluir ou excluir tanto no fim da fila quanto no início dela.  Por esse motivo, o
deque é conhecido como fila dupla (MILLER e RANUM, 2013).
80
Tendo isso claro, a Tabela 1 relaciona e define as operações necessárias para a
construção de uma estrutura de dados de deque.
Tabela 1 – Operações para Deque em Python
Fonte: Próprio autor.
Operador Descrição
Deque() Cria um novo deque vazio.
addFront(elemento) Insere um novo elemento no início do deque.
addRear(elemento) Insere um novo elemento no fim do deque.
removeFront()
Remove o elemento do início do deque. Retorna um
elemento e altera o deque.
removeRear()
Remove o elemento do fim do deque. Retorna um
elemento e altera o deque.
isEmpty()
Testa se o deque está vazio. Retorna um booleano (bool);
True se o deque está vazio e False caso não esteja vazio.
size()
Retorna o número de elementos no deque. Retorna um
inteiro.
Vamos dar início à implementação do nosso deque em Python. Como já vimos, o
Python conta com diversos recursos que podem facilitar o desenvolvimento de novas
estruturas, e para desenvolver o nosso deque, vamos criar uma nova classe com
nome de Deque e novamente utilizar uma lista nativa de Python como base. Tendo
isso, vamos escrever as operações que vimos na Tabela 1 como métodos da nossa
nova classe.
Ainda contamos com alguns métodos nativos para listas que podem nos auxiliar no
nosso deque, como o insert(), append() e pop(). Só temos que ficar atentos a qual das
extremidades da lista vamos utilizar como fim e qual será o início. Na nossa
81
Imagem 3 – Classe Deque para implementação de filas duplas em Python.
Fonte: autor.
implementação, vamos assumir que o fim da fila está na posição 0 da lista
A Imagem 3 traz o código da classe Deque, ou seja, na nossa implementação de
deque, nota-se que no método construtor existe a declaração de uma variável
elements que é uma lista Python vazia, e os demais métodos como add e remove
utilizam os métodos Python a partir desta variável elements.
class Deque:
   def __init__(self):
       self.elements = []
   def isEmpty(self):
       return self.elements == []
   def addFront(self, item):
       self.elements.append(item)
   def addRear(self, item):
       self.elements.insert(0,item)
   def removeFront(self):
       return self.elements.pop()
   def removeRear(self):
       return self.elements.pop(0)
   def size(self):
       return len(self.elements)
82
Imagem 4 – Exemplo de execução de uma fila.
Fonte: autor.
A Imagem 4 traz uma execução do deque criado por nós, utilizando como exemplo o
cenário de entrada e saída que utilizamos na Figura 2 para demonstrar o
funcionamento de um deque.
>>> from Deque import Deque
>>> deque = Deque()
>>> print(deque.isEmpty())
True
>>> deque.addRear(10)
>>> deque.addRear(20)
>>> deque.addFront("AB")
>>> deque.addFront(True)
>>> print(deque.size())
4
>>> print(deque.isEmpty())
False
>>> deque.addRear(5.5)
>>> print(deque.removeRear())
5.5
>>> print(deque.removeFront())
True
83
10
Matrizes
Vimos até agora diversas estruturas de dados e como lidar com coleções de dados,
passando por tipos nativos do Python tais como listas e dicionários, mas também por
tipos de dados abstratos como listas ligadas, filas e pilhas. Porém, até agora todas as
estruturas têm algo em comum sobre o espaço dos dados: estão distribuídos em uma
única dimensão, o que pode limitar em alguns pontos a organização e distribuição
dos dados.
Agora, veremos o conceito de matrizes, que se caracterizam por serem estruturas de
dados bidimensionais, assemelhando-se a uma tabela e possuindo M linhas para N
colunas. O conceito de matriz tem sua origem na matemática, e são aplicadas em
diversas soluções importantes, por exemplo, para fazer análise de dispersão ou
resolução de sistemas de equações lineares (SZWARCFITER e MARKENZON, 2017;
PERKOVIC, 2016; GUIMARÃES, 1984).
Podemos olhar então uma matriz como uma lista multidimensional, ou seja, um vetor
com vetores.
Mas como podemos pensar nisso com a linguagem Python? Em Python, pensar como
uma lista de lista, ou seja, cada elemento de uma lista, como vimos anteriormente,
será uma lista (SZWARCFITER e MARKENZON, 2017; PERKOVIC, 2016). 
85
Imagem 2 – Exemplo matriz de alunos e notas.
Fonte: Próprio autor.
Para consolidar bem o conceito de matrizes, vamos pensar que precisamos
controlar as notas de uma turma de 10 alunos, porém, o aluno tem três
notas e precisamos implementar uma estrutura de dados que seja capaz de
associar 10 alunos com 3 notas, de forma que haja um controle e uma
relação entre cada aluno e suas respectivas notas.
Assim, podemos pensar da seguinte forma: criar uma lista em Python com
10 posições, onde cada posição se refere a um aluno, mas tem outra lista
com 3 posições para cada uma das notas. A Imagem 2 traz uma
representação gráfica de como ficaria a matriz para esse cenário.
Lembrado que assim como as listas, a contagem das posições sempre
começa em 0.
Como uma matriz é composta por um tipo nativo do Python de coleções (as listas), a
estrutura de dados é também um tipo de dado nativo, fazendo assim uso de todas as
funções e operações relacionadas a listas, como, por exemplo, a iteração e a
concatenação. Para a construção e a implementação de uma matriz, é necessário
86
Imagem 3 – Método para criação de matrizes com Python.
utilizar diversos recursos das estruturas de repetição tais como while e for. Com o uso
de ambas as estruturas junto com métodos personalizados é possível trabalhar com
matrizes em Python (SZWARCFITER e MARKENZON, 2017; PERKOVIC, 2016).
Para criar nossa primeira estrutura de dados com matrizes com Python, vamos
pensar em uma função capaz de receber o número de linhas e colunas necessárias,
então essa função ficará responsável por criá-las e depois veremos algumas formas
de iterar e navegar entre os dados de uma matriz.
A Imagem 3 demonstra o código da função feita para criar matrizes. A função recebe
três parâmetros, n_linhas, n_colunas e valor, que representam respectivamente a
quantidade de linhas que terá em nossa matriz, a quantidade de colunas que terána
matriz e por último o valor que será preenchido para criar as células.
Analisando o código, podemos ainda perceber que são utilizados dois comandos for
para iterar: um for fica responsável por iterar as linhas e o outro por iterar as colunas.
A função range é nativa do Python e faz o papel de criar um intervalo até o número
ordenado no parâmetro que, nesse caso, é o número de linhas ou colunas
necessárias.
def cria_matriz(n_linhas, n_colunas, valor):
matriz = [] # lista vazia
for i in range(n_linhas):
# cria a linha i
linha = [] # lista vazia
for j in range(n_colunas):
linha += [valor]
# coloque linha na matriz
matriz += [linha]
return matriz
Fonte: autor.
87
Imagem 4 – Método para impressão de matrizes com Python.
Esta função retorna a estrutura de dados da matriz já pronta para o uso, em que se
pode iterar e manipular os dados da forma como for necessário. Quando criamos
uma lista para acessar uma informação, em determinado índex utilizamos colchetes [
] com o índices desejado no meio. Porém, uma matriz é bidimensional, ou seja, temos
o índice X e Y, remetendo a um gráfico, só que aqui lidamos com linhas e colunas.
Assim, para acessar uma célula ou elemento específico em uma estrutura
bidimensional, serão necessários dois pares de colchetes, respeitando a seguinte
sintaxe:
matriz[linha][coluna]
Mas existe uma limitação em acessar elemento por elemento de uma matriz, dessa
forma, quanto maior a matriz, mais inviável se torna acessar os valores desta
maneira, principalmente não conhecendo o tamanho da matriz. Assim, podemos criar
outros métodos que podem auxiliar na interpretação e uso, e um dos primeiros e
essenciais a ser implementado é realizar uma impressão da matriz, ou seja, mostrar
todos os valores de uma forma estruturada.
A Imagem 4 demonstra o código desenvolvido para receber uma matriz qualquer por
parâmetro e então imprimi-la. Este método faz a análise da quantidade de linhas e
colunas, não fixando os valores, o que garante a ampla adoção do método.
def imprime_matriz(matriz):
linhas = len(matriz)#número de linhas
colunas = len(matriz[0])#número de colunas
for i in range(linhas):#iteração com linhas
for j in range(colunas):#iteração com colunas
print( str(matriz[i][j]) + " | ", end="" )
Fonte: autor.
print("\n")
88
Imagem 5 – Método para impressão de matrizes com Python.
Fonte: autor.
A Imagem 5 traz o resultado, a criação e a impressão de uma matriz 5 x 5 (5 linhas por
5 colunas).
>>> A = cria_matriz(5,5,0)
>>> imprime_matriz(A)
0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 |
Para realizar a alteração de um valor dentro de uma matriz, é necessário conhecer o
índice da linha e da coluna. A partir disso, é o processo de atribuição de valores,
porém, respeitando o acesso aos dados da matriz, da seguinte forma:
matriz[linha][coluna] = novo_valor
Para validar todos os conceitos e poder treinar a criação de matrizes e
outras estruturas lineares que vimos até agora, vale conferir o site
https://algoritmosempython.com.br que traz exemplos de diversas
estruturas de dados e conta também com uma sessão que consegue rodar
seu próprio algoritmo em Python no navegador.
89
11
Recursividade
Até o momento, estudamos diversas estruturas de dados, tipos de dados primitivos e
abstratos, passando por listas encadeadas, pilhas e filas, entre outros. Porém,
também precisamos ver formas de resolver e lidar com essas estruturas, pois o papel
de uma estrutura de dados é promover a melhor organização das informações e
possibilitar a construção de melhores processos computacionais a partir delas.
A construção de processos computacionais está diretamente ligada à resolução de
problemas, e uma das formas é aplicando a recursão. A recursão é definida como um
método que foca em resolver problemas quebrando-os em subproblemas, focando
na menor ação possível até que se consigo o problema mais simples que possa ser
resolvido (SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013; GUIMARÃES,
1984).
Apesar de ser uma definição simples e até abstrata, a técnica de recursão possibilita
desenvolver soluções poderosas que de outras formas talvez não fossem possíveis ou
de uma complexidade muito maior, além de garantir um código mais limpo e
elegante.
Vamos construir nosso primeiro método recursivo para resolver um problema
simples e assim compreender melhor a aplicação da recursividade. Um primeiro
ponto sobre toda recursão – e que se torna uma das suas principais característica – é
que um método deve chamar a si mesmo, ou seja, dentro da construção de um
método, existe uma condição que chama o próprio método, criando um loop, assim
como vimos nos comandos iterativos, e sempre ficamos atentos ao problema de gerar
um loop infinito (SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013).
O primeiro problema que será resolvido com a recursão é implementar a soma de
uma lista de número, e como exemplo vamos utilizar a lista: [1, 2, 4, 6, 8]. A Imagem 2
traz uma solução para a soma de lista, porém, ainda de forma iterativa utilizando o
comando for, junto com uma variável acumuladora que inicia com o valor 0 e vai
incrementar seu valor a cada nova iteração entre os elementos da lista.
91
Imagem 2 – Soma de lista de forma iterativa.
Fonte: Adaptado de Miller e Ranum, 2013.
def somaLista(numeros):
   soma = 0
   for i in numeros:
       soma = soma + i
   return soma
Existem outras formas de olhar para esse problema. Se perguntassem para um
matemático como poderia somar uma sequência de valores, ele iria citar o uso de
parênteses e que se poderia segmentar os valores a serem somados em pares. Se o
problema fosse escrito dessa forma, seria algo como:
((((1 + 2) + 4) + 6) + 8)
É possível também inverter a expressão sem alterar o resultado:
(1 + (2 + (4 + (6 + 8))))
Como de costume, iremos começar a resolver o problema do parêntese mais interno,
e nesse caso vamos alterar a expressão invertida. Observe que podemos implementar
um algoritmo com essa estrutura e sem comandos de repetição. A sequência a seguir
mostra como seria essa execução
Total = (1 + (2 + (4 + (6 + 8)))) 
Total = (1 + (2 + (4 + 14))) 
Total = (1 + (2 + 18)) 
Total = (1 + 20) 
Total = 21
Para escrever uma solução com essa lógica com a linguagem Python, é preciso pensar
a estrutura em que os dados estarão, neste caso, uma lista. Assim, podemos
considerar então que o resultado é obtido através da soma do primeiro elemento
92
Imagem 3 – Soma de lista de forma recursiva.
Fonte: Adaptado de Miller e Ranum, 2013.
com a soma do resto da lista. Para escrever o primeiro elemento da lista, vamos
utilizar colchetes para definir o índice e depois criar um recorte da lista. Pesando em
um método, a estrutura básica seria:
somaLista(numeros) = numeros[0] + somaLista(numeros[1:])
Nesta estrutura, primeiro é selecionado o primeiro elemento com o comando
numeros[0], e no segundo momento, o método somaLista é chamado novamente, mas
agora passando uma lista com o resto dos elementos, o comando numeros[1:] faz um
recorte na lista atual, pegando do elemento de índice de número 1 até o final, ou seja,
excluindo o primeiro elemento.
A Imagem 3 demonstra o código do método recursivo para soma de lista, observe que
não existem comandos de repetição, mas sim a chamada da própria função, criando
uma espécie de loop controlado para a soma.
def somaLista(numeros):
  if len(numeros) == 1:
       return numeros[0]
  else:
       return numeros[0] + somaLista(numeros[1:])
O primeiro ponto importante a ser notado nesse método é a validação de quantos
elementos estão presentes na lista “len(numero)”. Essa validação é essencial para
garantir o controle do algoritmo e não se tornar um loop infinito ou gerar erros.
Observe que quando a quantidade de elemento presente na lista for igual a 1, o
algoritmo retorna esse único elemento que está no índice 0 por padrão.
Neste caso, a recursão realmente acontece no segundo return, em que ele soma o
primeiro elemento com a somado restante dos elementos, e assim, a cada nova
interação é gerada uma nova lista para ser somada. Quando existe um único
93
elemento, o processo faz o caminho contrário e são feitas as somas. Em um primeiro
momento, pode parecer bem confuso, porém, é necessário prática e treino, e logo
será possível criar métodos recursivos cada vez mais complexos.
A Imagem 4 mostra a série de chamadas recursivas do nosso método para realizar a
soma da lista [1 + 2 + 4 + 6 + 8], lembrando que cada chamada recursiva foca em
resolver um problema menor que o interior, neste caso, um número a menos para ser
somado até restar apenas um valor. Cada seta representa uma nova chamada ao
método.
Imagem 4 – Chamadas recursivas do método somaLista.
Fonte: Adaptado de Miller e Ranum, 2013.
94
Imagem 5 – Returns recursivo das chamadas ao método somaLista.
Fonte: Adaptado de Miller e Ranum, 2013.
A Imagem 5 demonstra o retorno das chamadas mostradas na Imagem 4, ou seja, a 
realização efetiva de cada operação de soma.
95
12
Métodos de 
Ordenação I
Nas diversas estruturas de dados existentes, faz-se necessário conhecer, manipular,
iterar e identificar elementos que estão presentes em tais estruturas. Já vimos a
capacidade dos métodos recursivos em criar métodos poderosos e elegantes para
iterar entre as estruturas.
Há processos a serem implementados para estruturas de dados que podem se
aproveitar de recursividade e chegam a ser tão importante quanto ela: um deles é a
ordenação. O processo de ordenar elementos em estrutura de dados é ligado ao
básico de colocar os elementos em uma determinada ordem, por exemplo, uma lista
de nomes em ordem alfabética, uma lista de preços em ordem decrescente ou até
mesmo uma lista de palavras por ordem de tamanho (SZWARCFITER e MARKENZON,
2017; MILLER e RANUM, 2013; GUIMARÃES, 1984).
Diversas outras soluções em programação podem tirar benefícios da ordenação, tais
como algoritmos de busca ou soluções de anagrama. Essa possibilidade de aplicação
em diversas soluções computacionais sugere que os métodos de ordenação é uma
importante área de estudo. Outro fator que colabora com essa afirmação é a grande
quantidade de métodos de ordenação que já existem e são continuamente estudados
(SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013).
O desempenho dos métodos de ordenação está ligado a diversos fatores, como, por
exemplo, a quantidade de elementos: quanto maior a estrutura, mais desempenho
computacional é exigido para o processamento. Outro fator que implica é a
complexidade de desenvolvimento do método; por exemplo, um método muito
otimizado e complexo para a construção pode não valer a pena se for uma
quantidade pequena de elementos. Porém, grandes coleções de dados podem tirar
proveito dos métodos de ordenação mais complexos (MILLER e RANUM, 2013).
Antes de começar a desenvolver nossos métodos de ordenação, devemos considerar
alguns fatores, pois em todo método de ordenação existem comparações entre
valores, e para cada método uma forma de comparação pode ser elaborada,
normalmente de forma quantitativa para definir qual é maior ou menor. O segundo
passo é definir uma forma sistemática de comparação, ou seja, qual será a sequência
definida de comparação entre os elementos (SZWARCFITER e MARKENZON, 2017;
MILLER e RANUM, 2013).
97
Por fim, quando dois elementos são comparados e estão fora da devida ordenação,
necessitam ser trocados de posição. As operações de comparação dos valores e a
troca são custosas, ou seja, demandam bastante poder computacional, por isso
devem ser implementadas da melhor possível. Por esse motivo, cada método de
ordenação tem um determinado desempenho baseado em como é feita a
comparação e troca de elementos (SZWARCFITER e MARKENZON, 2017; MILLER e
RANUM, 2013).
Um dos métodos mais comuns e aplicados de ordenação é o bubble sort, método que
itera a lista a ser ordenada diversas vezes. Ele compara elementos que são vizinhos,
ou seja, o elemento no índice i com o elemento no índice i+1. Assim, a cada passagem
pela estrutura, o bubble sort ordena um par de valores, colocando-os na devida
posição (SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013).
A Imagem 2 traz o exemplo da primeira iteração em uma lista com valores inteiros a
ser ordenada pelo método bubble sort, cada linha representa um passo e comparação
feito pelo algoritmo dentro dessa primeira iteração. Os elementos destacados
representam os dois elementos que estão sendo comparados, e se estiverem fora da
ordem correta, neste caso a ordem crescente, apenas estes dois elementos são
trocados.
Ao final da primeira iteração, teremos uma ordenação parcial, tendo certeza que o
maior valor presente na lista já estará na última posição possível. Este processo vai
ocorrer a cada iteração, fazendo com que cada valor maior “flutue” até o final da fila,
por isso o nome bubble, “bolha” em inglês (MILLER e RANUM, 2013). 
98
Imagem 2 – Primeira iteração do método bubble sort.
Fonte: Adaptado de Miller e Ranum, 2013.
A Imagem 3 traz o código implementado para o nosso método bolha, e nota-se que
para realizar a troca dos elementos quando necessário, é utilizada uma variável
auxiliar (aux), recurso comum em diversos métodos de ordenação, em que se cria
uma área de swap para fazer a troca de valores, chamada de variável ou auxiliar ou
variável temporária.
99
Imagem 3 – Implementação do método bubble sort.
Fonte: Adaptado de Miller e Ranum, 2013.
Imagem 4 – Resultado bubble sort.
Fonte: Próprio autor.
def bubbleSort(list):
   for passnum in range(len(list)-1,0,-1):
       for i in range(passnum):
           if list[i]>list[i+1]:
               aux = list[i]
               list[i] = list[i+1]
               list[i+1] = aux
A Imagem 4 demonstra como seriam a chamada e o resultado obtido com a aplicação
deste método em uma lista pequena. Existem formas de calcular a complexidade
temporal e espacial deste algoritmo, porém, o foco desta disciplina é aprender o que
são as estruturas e como implementá-las.
>>> lista = [20, 5, 22, 3, 30, 27]
>>> bubbleSort(lista)
>>> print(lista)
[3, 5, 20, 22, 27, 30]
100
13
Métodos de 
Ordenação II
Vamos retomar um assunto da aula passada: embora o método de ordenação bubble
sort tenha sua eficiência comprovada, este é um dos métodos mais comuns, mas
ainda um dos menos otimizados ou aplicados para soluções mais complexas. Isso
levou a uma evolução de mais algoritmos de ordenação, sendo alguns baseados no
bubble sort.
O método de ordenação por seleção, ou selection sort, é um dos métodos inspirados
no bubble sort que já apresenta algumas melhorias. Este método realiza apenas uma
troca de valor por iteração na lista. A ordenação por seleção procura o maior valor na
passagem e depois de completar a iteração, o elemento de maior valor é trocado de
lugar, sendo alocado na posição correta. Assim, ao final da primeira iteração, o maior
valor estará na posição correta da lista, assim como no bubble sort (SZWARCFITER e
MARKENZON, 2017; MILLER e RANUM, 2013; GUIMARÃES, 1984).
Outra diferença que dá mais eficiência ao selection sort é que o algoritmo irá iterar
menos elementos a cada passagem, pois o algoritmo assume que a partir da segunda
iteração, o elemento de maior valor já estará no final da lista. Por exemplo, em uma
lista de 4 elementos na primeira iteração, serão processados os 4 elementos, na
segunda iteração 3 elementos, na terceira iteração 2 elementos e na última, apenas
um elemento (MILLER e RANUM, 2013).
A Imagem 2 traz um exemplo de um processo de ordenação completo através do
selection sort, em que cada linha representa uma iteração e cada iteração seleciona e
troca o maior valor dentro do intervalo de iteração. 
102
Imagem 2 – Exemplo de ordenação com selection sort.
Fonte: Adaptado de Miller e Ranum, 2013.
As Imagens 3 e 4 mostram respectivamente o código em Python do nosso método de
ordenação por seleção. Reparem que novamente é utilizada uma área de swap para
troca de valores, neste caso, a variável aux e o resultado obtidocom a ordenação.
103
Imagem 3 – Implementação do método Selection Sort.
Fonte: Adaptado de Miller e Ranum, 2013.
Imagem 4 – Resultado Selection Sort.
Fonte: autor.
def selectionSort(list):
  for fillslot in range(len(list)-1,0,-1):
      positionOfMax=0
      for location in range(1,fillslot+1):
          if list[location]>list[positionOfMax]:
              positionOfMax = location
 
      aux = list[fillslot]
      list[fillslot] = list[positionOfMax]
      list[positionOfMax] = aux
>>>lista = [20, 5, 22, 3, 30, 27]
>>> selectionSort(lista)
>>> print(lista)
[3, 5, 20, 22, 27, 30]
Outro método de ordenação que vamos estudar é a ordenação por inserção ou
insertion sort. Esse método é construído e tem uma execução diferente do bubble sort
e do selection sort, em que é criada uma sublista já ordenada nas posições da lista
principal, sendo que a cada nova iteração para ordenação um novo elemento é
“inserido” nessa sublista, de modo que já esteja ordenada e com o item a mais. A
104
Imagem 5 – Exemplo de ordenação com insertion sort.
Fonte: Adaptado de Miller e Ranum, 2013.
Imagem 5 traz um exemplo visual de como ocorre o insertion sort. Os elementos em
destaque representam a sublista já ordenada conforme as iterações feitas
(SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013; GUIMARÃES, 1984).
105
Imagem 6 – Implementação do método Insertion Sort.
Fonte: Adaptado de Miller e Ranum, 2013.
Imagem 4 – Resultado Insertion Sort.
Fonte: autor.
As Imagens 6 e 7 mostram respectivamente o código em Python do nosso método de
ordenação por inserção, neste caso, a área de swap para trocar os elementos a serem
ordenados está dentro de uma estrutura while, pois a troca é realizada dentro de uma
sublista que demanda essa segunda iteração entre somente os elementos ordenados.
def insertionSort(list):
  for index in range(1,len(list)):
    currentValue = list[index]
    position = index
    while position>0 and list[position-1]>currentValue:
        list[position] = list[position-1]
        position = position-1
    list[position] = currentValue
>>> lista = [20, 5, 22, 3, 30, 27]
>>>insertionSort(lista)
>>> print(lista)
[3, 5, 20, 22, 27, 30]
106
O estudo de métodos de ordenação pode ser levado muito longe, e existem
diversos métodos ainda melhores que podemos aprender e aplicar, sendo
umas das áreas que avançam entre as linhas de pesquisa científica,
juntamente com pesquisa de otimização computacionais e complexidade de
algoritmo.
Para se tornar ainda melhor com ordenação, é recomendada a pesquisa
sobre os métodos Shell Sort, Merge Sort e Quick Sort, pelos quais será possível
entender ainda mais e ver novas formas de implementar as ordenações de
estruturas de dados.
107
14
Métodos de Busca: 
Sequencial
Imagem 2 – Busca com operador in no Python.
Fonte: autor.
Durante os estudos e a implementação dos métodos de ordenação de estrutura de
dados, vimos o quão importante é buscar um valor ou elemento dentro de uma lista
de maneira eficiente e otimizada, uma vez que pode afetar diretamente o
desempenho do algoritmo e da solução como um todo.
A busca em si é caracterizada como um processo computacional capaz de localizar
um elemento específico em uma coleção, e a busca normalmente tem como resposta
padrão um valor boolenano (True ou False), correspondendo ao caso se o elemento
em questão foi encontrado ou não (SZWARCFITER e MARKENZON, 2017; MILLER e
RANUM, 2013; GUIMARÃES, 1984).
Em algumas variações de algoritmos de busca, também é possível retornar o valor do
elemento quando este é encontrado, e caso não for encontrado, retorna-se False ou
um valor nulo. Tratando especificamente da linguagem Python, esta já traz uma busca
implementada, facilitando validar se um determinado elemento está em uma lista de
elementos aplicando o operador in (SZWARCFITER e MARKENZON, 2017; MILLER e
RANUM, 2013).
A Imagem 2 traz a aplicação do operador in na linguagem Python, em que é
consultado dois valores, e por padrão retorna True ou False. 
>>> lista = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
>>> 2 in lista
False
>>> 11 in lista
True
109
Imagem 3 – Busca sequencial em valores inteiros.
Fonte: Adaptado de Miller e Ranum, 2013.
Apesar dessa solução em Python resolver parte dos problemas e ser fácil de
implementar, ainda existe um processo interno que não conhecemos, que está
abstraído e que é realmente como ocorre a busca entre os elementos. É importante
conhecer esse processo, uma vez que existem diferentes maneiras de implementar a
busca e diferentes técnicas. Vamos tratar de duas principais formas: a busca
sequencial e a busca binária (MILLER e RANUM, 2013).
A busca sequencial, como o próprio nome diz, é um algoritmo de busca de dados em
estruturas que segue um processamento linear e sequencial, acompanhando os
índices da estrutura consultada. Este método é especialmente aplicado quando os
dados estão em estruturas ou coleções como listas ou que se assemelham a tal
(MILLER e RANUM, 2013).
Como vimos em listas lineares, cada elemento é armazenado em uma posição relativa
aos demais. No Python, as posições relativas são os índices dos elementos presentes
na lista. Nativamente os índices são ordenados, o que permite um controle e iteração
com os itens de forma sequencial, processo que se caracteriza como a técnica de
busca sequencial.
A Imagem 3 traz uma representação gráfica do processo de busca sequencial em uma
lista de inteiros, indicando o ponto início e a iteração entre cada elemento da lista.
A Imagem 4 demonstra o nosso método de busca sequencial desenvolvido, e ao
analisar a função, percebe-se que são necessários dois parâmetros, a lista onde será
feita a busca(list) e qual valor quer ser encontrado(element). Para identificar o valor,
temos uma variável booleana que controla esse estado: a variável found, que inicia
com valor False, e quando o valor é encontrado, esta variável tem o valor alterado
para True.
110
Imagem 4 – Implementação do método de busca sequencial.
Fonte: Adaptado de Miller e Ranum, 2013.
Imagem 5 – Resultado da busca sequencial.
Fonte: autor.
def sequentialSearch(list, element):
   pos = 0
   found = False
 
   while pos < len(list) and not found:
       if list[pos] == element:
           found = True
       else:
           pos = pos+1
 
   return found
A Imagem 5 traz um exemplo de execução do nosso método de busca sequencial,
criando uma lista com os mesmo elementos da Imagem 3 e realizando dois casos de
teste, um com resposta False, pois o valor não foi encontrado na estrutura, e um com
resposta True, pois o valor foi encontrado com sucesso.
>>> lista = [3, 28, 52, 294, 1, 45, 27, 14, 89, 157]
>>> print(sequentialSearch(lista,9))
False
>>> print(sequentialSearch(lista,45))
True
111
15
Métodos de Busca: 
Binária
Imagem 2 – Busca sequencial em valores inteiros.
Fonte: Adaptado de Miller e Ranum, 2013.
Como vimos anteriormente na busca sequencial, é necessário passar por todos os
elementos comparando-os com o parâmetro a ser buscado. Porém, existem formas
de otimizar a busca, como por exemplo segmentar o trecho da lista em que será feita
a busca por valores, por exemplo, a busca binária que, ao invés de comparar
elemento por elemento, aplica um técnica diferente de movimentação.
A técnica de busca binária depende diretamente das técnicas de ordenação, pois uma
vez que a lista de busca está ordenada, conseguimos otimizar as ações de busca.
Assim, a busca binária compara segmentos inteiros, e não apenas valor por valor.
Pense da seguinte forma: você quer busca um valor X qualquer na lista, e se ela
estiver ordenada, podemos olhar o elemento do meio da lista e compará-lo,  e se este
for elemento buscado, já retorna True (SZWARCFITER e MARKENZON, 2017; MILLER e
RANUM, 2013; GUIMARÃES, 1984).
Porém, se este não for o elemento buscado, o algoritmo faz uma comparação: o valor
buscado é maior ou menor que o valor do elemento do meio da lista, se for menor, o
algoritmo irá comparar apenas o elementos do meiopara o início, e se for maior, irá
comparar os elementos do meio para o final (SZWARCFITER e MARKENZON, 2017;
MILLER e RANUM, 2013; GUIMARÃES, 1984).
Isso sempre aplicando este mesmo processo, pegando o elemento do meio dessa
nova sublista, do meio para o fim ou do meio para o início, e feitos os processos de
comparação novamente. Pensando dessa forma, pode parecer mais trabalhoso,
porém, ao aplicarmos este método em listas maiores, o ganho pode ser significativo,
uma vez que não precisa iterar e testar todos os elementos presentes na estrutura de
dados.
A Imagem 2 demonstra graficamente como seria a lógica de passos para realizar a
busca binária em uma lista já ordenada, por exemplo, em que tenha sido aplicado o
método bubble sort. 
113
Imagem 3 – Implementação do método de busca binária.
Fonte: Adaptado de Miller e Ranum, 2013.
A Imagem 3 traz a implementação do nosso método de busca binário – ou binary
search. Podemos perceber que o primeiro passo é descobrir qual é o elemento do
meio da lista fazendo uma divisão inteira utilizando o operador // do Python. Com
esse índice, podemos comparar se o valor do meio da lista é o valor busca, caso
contrário, é validado se o valor de busca é maior ou menor que o valor do elemento
do meio, e então é feita uma nova atribuição de índices de busca, selecionando-se o
fim da lista com valores maiores, ou o início da lista com valores menores.
def binarySearch(list, element):
   first = 0
   last = len(list)-1
   found = False
   while first<=last and not found:
       midpoint = (first + last)//2
       if list[midpoint] == element:
           found = True
       else:
           if element < list[midpoint]:
               last = midpoint-1
           else:
               first = midpoint+1
   return found
114
Ao aplicar o método de busca binária, temos um ótimo exemplo da estratégia de
resolução de problemas, conhecida por “dividir para conquistar”, que busca a melhor
forma de resolver um problema dividindo-o em problemas menores e com menos
complexidade, o que permite resolver partes menores de uma forma mais otimizada
até que consigamos resolver o problema maior por completo (MILLER e RANUM,
2013).
Na busca binária, repare que vamos “cortando” a área de busca, o que facilita e
otimiza encontrar o valor desejado. Pensar nessa forma de resolver o problema de
busca, segmentando em problemas menores e resolvendo problemas menores até
conseguir resolver o principal, nos remete às técnicas de recursividade, em que um
mesmo problema é segmentado diversas vezes até chegar aos problemas mais
simples e possíveis de se resolver.
Pensando assim, é possível implementar uma busca binária aplicando as técnicas de
recursividade já vistas anteriormente, otimizando e deixando ainda mais elegante
nossa solução de busca binária. A Imagem 4 traz a implementação da busca binária
com recursividade: reparem que ao invés de haver uma estrutura de repetição para
iterar entre os elementos, conforme os teste de posição e elemento do meio são
feitos, e conforme o resultado, uma nova chamada é feita a função de busca recursiva
alterando os parâmetros de busca. A Imagem 5 traz um exemplo de execução de
ambas as implementações.
115
Imagem 4 – Implementação do método de busca binária com recursividade.
Fonte: Adaptado de Miller e Ranum, 2013.
Imagem 5 – Exemplos busca binária.
def recursiveBinarySearch(list, element):
if len(list) == 0:
return False
else:
midpoint = len(list)//2
if list[midpoint]==element:
return True
else:
if element<list[midpoint]:
return
recursiveBinarySearch(list[:midpoint],element)
else:
return
recursiveBinarySearch(list[midpoint+1:],element)
>>> lista = [1, 3, 14, 27, 28, 45, 52, 89, 157, 294]
>>> print(binarySearch(lista,2))
False
>>> print(binarySearch(lista,14))
True
>>> print(recursiveBinarySearch(lista,30))
False
>>> print(recursiveBinarySearch(lista,45))
True
Fonte: autor.
116
16
Árvore
Imagem 2 – Exemplo árvore para ordenação.
Fonte: Próprio autor.
Depois de conhecer diferentes estruturas de dados, desde listas até matrizes, junto
com técnicas tais como a recursividade e métodos de ordenação e busca de dados,
vamos abordar uma das estruturas de dados mais comuns e com diversas aplicações:
a árvore.
Árvores são aplicadas em diversas linhas de estudo nas áreas da Ciência da
Computação e várias disciplinas relacionadas à Tecnologia da Informação como um
todo, tais como sistemas operacionais, computação gráfica, redes de computadores e
bancos de dados. Estruturas de dados em árvores não levam esse nome sem motivo,
uma vez que sua construção é diretamente inspirada nas árvores reais, pois a árvore
enquanto estrutura conta com uma raiz, ramificações e folhas, mas aqui vamos
pensar nela em ordem invertida, como se a pegássemos e a rotacionasse em 180º, ou
seja, para nós, a raiz da árvore terá a raiz no topo e as folhas na base (SZWARCFITER e
MARKENZON, 2017; MILLER e RANUM, 2013; GUIMARÃES, 1984).
A Imagem 2 traz um exemplo de construção de uma árvore de dados, neste caso,
uma árvore de valores inteiros e focada em promover a busca de elementos, uma vez
que existem algoritmos de busca totalmente desenvolvidos para árvores. Neste caso,
porém, vamos focar em um caso simples: a partir de uma raiz, cada nó será um valor
diferente, e como regra todo valor menor que este nó estará à sua esquerda e todo
valor maior estará à sua direita. Os nós de um nó podem ser chamado de “filhos”,
porém, os nós mais baixo e que não têm filhos são as folhas. 
118
Ao analisar a nossa árvore, podemos notar alguns fatos interessantes sobre a iteração
e a navegação entre os nós. Digamos que precisemos indicar o menor valor dessa
estrutura de dados. Independentemente de quantos nós, níveis ou folhas existam,
sempre será a folha mais à esquerda da estrutura – neste caso o valor “1”. Se for o
maior valor, é a mesma lógica, mas do lado direto. Quando navegamos pela árvore,
podemos perceber que cada nó é validado se o valor buscado é o valor do nó ou se é
menor ou maior (SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013).
Uma propriedade importante sobre as árvores é que as folhas são únicas, ou seja,
cada caminho possível da raiz até uma das folhas é único, garantindo a qualidade de
construção da estrutura e a representatividade dos valores (SZWARCFITER e
MARKENZON, 2017; MILLER e RANUM, 2013; GUIMARÃES, 1984).
Outro exemplo no qual podemos pensar sobre a construção de árvores são
diretórios de pastas e arquivos, onde temos pastas e subpastas em diferentes
diretórios que respeitam uma estrutura de árvore e em que os arquivos ou pastas
vazias são as folhas e o nó a raiz, pode ser, por exemplo, o diretório “C:/” ou “/home”.
Este exemplo de uma estrutura de árvore para pastas revela mais um conceito
importante das estruturas de árvores, conhecido como subárvore, que define a
possibilidade de mover níveis inteiros de uma árvore para outro nó ou nível sem
afetar os níveis inferiores. Fazendo uma analogia, a estrutura de pastas e subpastas
seria o equivalente ao fazer um ctrl+x e ctrl+v de uma pasta com todo o seu conteúdo
para outro diretório.
Com estes exemplos, compreendemos o quão dinâmica é uma estrutura de dados em
árvore, pois permite diversas aplicações e resolver problemas computacionais de
diversas naturezas. Entretanto, além de entender aplicações e exemplos de árvores,
precisamos conhecer algumas definições para árvores. A seguir são listados e
descritos os principais componentes de uma árvore (MILLER e RANUM, 2013).
Nó: elemento fundamental para a expansão e construção de qualquer árvore.
Aresta: a responsabilidade da aresta é conectar dois nós, demonstrando assim
uma relação direta entre ambos, também sendo uma das estruturas
fundamentais.
Raiz: elemento inicial de qualquer estrutura de árvore e essencial para a
construção e expansão de uma árvore, sendo o único nó de uma árvore que não
tem arestas de entrada.
Caminho: é o conjunto de arestas e nós em formato de lista ordenada que
representa o percurso até umafolha. Por exemplo: 28 -> 14 -> 3 -> 1. Este seria o
caminho para a folha com valor “1” baseado na Imagem 2.
119
Filho: um nó ou conjunto de nós que têm arestas de entrada que partem de um
mesmo nó em um nível hierárquico mais alto, este conjunto são considerados
filhos do nó de onde as arestas partem.
Pai: um nó pai é o nó que conecta diversos outros nós, seus filhos, e todos os
nós relacionados à aresta de saída de um nó são considerados seus filhos.
Irmãos: são nós em uma estrutura de árvore que são filhos de um mesmo nó
pai, ou seja, irmãos.
Subárvore: cada conjunto de nós e arestas composto que tem um nó pai em
comum e todos os nós descendentes.
Folha: é considerado um nó folha todo aquele que não tenha filhos, ou seja, os
nós inferiores de uma árvore.
Nível: o nível de um nó inserido em uma árvore é por definição o número de
arestas do nó pai até o nó em questão. Dessa forma, o nó raiz é de nível 0.
Altura: a altura de uma árvore é equivalente ao nível mais alto que existe de
qualquer nó em determinada árvore. 
Conhecendo os termos básicos de um vocabulário sobre estrutura de árvores,
podemos ver em definições mais formais o que seria uma árvore. São duas principais,
uma que define as árvores envolvendo nós e arestas, e a segunda definição é uma
definição que utiliza de recursividade.
A primeira definição formal de árvores diz que uma árvore é constituída por um
conjunto de nós e um conjunto de arestas que conectam pares de nós, tendo as
seguintes propriedades (SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013):
Um nó da árvore é destinado a ser o nó raiz.
Todo nó, exceto a raiz, é conectado por uma aresta exatamente entre dois nós,
assim, esses nós ligados se tornam parentes (pais e filhos).
Um caminho único possível vai do nó raiz até cada um dos nós.
Se cada um dos nós presentes em uma árvore tem no máximo dois filhos, esta
estrutura é definida como uma árvore binária. 
A Imagem 3 traz um exemplo de árvore segundo a definição 1. Observe que um único
nó pode ter mais de dois filhos conforme a necessidade do cenário.
120
Imagem 3 – Exemplo árvore conforme a definição um.
Fonte: Adaptado de Miller e Ranum, 2013.
A segunda definição, também amplamente aceita, é que uma árvore pode ser tanto
vazia quanto com elemento, mas basicamente composta por um nó raiz e conta com
nenhuma ou mais subárvores, em que cada uma dessas subárvores é outra árvore.
Assim, cada nó raiz de cada subárvore está de alguma forma conectado à raiz da
árvore pai por meio de uma aresta. Essa definição recursiva não se limita em definir
uma estrutura ou limite para a estrutura. A Imagem 4 traz um exemplo gráfico de
como seria a construção inicial de uma árvore conforme a definição recursiva
(SZWARCFITER e MARKENZON, 2017; MILLER e RANUM, 2013).
121
Imagem 4 – Exemplo árvore conforme a definição dois (recursiva).
Fonte: Adaptado de Miller e Ranum, 2013.
122
Material Complementar
Livro
Problem Solving with Algorithms and Data Structures Using
Python
Autor: Bradley N. Miller e David L. Ranum
Editora: Franklin Beedle & Associates
Sinopse: É um livro sobre ciência da computação, mas também
focado em Python e como se pode aplicar esta poderosa
linguagem de programação para solução de diversos problemas
computacionais, abordando diversos pontos relevantes para as
estruturas de dados.
Web
Você pode melhorar seus conhecimentos sobre Python e
estruturas de dados consultando plataformas de cursos online
como a Udemy e a Code Cademy.
Udemy Code Cademy
123
https://www.udemy.com/
https://www.codecademy.com/
GUIMARÃES, L. Algoritmos e Estrutura de Dados. 1. Ed. LTC, 2964.
MENEZES, N. N. C. Introdução à Programação com Python: Algoritmos e Lógica de
Programação Para Iniciantes. 3. Ed. Novatec Editora, 2019.
MILLER, B. N., RANUM D. L. Problem Solving with Algorithms and Data Structures
using Python. 2. Ed. Franklin Beedle & Associates, 2013.
PERKOVIC, L. Introdução à Computação Usando Python – Um Foco no
Desenvolvimento de Aplicações. 1. Ed. LTC, 2016.
PYSCIENCE-BRASIL. Python: o que é? Por que usar? [2019]. Disponível em:
http://pyscience-brasil.wikidot.com/python:python-oq-e-pq. Acesso em: 10 ago. 2020.
SILVA, D. M. Python: história e ascendência. Revista Programar, Lisboa, ed. 59, p. 96–
99, 2018.
SZWARCFITER, J. L.; MARKENZON, L. Estrutura de Dados e Seus Algoritmos. 3. Ed. LTC,
2017.
Referências
124
	Introdução ao Python e Estruturas Básicas
	Tipos de Dados: Primitivos e Abstratos
	Coleções de Dados em Python
	Listas Lineares
	Listas Lineares Desordenadas
	Listas Lineares Ordenadas
	Pilhas
	Filas
	Deque
	Matrizes
	Recursividade
	Métodos de Ordenação I
	Métodos de Ordenação II
	Métodos de Busca: Sequencial
	Métodos de Busca: Binária
	Árvore