Inicialmente devemos apresentar o que são cada estrutura de dados.
Drozdek apresenta um conceito simples de pilha, no qual é apresentada como uma estrutura linear de dados e somente pode ser acessada por uma de suas extremidades para armazenar e recuperar dados. Assim, o primeiro a ser armazenado (entrar na pilha) é o primeiro a ser recuperado (sair) - comumente apresentado como o princípio last-In first-out (LIFO)
Habitualmente, trabalhamos com pilhas, seja jogando cartas ou em um restaurante para pegarmos um prato.
Já a Fila é uma estrutura de dados, na qual ambas as extremidades são utilizadas: em seu final, os elementos são adicionados, enquanto os elementos são removidos pela sua frente. Dessa forma o primeiro a ser adicionado, será o primeiro a ser recuperado. Princípio first-In first-out (FIFO)
Basicamente uma pilha, terá que dois métodos principais:
push(e): adiciona elemento 'e' no topo da pilha.
pop( ): remove e retorna o elemento que se encontra no topo da pilha. caso a pilha encontra-se vazia deverá ser lançado um erro.
Outros métodos
len(): retorna o número de elementos da pilha.
isEmpty(): retorna true se pilha vazia, false caso contrário.
peek(): retorna o conteúdo do topo da pilha, sem removê-lo.
Ao se utilizar uma Fila como base, irei utilizar como fundamento preservar a ordem de seus elementos.
Dessa forma ao inserir um elemento no topo da pilha, o elemento irá para o fim da fila.
Tal decisão incorrerá no custo de ter quer trazer esse elemento para o início da fila, para fins de extração ou verificação de seu conteúdo, e isso será verificado na implementação dos métodos pop() e peek().
Como estamos utilizando python como linguagem, será garantido que a estrutura de dados será abstrata (ADT), visto que é possui a tipagem dinâmica, não sendo necessário declarar o tipo de cada variável no código.
Foi criada a classe StackADT, com os métodos abaixo, destaca-se que todos os métodos terão complexidade o(1), exceto os métodos pop() e peek(), pela necessidade de percorrer a fila inteira para remover ou acessar o último elemento (presente no topo da fila).
O parâmetro maxsize indicará se a pilha terá finita ou não (maxsize = 0).
Destaca-se que a classe Queue implementa, dentre outras, uma Fila em Python. Os principais métodos são get (recupera e remove o elemento do inicío da fila) e put (inclui o elemento e no fim da fila)
class StackADT:
def __init__(self,maxsize=0):
self.__fila = Queue(maxsize)
self.__imagens = []
# remover todos os elementos da pilha
def clear(self):
while (len(self) > 0):
aux = self.__fila.get() #O(n)
# verifica se a pilha está vazia
def isEmpty(self):
return self.__fila.empty() #O(1)
# adiciona elemento no topo da pilha
def push(self,elem):
if not (self.__fila.full()):
self.__fila.put(elem) #O(1)
else:
raise Exception("Stack ADT cheia!! " + str(elem))
#print("Stack ADT cheia!! " + str(elem))
# remove elemento do topo da pilha, como estou utilizando um objeto queue como base para a pilha,
# tenho que percorrê-la para chegar ao seu final, obtendo o último elemento
def pop(self):
if len(self) > 0:
for i in range(len(self)-1):
self.__fila.put(self.__fila.get())
aux = self.__fila.get()
return aux #O(n)
else:
raise Exception("Impossível remover, Stack ADT vazia!!")
# retorna o elemento do topo da pilha sem removê-lo
def peek(self):
if len(self) > 0:
for i in range(len(self)-1):
aux = self.__fila.get()
self.__fila.put(aux)
aux = self.__fila.get()
# reorganizo a queue
self.__fila.put(aux)
return aux #O(n)
else:
raise Exception("Impossível acessar conteúdo, Stack ADT vazia!!")
#print("Stack ADT vazia!!")
def __len__(self):
return self.__fila.qsize() # O(1)
Por fim alterei toda a estrutura já apresentada para permitir verificar cada passo dos métodos push, pop e peek por meio de imagens.
-atributo __imagens -> armazena as imagens de cada interação.
- getElements -> retorna a pilha em uma lista, sem alterar os dados
- getImageStack -> cria a imagem da Pilha com base no resultado de getElements()
- getImageQueue-> cria a imagem da Fila com base no resultado de getElements()
- Imagem -> Une as imagens da Pilha e da Fila
- getImagens -> recebe a lista de imagens criada.
Para a Pilha, a célula azul indica o seu topo.
Para a Fila, a célula azul indica o início da fila, enquanto a verde indica o final.
# importar a biblioteca Python Image Library para trabalhar com imagens
from PIL import Image, ImageDraw,ImageColor, ImageFont
from queue import Queue
class StackADT:
def __init__(self,maxsize=0):
self.__fila = Queue(maxsize)
self.__imagens = []
# remover todos os elementos da pilha
def clear(self):
self.Imagem('',operacao='Clear')
while (len(self) > 0):
aux = self.__fila.get() #O(n)
self.Imagem('pop',operacao='Pop ' + str(aux) )
self.Imagem('pop',operacao='Fim' )
# verifica se a pilha está vazia
def isEmpty(self):
return self.__fila.empty() #O(1)
# adiciona elemento no topo da pilha
def push(self,elem):
self.Imagem('push',operacao='Push ' + str(elem) )
if not (self.__fila.full()):
self.__fila.put(elem) #O(1)
self.Imagem('push',operacao='Fim')
else:
raise Exception("Stack ADT cheia!! " + str(elem))
#print("Stack ADT cheia!! " + str(elem))
# remove elemento do topo da pilha, como estou utilizando um objeto queue como base para a pilha,
# tenho que percorrê-la para chegar ao seu final, obtendo o último elemento
def pop(self):
if len(self) > 0:
self.Imagem('pop',operacao='Pop ')
for i in range(len(self)-1):
self.__fila.put(self.__fila.get())
self.Imagem('pop',operacao='Pop exec ')
aux = self.__fila.get()
self.Imagem('pop',operacao='Pop ' + str(aux))
return aux #O(n)
else:
raise Exception("Impossível remover, Stack ADT vazia!!")
#print("Stack ADT vazia!!")
# retorna o elemento do topo da pilha sem removê-lo
def peek(self):
if len(self) > 0:
self.Imagem('pop',operacao='Peek ')
for i in range(len(self)-1):
aux = self.__fila.get()
self.__fila.put(aux)
self.Imagem('push',operacao='Push '+ str(aux))
aux = self.__fila.get()
self.Imagem('pop',operacao='Pop '+ str(aux))
# reorganizo a queue
self.__fila.put(aux)
self.Imagem('push',operacao='Push '+ str(aux))
return aux #O(n)
else:
raise Exception("Impossível acessar conteúdo, Stack ADT vazia!!")
#print("Stack ADT vazia!!")
def __len__(self):
return self.__fila.qsize() # O(1)
#visa apenas pegar o atual da pilha para permite criar graficamente seu estado
def getElements(self):
elements =[] #lista, não fila :)
if len(self) > 0:
# ao percorrer a fila, volta ao seu estado original
for i in range(len(self)):
aux = self.__fila.get()
self.__fila.put(aux)
#colocando cada elemento da fila no inicio da lista, para representar a pilha
elements.insert(0,aux)
return elements
# antes e depois de realizar as operacoes na pilha, devo tirar um 'print' de seu estado
# e se for o caso, definir a próxima operacao (put ou pop)
def getImageStack(self,operacao=''):
imagens = []
#diretorio = 'c:\python\\'
tam=50
width = 3*tam #largura
height = tam #altura
lista = self.getElements()
font = ImageFont.truetype('times.ttf', size=45)
index = 1
for elem in lista:
imagem = Image.new('RGB', (width,height), color = 'white')
d = ImageDraw.Draw(imagem)
msg = str(elem)
w, h = d.textsize(msg, font=font)
h += int(h*0.21)
d.text(((width-w)/2, (height-h)/2),msg , fill='black', font = font)
if lista[0] == elem:
d.rectangle([(0,0),(width-1,height-1)], outline='blue',width = 3) # o topo da pilha terá a cor azul
else:
d.rectangle([(0,0),(width-1,height-1)], outline='black')
imagens.append(imagem)
index =index +1
#juntando cada caixinha dos elementos
espaco = 50
espaco2 = 180
desloc = 70
if len(lista) > 0:
dst = Image.new('RGB', (width + espaco + espaco2, height*len(imagens)+desloc),color = 'white')
i = 0
draw = ImageDraw.Draw(dst)
for imagem in imagens:
dst.paste(imagem, (espaco, i*height+ desloc ))
i = i + 1
else:
dst = Image.new('RGB', (width + espaco + espaco2, height + desloc), color = 'white')
draw = ImageDraw.Draw(dst)
# caso queira gravar uma mensagem
if operacao != '':
draw.text((width + espaco + 5, 10),operacao , fill='black', font = font)
draw.text((10, 10), "Stack" , fill='black', font = font)
return dst
# cria imagem da pilha
# tipoOperacao -> indicará se a operacao será no começo (pop) ou no fim (push) da Queue
# operacao -> texto que descreverá a operacao, por exemplo Push ou Pop 10
def getImageQueue(self,tipoOperacao,operacao=''):
imagens = []
#diretorio = 'c:\python\\'
tam=50
width = 3*tam #largura
height = tam #altura
lista = self.getElements()
font = ImageFont.truetype('times.ttf', size=45)
index = 1
for elem in lista:
imagem = Image.new('RGB', (width,height), color = 'white')
d = ImageDraw.Draw(imagem)
msg = str(elem)
w, h = d.textsize(msg, font=font)
h += int(h*0.21)
d.text(((width-w)/2, (height-h)/2),msg , fill='black', font = font)
if lista[len(lista)-1] == elem:
d.rectangle([(0,0),(width-1,height-1)], outline='blue',width = 3) # o inicio da Queue terá a cor azul
elif lista[0] == elem:
d.rectangle([(0,0),(width-1,height-1)], outline='green',width = 3) # o fim da Queue terá a cor verde
else:
d.rectangle([(0,0),(width-1,height-1)], outline='black')
imagens.append(imagem)
index =index +1
#juntando cada caixinha dos elementos
espaco = 400
espaco2 = 180
desloc = 70
if len(lista) > 0:
dst = Image.new('RGB', (width*len(imagens)+ espaco + espaco2, height+desloc),color = 'white')
i = 0
draw = ImageDraw.Draw(dst)
for imagem in imagens:
dst.paste(imagem, (espaco +i*width, desloc ))
i = i + 1
else:
dst = Image.new('RGB', (width + espaco + espaco2, height + desloc),color = 'white')
draw = ImageDraw.Draw(dst)
# caso queira gravar uma mensagem
if operacao != '':
if tipoOperacao == 'push':
draw.text((espaco/2 + 5, 10),operacao , fill='black', font = font)
else:
draw.text((width*len(imagens) + espaco + 5, 10),operacao , fill='black', font = font)
draw.text((10, 10), "Queue" , fill='black', font = font)
return dst
# juntar imagens
def Imagem(self,tipoOperacao,operacao=''):
img1 = self.getImageStack(operacao)
img2 = self.getImageQueue(tipoOperacao,operacao)
width = max(img1.width,img2.width)
height = img1.height+img2.height
dst = Image.new('RGB', (width, height) ,color = 'white')
dst.paste(img1, (int((width - img1.width)/2), 0 ))
dst.paste(img2, (0, img1.height))
self.__imagens.append(dst)
def getImagens(self):
return self.__imagens
def clearImagens(self):
self.__imagens.clear()
Testando tudo:
if __name__ == "__main__":
try:
pilha = StackADT(5)
pilha.push(6)
pilha.push(8)
pilha.push(10)
pilha.push(15)
print('tamanho ' + str(len(pilha)))
tamanho 4
saida = pilha.pop()
saida = pilha.peek()
print("Peek " + str(saida))
pilha.push(25)
imagens = pilha.getImagens()
diretorio = 'c:\python\\'
i =1
for imagem in imagens:
imagem.save(diretorio + 'pilha' +str(i) + '.jpeg')
i = i + 1
except:
print("Ocorreu um erro")