Estruturas de Dados Básicas - Pilhas, Filas, Deques e Listas
Este artigo tem o intuito de apresentar de forma breve as Estruturas de Dados Básicas Pilha, Fila, Deque, Lista desordenada e Lista ordenada. A seguir, as estruturas serão apresentadas com uma breve explicação e por fim serão implementadas na linguagem Python.
Você pode estar se perguntando sobre a utilidade deste conteúdo. Pois bem, as linguagens de programação costumam vir com tipos de dados padrões como int, float, bool, contudo nem sempre esses tipos de dados são suficientes para colocarmos algum projeto em prática. Surge, então, a necessidade de criarmos nossos próprios tipos de dados.
Sumário
Pilha
Uma Pilha (Stack) é uma coleção de itens onde a inserção de novos itens e a remoção de itens existentes ocorre sempre na mesma extremidade. Pensando numa analogia cotidiana: numa pilha de pratos você coloca e retira um prato da pilha sempre pelo topo dela. Pensando numa aplicação prática: o seu histórico de navegação funciona de forma similar, à medida que vai acessando novas páginas elas vão sendo armazenadas numa pilha, quando você aperta um botão de voltar você retira o item mais no topo e volta para a página anterior.
Uma propriedade interessante da pilha é que se você remover os itens dela, eles estarão na ordem contrária da qual foram inseridos. Além disso, uma das principais características de uma pilha é que o primeiro item a entrar é o último a sair.
Agora pensamos nas características de uma pilha para criarmos o tipo abstrato Pilha e para definirmos suas funcionalidades. Numa pilha, devemos ser capazes de adicionar um novo item no seu topo, remover um item existente do seu topo, ver qual item está no seu topo, porém sem removê-lo, saber quantos itens estão presentes na pilha e saber se ela está vazia.
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
self.items.pop()
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)
def isEmpty(self) -> bool:
return self.items == []
Você pode utilizar a estrutura de dados da seguinte forma:
pilha_1 = Stack()
pilha_2 = Stack()
pilha_1.push(4)
pilha_1.push(2)
pilha_1.push(7)
print(pilha_1)
print(pilha_2)
pilha_1.pop()
pilha_2.push(5)
print(pilha_1)
print(pilha_2)
A saída do programa acima é a seguinte:
<<< [4, 2, 7]
<<< []
<<< [4, 2]
<<< [5]
Fila
Uma Fila (Queue) é uma coleção de itens onde a inserção de novos itens acontece numa extremidade e a remoção de itens existentes acontece na outra. Pensando numa analogia cotidiana: Você entra no fim da fila do pão e vai seguindo até o seu início, no balcão, para ser atendido. Pensando numa aplicação prática: a fila de impressão de uma impressora, os arquivos serão impressos na ordem em que você os mandou imprimir.
Agora pensamos nas características de uma fila para criarmos o tipo abstrato Fila e para definirmos suas funcionalidades. Numa fila devemos ser capazes de adicionar novos itens por uma extremidade e remover pela outra extremidade (considerando que uma fila possui 2 extremidades), saber quantos itens estão presentes na fila e por fim saber se ela está vazia.
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
self.items.pop(0)
def size(self):
return len(self.items)
def isEmpty(self):
return self.items == []
Você pode utilizar a estrutura de dados da seguinte forma:
fila = Queue()
fila.enqueue(5)
fila.enqueue(7)
fila.enqueue(9)
print(fila)
fila.dequeue()
print(fila)
A saída do programa acima é a seguinte:
<<< [5, 7, 9]
<<< [7, 9]
Na saída acima fica claro a principal característica de uma fila: o primeiro a entrar (5) é o primeiro a sair.
Deque
Um Deque é uma coleção de itens onde tanto a inserção quanto a remoção podem ser realizadas em ambas as extremidades. Estando livre das limitações impostas nas pilhas e filas.
Agora pensamos nas características de um deque para criarmos o tipo abstrato Deque e para definirmos suas funcionalidades. Devemos ser capazes de adicionar e remover em ambas as extremidades, saber quantos itens estão presentes no deque e se ele está vazio.
class Deque:
def __init__(self):
self.items = []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0, item)
def removeFront(self):
self.items.pop()
def removeRear(self):
self.items.pop(0)
def size(self):
return len(self.items)
def isEmpty(self):
return self.items == []
Você pode utilizar a estrutura de dados da seguinte forma:
deque = Deque()
deque.addFront(4)
deque.addFront(7)
deque.addRear(8)
deque.addRear(9)
print(deque)
A saída do programa acima é a seguinte:
<<< [9, 8, 4, 7]
Lista desordenada
Uma lista desordenada, como o próprio nome já diz, é uma coleção de itens em que cada item possui uma posição relativa em relação aos demais. O que a difere da lista ordenada, como veremos mais adiante, é que na ordenada nós vamos nos preocupar em deixar os itens adicionados em ordem crescente, por exemplo.
Você deve estar se perguntando o porquê de eu implementar a estrutura Lista em python uma vez que ela já existe. Existem linguagens que não possuem essa estrutura, por isso é importante estudá-la, e eu estou usando Python por ter um código mais limpo e ser fácil de entender.
Agora pensamos nas características de uma lista para criarmos o tipo abstrato Lista e para definirmos suas funcionalidades. Devemos ser capazes de adicionar um novo item em qualquer posição da lista, remover um item de qualquer posição da lista, saber se um determinado item está presente ou não na lista, saber a posição de um item na lista, saber quantos itens estão na lista e saber se ela está vazia ou não.
Para implementar a estrutura lista vamos usar o auxílio de uma estrutura nó, a qual vai armazenar o valor do item e vai referenciar o próximo item. Dessa forma, uma sequência de nós formará uma lista. Atente-se que sempre devemos saber qual é o primeiro item, pois é através dele que chegaremos nos demais, por uma espécie de varredura.
Nó
class Node:
def __init__(self,initdata):
self.data = initdata
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
Lista
class UnorderedList:
def __init__(self):
self.head = None
def __len__(self):
return self.size()
def __repr__(self):
current_node = self.head
items = list()
counter = 0
while current_node:
counter += 1
items.append(current_node.getData())
current_node = current_node.getNext()
return f"{self.__class__.__name__}(size: {counter}, items: {items})"
def get_items(self):
items = []
current_node = self.head
while current_node:
items.append(current_node.getData())
current_node = current_node.getNext()
return items
def add(self, item): # adiciona no começo da lista
new = Node(item)
new.setNext(self.head)
self.head = new
def append(self, item): # adiciona no final da lista
current_node = self.head
if self.head is None:
self.head = Node(item)
while current_node:
if current_node.getNext() is None:
current_node.setNext(Node(item))
break
else:
current_node = current_node.getNext()
def insert(self, pos, item): # adiciona na posição pos
if pos == 0:
self.add(item)
elif pos >= self.size():
self.append(item)
else:
previous_node = self.head
current_node = self.head.getNext()
counter = 1
while current_node:
if counter == pos:
new = Node(item)
previous_node.setNext(new)
new.setNext(current_node)
break
else:
previous_node = current_node
current_node = current_node.getNext()
counter += 1
def remove(self, item): # remove um item assumindo que ele está na lista
if self.head.getData() == item:
self.head = self.head.getNext()
else:
previous_node = self.head
current_node = self.head.getNext()
while current_node:
if current_node.getData() == item:
previous_node.setNext(current_node.getNext())
break
else:
previous_node = current_node
current_node = current_node.getNext()
def pop(self, pos=-1):
# remove e retorna o item da posição pos, se pos não for informado ele remove
# o último item da lista.
if pos == 0 or len(self.get_items()) == 1:
c = self.head.getData()
self.head = self.head.getNext()
return c
else:
previous_node = self.head
current_node = self.head.getNext()
counter = 1
while current_node:
if counter == pos or current_node.getNext() is None:
previous_node.setNext(current_node.getNext())
return current_node.getData()
else:
previous_node = current_node
current_node = current_node.getNext()
counter += 1
def search(self, item):
current_node = self.head
found = False
while current_node:
if current_node.getData() == item:
found = True
break
else:
current_node = current_node.getNext()
return found
def index(self, item): # supõe que o item está na lista
current_node = self.head
counter = 0
while current_node:
if current_node.getData() == item:
break
else:
current_node = current_node.getNext()
counter += 1
return counter
def size(self):
current_node = self.head
counter = 0
while current_node:
current_node = current_node.getNext()
counter += 1
return counter
def isEmpty(self):
return self.head is None
Lista ordenada
Como dito anteriormente, a única diferença entre a lista ordenada e desordenada é que na ordenada nós nos preocupamos com a ordem, crescente neste exemplo, ao adicionar os itens na lista. Sendo assim, nós podemos aproveitar o que já foi escrito anteriormente, contudo agora só adicionaremos itens com a função add.
class OrderedList:
def __init__(self):
self.head = None
def add(self, item): # adiciona em ordem crescente
if self.head is None or item < self.head.getData():
new = Node(item)
new.setNext(self.head)
self.head = new
else:
current_node = self.head
next_node = self.head.getNext()
added = False
while next_node:
if item < next_node.getData():
new = Node(item)
current_node.setNext(new)
new.setNext(next_node)
added = True
break
else:
current_node = next_node
next_node = next_node.getNext()
if not added:
current_node.setNext(Node(item))
def remove(self, item): # remove um item assumindo que ele está na lista
if self.head.getData() == item:
self.head = self.head.getNext()
else:
previous_node = self.head
current_node = self.head.getNext()
while current_node:
if current_node.getData() == item:
previous_node.setNext(current_node.getNext())
break
else:
previous_node = current_node
current_node = current_node.getNext()
def pop(self, pos=-1):
# remove e retorna o item da posição pos, se pos não for informado ele remove
# o último item da lista.
if pos == 0:
self.head = self.head.getNext()
else:
previous_node = self.head
current_node = self.head.getNext()
counter = 1
while current_node:
if counter == pos or current_node.getNext() is None:
previous_node.setNext(current_node.getNext())
return current_node.getData()
else:
previous_node = current_node
current_node = current_node.getNext()
counter += 1
def search(self, item):
current_node = self.head
found = False
while current_node:
if current_node.getData() == item:
found = True
break
else:
current_node = current_node.getNext()
return found
def index(self, item): # supõe que o item está na lista
current_node = self.head
counter = 0
while current_node:
if current_node.getData() == item:
break
else:
current_node = current_node.getNext()
counter += 1
return counter
def size(self):
current_node = self.head
counter = 0
while current_node:
current_node = current_node.getNext()
counter += 1
return counter
def isEmpty(self):
return self.head is None
Você também poderia ter escrito a classe OrderedList usando a UnorderedList e os conceitos de herança, mas deixo isso como exercício para leitor. Outro exercício que deixo para o leitor é implementar a função __repr__ para as listas para facilitar a visualização dos seus elementos.
Conclusão
Neste artigo passamos brevemente pelas Estruturas de Dados básicas. Este conteúdo é essencial para quem quer seguir carreira na programação, pois abre um amplo leque de possibilidades na criação de projetos.
Nota: Peço que teste o código na sua máquina, eu não rodei na minha, fiz de cabeça. Pode parecer estranho mas no começo da faculdade um professor me disse que um bom programador deve saber o que o seu código faz sem precisar executá-lo, então usei esse post para praticar isso. Em caso de erros peço que me avise nos comentários para que eu faça as devidas alterações.
Referência
Para escrever este post eu me baseei no livro Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python e recomendo a leitura para complementar o que foi ensinado aqui.
Relacionados
Nesta seção deixarei links para alguns posts do tabnews que também falam sobre estruturas de dados.
Estrutura de Dados #0
Uma breve Introdução a teoria dos Grafos !
Estrutura de dados com exemplos em javascript
Apêndice
Neste artigo foram apresentados conceitos os quais podem não ser familiares para todos, por isso deixarei 2 livros referenciados aqui, um que ensina python básico, e o outro ensina estrutura de dados, classes, etc.
Pense em Python
Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python
Além disso deixo aqui 2 posts do tabnews.
Tutorial: Aprenda Python em 10 Minutos para Iniciantes
Clean Code - Conceitos | Exemplos 🎈
Sobre
5º período de Engenharia Mecatrônica - Universidade de Brasília (UnB)