RACIOCÍNIO

ALGORÍTMICO

Juliano Vieira Martins

Estrutura de dados
homogêneos do tipo
vetor em Python
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:

 Descrever a lógica de manipulação de uma estrutura do tipo vetor.

 Reconhecer casos em que é necessário utilizar vetor.
 Programar algoritmos empregando vetores.

Introdução
O papel principal de um programa de computador é armazenar e pro-
cessar dados. Qualquer software de computador possui um modelo de
dados que define quais dados serão coletados e manipulados. Esses
modelos também são chamados de “estrutura de dados” e definem como
o fluxo de dados é controlado em relação às entradas, aos processos e
às saídas. Assim, os dados que são manipulados em um programa de
computador são organizados por meio de uma dessas estruturas de
dados. Existem diferentes formas de organizar os dados e uma delas é
fazendo uso dos vetores.
Neste capítulo, você vai conhecer a lógica de manipulação de uma
estrutura de dados do tipo vetor. Além disso, vai ver como reconhecer os
casos em que é necessário utilizar vetores e como programar algoritmos
empregando esse tipo de estrutura de dados.

1 Introdução ao conceito de vetores

O vetor é um método de armazenamento de dados em uma estrutura or-
ganizada. Quando um vetor é criado em um programa, uma variável (ou
identificador) é assinada para esse vetor; isso é chamado de “declaração”.
2 Estrutura de dados homogêneos do tipo vetor em Python

Na declaração de criação do vetor, o programa precisa saber algumas infor-

mações relevantes que farão parte de todo o ciclo de vida do vetor dentro
dele. Assim, no momento da declaração, é necessário informar o tamanho
exato que o vetor vai ter e o tipo dos elementos. Após a criação do vetor,
com suas respectivas posições, é possível somente alterar o valor do elemento
no vetor, pois conceitualmente não há as operações de inserção e remoção
em um vetor de tamanho fi xo.
Os vetores são classificados como estruturas de dados homogêneas,
pois armazenam elementos do mesmo tipo (BROOKSHEAR, 2013). Essa
estrutura pode armazenar números, sequências de caracteres, valores bo-
oleanos (verdadeiro e falso), caracteres, objetos e assim por diante. Porém,
depois de definido o tipo de valores que o vetor armazenará, todos os seus
elementos deverão ser do mesmo tipo. Não é possível “misturar” diferentes
tipos de dados em um mesmo vetor, ou seja, vetores não armazenam tipos
de dados mistos.
Cada elemento em um vetor se refere a um local específico na memória.
Para entender como isso funciona, é muito útil visualizar a memória de um
computador como uma “grade” (grid) de pequenos blocos. Cada informação
é armazenada em um desses pequenos blocos que formam a grade. Dessa
forma, os vetores aproveitam essa estrutura de “grade” para armazenar as
informações relacionadas em locais de memória adjacentes ou sequenciais e,
assim, garantir extrema eficiência no momento da localização desses valores.
Quando é necessário acessar mais de um deles, o processo é extremamente
otimizado, pois o computador já sabe onde o valor está localizado.
O vetor armazena um conjunto de elementos de dados em determinada
ordem, e essa ordem é mantida durante todo o ciclo de vida do vetor, a menos
que o próprio programador a altere. Isso se deve ao fato de que os vetores
possuem o que é chamado de “índice” para acessar cada valor nessa estrutura.
Os índices são valores numéricos, inteiros, que se referem ao local em que
cada valor está armazenado no vetor. O primeiro elemento do vetor está po-
sicionado no índice zero (0), o segundo elemento, no índice um (1), o terceiro,
no índice dois (2) e assim consecutivamente. Essa forma de indexar o vetor
começando em zero é chamada de “indexação baseada em zero”, do inglês
zero-based numbering. Dessa forma, fica fácil perceber que os elementos do
vetor avançam em uma direção ou dimensão. Essa dimensão é geralmente
chamada de “comprimento” do vetor. A seguir, veja os tipos de indexação
que um vetor pode ter.
 Estrutura de dados homogêneos do tipo vetor em Python 3

 0 (indexação baseada em zero): o primeiro elemento do vetor é indexado

pelo inteiro zero (0);
 1 (indexação baseada em um): o primeiro elemento do vetor é indexado
pelo inteiro um (1);
 n (indexação baseada em n): o índice base do vetor pode ser escolhido
livremente.

Geralmente, linguagens de programação que permitem indexação baseada

