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á