em n também permitem valores de índice negativos e outros tipos de dados
escalares, como enumerações ou caracteres, que podem ser usados como um
índice vetorial.
No momento da declaração do vetor, em que é informado o comprimento e o
tipo de dados, são reservados na memória os espaços (blocos) que os elementos
do vetor ocuparão. Mesmo que esses espaços não sejam preenchidos com os
elementos, eles são mantidos e reservados vazios na memória, aguardando
atribuições futuras. Dessa forma, há uma desvantagem em termos de uso de
memória, pois é feita a reserva de memória para operações futuras que podem
não ocorrer. É por isso que os vetores são recomendados em situações em que
se sabe de antemão quantos elementos será necessário armazenar.
Na Figura 1, a seguir, veja um vetor contendo as letras do alfabeto como
elementos. Os respectivos índices dos elementos são baseados em zero.
Os valores dos endereços na memória são meramente ilustrativos, pois ende-
reços de memória são valores hexadecimais ou binários.

Figura 1. Vetor contendo as letras do alfabeto como elementos.

Listas em Python
O tipo lista da linguagem de programação Python é o tipo que mais atende
ao conceito de vetor. Uma pequena diferença é que uma lista em Python é
implementada para armazenar sequências de vários tipos de dados (PYTHON
4 Estrutura de dados homogêneos do tipo vetor em Python

SOFTWARE FOUNDATION, 2020b). Assim, uma lista pode ser definida

como uma coleção de valores heterogêneos, ou seja, itens de diferentes tipos.
Python contém outros tipos de dados capazes de armazenar sequências, mas
o tipo mais comum é a lista. De acordo com a sintaxe Python, os itens da lista
são separados por vírgula (,) e delimitados por colchetes ([]). Assim, para criar
uma lista em Python, a sintaxe seria desta forma:

lista = ['e', 4, 'e', 3.6, True, [1, 2, 3]]

Uma lista pode conter objetos arbitrários, por exemplo, os elementos de uma
lista podem ser todos do mesmo tipo, ou podem conter qualquer variedade de
tipos diferentes. As listas podem conter objetos complexos, bem como funções,
classes ou módulos. Além disso, uma lista pode conter qualquer quantidade
de objetos, de zero a quantos a memória do computador permitir. Às vezes,
uma lista com um único objeto é chamada de lista singleton. Além disso, os
objetos em uma lista não precisam ser exclusivos, ou seja, um objeto pode
aparecer várias vezes em uma mesma lista Python.
Elementos individuais em uma lista podem ser acessados por meio de um
índice entre colchetes. Isso é exatamente análogo a acessar caracteres indi-
viduais em uma sequência de texto (string). A indexação de lista é baseada
em zero, assim como nas sequências de caracteres. Além do índice normal,
listas em Python possuem um índice negativo que é contado do final da lista,
começando em menos um (–1) e indo em direção ao começo (Figura 2).

Figura 2. Ilustração de uma lista em Python

contendo as vogais maiúsculas como ele-
mentos. Os respectivos índices normais
(positivos) dos elementos são baseados em
zero, e os índices negativos começam no final
da lista em –1.
 Estrutura de dados homogêneos do tipo vetor em Python 5

Acessar os elementos de uma lista em Python é possível do mesmo modo

que nos vetores. Assim, os elementos da lista podem ser acessados por meio
do identificador da lista (nome) seguido do operador de fatiamento, que são
os colchetes. Além disso, diferentemente de outras linguagens, a linguagem
de programação Python também oferece a flexibilidade de usar a indexação
negativa para acessar os elementos da lista.

lista = [ 'A', 'E', 'I', 'O', 'U' ]

print( lista[0] ) # Saída: A

print( lista[1] ) # Saída: E
print( lista[2] ) # Saída: I
print( lista[-2] ) # Saída: O
print( lista[-1] ) # Saída: U

print( lista[-5:-2] ) # Saída: A, E, I

print( lista[2:5] ) # Saída: I, O, U

print( lista[:2] ) # Saída: A, E, I

print( lista[2:] ) # Saída: I, O, U

A omissão do primeiro índice inicia o fatiamento no início da lista, e a

omissão do segundo índice estende o fatiamento até o final dela. Essa com-
binação de indexação positiva e negativa, em conjunto com o fatiamento, é
uma poderosa ferramenta que torna as listas em Python uma estrutura de
dados versátil, tanto no armazenamento dos tipos de dados quanto no acesso
a esses dados.
O Python também fornece métodos para adicionar novos valores à lista,
bem como métodos para remover valores dela. Os métodos de inserção de
elementos na lista são os métodos “append()” e “insert()”, e os métodos de
remoção de elementos da lista são os métodos “pop()” e “remove()”, além da
instrução del.
6 Estrutura de dados homogêneos do tipo vetor em Python

lista = ['A', 'E', 'I', 'O', 'U']

print(lista) # Saída: [A, E, I, O, U]

[Link]('B') # Adicionar na lista

print(lista) # Saída: [A, E, I, O, U, B]

[Link]() # Remover elemento do último índice

print(lista) # Saída: [A, E, I, O, U]

[Link](2) # Remover elemento do índice 2

print(lista) # Saída: [A, E, O, U]

[Link](2, 'I') # Adicionar elemento I no índice 2

print(lista) # Saída: [A, E, I, O, U]

del lista[1] # Remover elemento do índice 1

print(lista) # Saída: [A, I, O, U]

[Link]('A') # Remover elemento A

print(lista) # Saída: [I, O, U]

2 Aplicação de vetor como pilha e fila

Os vetores também podem ser usados para implementar outras estruturas
de dados que usam vetores como base. Para isso, é necessário implementar
alguns métodos a fim de manipular os elementos de acordo com a estrutura.
A pilha é uma estrutura de dados que armazena itens de maneira que o último
a entrar na pilha é o primeiro a sair. Esse comportamento tem a sigla, em
inglês, Lifo, ou seja, Last In, First Out. Esse comportamento contrasta com a
estrutura de dados fila, que armazena itens de maneira que o primeiro a entrar
é o primeiro a sair. Esse comportamento é chamado Fifo, do inglês First In,
First Out. É mais fácil entender uma pilha quando se pensa em um caso de
uso com o qual se esteja familiarizado, por exemplo, o recurso “desfazer” de
um editor de código.
 Estrutura de dados homogêneos do tipo vetor em Python 7

Em um editor de código, por exemplo, o conceito de pilha é implementado

nas ações que são feitas durante a edição. Assim, cada nova ação é colocada
como um novo elemento no topo de uma pilha. A ação de inserir elemento
no topo da pilha é chamada de push. Da mesma forma, há também a ação
de remover um elemento do topo da pilha; no editor de código, isso ocorre
quando é acionado o botão “Desfazer”. Essa ação de remover do topo da pilha
é chamada de pop. Para compreender melhor, observe a Figura 3, a seguir.

Figura 3. Duas pilhas representando os estados de um editor de código.

As ações de editar/refazer e desfazer do editor fazem com que os itens sejam
inseridos ou removidos da pilha, atendendo ao conceito das ações push e pop.

Vetores também podem ser usados para implementar o comportamento de

fila. Como foi mencionado anteriormente, esse comportamento é chamado de
Fifo, ou seja, o primeiro a entrar é o primeiro a sair. Na ciência da computação,
uma fila é uma coleção de elementos mantidos em uma sequência. Ela pode
ser modificada pela adição de elementos em uma extremidade da sequência ou
pela remoção de elementos na outra extremidade da sequência. Por convenção,
o final da sequência na qual os elementos são adicionados é chamado de “parte
traseira da fila”, e o início no qual os elementos são removidos é chamado de
“cabeça ou frente da fila”.
8 Estrutura de dados homogêneos do tipo vetor em Python

Esse tipo de comportamento é comumente utilizado em controle de estoque

quando os produtos são perecíveis e é necessário estar atento à sua data de
validade. Assim, o primeiro produto a entrar no estoque de um supermer-
cado deve ser o primeiro produto a sair do estoque. Isso é uma estratégia de
gerenciamento de estoque na qual os produtos armazenados por mais tempo
são enviados primeiro aos consumidores. Além de atentar à data de validade,
esse tipo de controle garante que o custo das mercadorias vendidas e o custo
do estoque restante correspondam.
O comportamento Fifo também é análogo ao comportamento de pessoas
em pé em uma fila; as pessoas deixam a fila na mesma ordem em que entraram
nela. Com o avanço da tecnologia, as filas foram substituídas pelas senhas, que
também atendem ao conceito de Fifo, ou seja, a primeira senha distribuída é
a primeira senha a ser chamada (Figura 4). A ação de adicionar um elemento
à parte traseira da fila é chamada de enqueue, e a ação de remoção de um
elemento da frente é chamada de dequeue.

Figura 4. Comportamento Fifo de uma fila contendo números de senhas como elementos.
A primeira senha distribuída (001) é a primeira a ser chamada. A última senha (101) a entrar
na fila será a última a ser chamada.

Em estruturas do tipo pilha ou fila, não se reordenam os itens que essas estruturas
carregam. Uma vez criadas as estruturas, os elementos devem permanecer ou ser
manipulados na mesma ordem em que foram inseridos. Afinal, por que algum pro-
gramador usaria estruturas do tipo pilha e fila para depois reordenar os elementos?
 Estrutura de dados homogêneos do tipo vetor em Python 9

3 Implementação de pilha e fila em Python

Python provê uma estrutura de lista ([Link], 2019) que é
utilizada com frequência pelos programadores. Essa estrutura pode ser usada
para implementar o comportamento de pilha, fazendo uso de dois métodos.
Os métodos que têm o mesmo comportamento de push e pop são respectiva-
mente os métodos de lista Python append e pop. Assim, em vez de push, é
possível usar append para adicionar novos elementos ao topo da pilha, enquanto
pop remove os elementos na ordem Lifo.

pilha = ['A', 'E', 'I', 'O']

print(pilha) # Saída: ['A', 'E', 'I', 'O']

[Link]('U') # Adicionar no topo da lista

print(pilha) # Saída: ['A', 'E', 'I', 'O', 'U']

[Link]() # Remover 'U' do topo da lista

[Link]() # Remover 'O' do topo da lista

[Link]() # Remover 'I' do topo da lista

[Link]() # Remover 'E' do topo da lista

[Link]() # Remover 'A' do topo da lista

[Link]() # Remover ??? do topo da lista

10 Estrutura de dados homogêneos do tipo vetor em Python

No exemplo anterior, existe uma última chamada para o método pop que
deveria remover mais um elemento do topo da pilha. No entanto, como a lista
está vazia, essa chamada vai gerar um IndexError, pois não existe elemento
algum a ser removido.

Traceback (most recent call last):

File "/[Link]", line 19, in <module>
[Link]()
IndexError: pop from empty list

Infelizmente, a lista em Python tem algumas falhas em comparação com

outras estruturas de dados. O maior problema é que uma lista pode enfrentar
queda de velocidade à medida que cresce. Os itens em uma lista são armaze-
nados com o objetivo de fornecer acesso rápido a elementos aleatórios na lista.
Em um nível alto, isso significa que os itens são armazenados próximos uns
dos outros na memória. No entanto, se a pilha crescer mais do que o bloco de
memória que a contém atualmente, o Python precisará fazer algumas alocações
de memória. Isso pode levar algumas chamadas do método append a demorar
muito mais do que outras.
Além disso, há outro problema, só que dessa vez um pouco menos sério.
Se for utilizado o método insert (método que adiciona um elemento em uma
posição indicada pelo programador) para adicionar um elemento na pilha em
uma posição diferente da posição final, o processo pode demorar muito mais.
Normalmente, adicionar um elemento em outra posição que não seja a última
é algo que um programador não faria em uma pilha.
Além da lista, que pode ser usada para implementar o comportamento
de pilha, Python fornece uma estrutura mais especializada para esse fim.
Essa estrutura ajuda a contornar o problema de realocação que ocorre na
lista. O módulo collections contém a classe “deque” ([Link].
ORG, 2019), que é útil para criar pilhas e filas Python. Assim, é possível
utilizar os mesmos métodos de lista que foram utilizados para implementar
a pilha, append e pop.
 Estrutura de dados homogêneos do tipo vetor em Python 11

from collections import deque

pilha = deque(['A', 'E', 'I', 'O'])

print(pilha) # Saída: ['A', 'E', 'I', 'O']

[Link]('U') # Adicionar no topo da lista

print(pilha) # Saída: ['A', 'E', 'I', 'O', 'U']

[Link]() # Remover 'U' do topo da lista

[Link]() # Remover 'O' do topo da lista

[Link]() # Remover 'I' do topo da lista

[Link]() # Remover 'E' do topo da lista

[Link]() # Remover 'A' do topo da lista

[Link]()

No exemplo anterior, também existe uma última chamada para o método

pop que deveria remover mais um elemento do topo da pilha. Da mesma forma,
como no uso de lista Python, a estrutura “deque” vai gerar um IndexError,
pois não existe elemento a ser removido do topo da pilha.
12 Estrutura de dados homogêneos do tipo vetor em Python

Traceback (most recent call last):

File "/[Link]", line 21, in <module>
[Link]()
IndexError: pop from an empty deque

O exemplo dado é muito parecido com o exemplo da lista Python usada

para implementar a pilha.
Python também permite implementar o comportamento de fila; assim,
é possível usar uma lista regular como uma fila, mas isso não é o ideal da
perspectiva de desempenho. Da mesma forma que as pilhas, as listas são
bastante lentas para esse fim, pois inserir ou excluir um elemento no início
requer a troca de todos os outros elementos de posição, um por um. Portanto,
não é recomendado usar uma lista como uma fila improvisada no Python, a
menos que se esteja lidando apenas com um pequeno número de elementos.
Para implementar esse tipo de fila usando lista, podem ser utilizados
também os métodos append para inserir no fim da fila e o método pop para
remover do início da fila. A diferença é que o método pop, sem passar ar-
gumento, sempre remove um elemento do final. Assim, é necessário passar
como argumento o valor zero (0), informando que ele é o índice que deseja
remover o elemento da fila.

fila = []

Como nos exemplos

print(fila) anteriores,
# Saída: [] tentar remover um item de uma fila que
já está vazia causa IndexError.
[Link]('1') # Adicionar no fim da fila
[Link]('2') # Adicionar no fim da fila
[Link]('3') # Adicionar no fim da fila
[Link]('4') # Adicionar no fim da fila
 Estrutura de dados homogêneos do tipo vetor em Python 13

[Link]('5') # Adicionar no fim da fila

print(fila) # Saída: ['1', '2', '3', '4', '5']

[Link](0) # Remover '1' do início da fila

[Link](0) # Remover '2' do início da fila

[Link](0) # Remover '3' do início da fila

[Link](0) # Remover '4' do início da fila

[Link](0) # Remover '5' do início da fila

[Link]()

Traceback (most recent call last):

File "/[Link]", line 23, in <module>
[Link]()
IndexError: pop from empty list

Para resolver o problema de eficiência na implementação de uma estrutura

do tipo fila, também é possível usar a classe “deque”. Essa classe implementa
uma fila de extremidade dupla que suporta adicionar e remover elementos de
cada extremidade muito mais rápido do que com o uso de uma lista Python.
Os objetos “deque” do Python são implementados como listas duplamente
vinculadas, o que oferece um excelente desempenho para enfileirar e remover
da fila. No entanto, esse tipo de estrutura tem um desempenho ruim para
acessar aleatoriamente elementos no meio da fila. Como a estrutura “deque”
suporta a adição e a remoção de elementos de qualquer extremidade, e faz isso
14 Estrutura de dados homogêneos do tipo vetor em Python

com um bom desempenho, ela pode servir para implementar pilhas e filas.
Para adicionar um elemento no final da fila, usa-se o método append; porém,
para remover o elemento que está no início da fila, usa-se o método popleft.

from collections import deque

fila = deque()

print(fila) # Saída: []

[Link]('1') # Adicionar no fim da fila

[Link]('2') # Adicionar no fim da fila
[Link]('3') # Adicionar no fim da fila
[Link]('4') # Adicionar no fim da fila
[Link]('5') # Adicionar no fim da fila

print(fila) # Saída: ['1', '2', '3', '4', '5']

[Link]() # Remover '1' do início da fila

[Link]() # Remover '2' do início da fila

[Link]() # Remover '3' do início da fila

[Link]() # Remover '4' do início da fila

[Link]() # Remover '5' do início da fila

[Link]()
 Estrutura de dados homogêneos do tipo vetor em Python 15

Seguindo a mesma lógica da tentativa de remoção de um elemento de fila

vazia, uma exceção de IndexError acontecerá se popleft for invocado sob
uma lista vazia.

Traceback (most recent call last):

File "/[Link]", line 25, in <module>
[Link]()
IndexError: pop from an empty deque

BROOKSHEAR, J. G. Ciência da computação: uma visão abrangente. 11. ed. Porto Alegre:
Bookman, 2013.
PYTHON SOFTWARE FOUNDATION. Data types. Delaware: Python Software Founda-
tion, 2020. Disponível em: [Link] Acesso
em: 17 jan. 2020.

Os links para sites da Web fornecidos neste capítulo foram todos testados, e seu fun-
cionamento foi comprovado no momento da publicação do material. No entanto, a
rede é extremamente dinâmica; suas páginas estão constantemente mudando de
local e conteúdo. Assim, os editores declaram não ter qualquer responsabilidade
sobre qualidade, precisão ou integralidade das informações referidas em tais links.