Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Implemente a estrutura de dados Pilha, utilizando como base a estrutura de dados Fila.

0 votos
23 visitas
perguntada Out 23 em Economia por Philippe Azevedo (16 pontos)  

Requisitos adicionais:

-Apresente para cada método criado o respectivo custo.
- Considere que será utilizada para manipular tipos de dados abstratos (qualquer tipo de dado. Por exemplo: inteiro, strings, objetos em geral)
-Para os métodos que trabalham com manipulação de dados, apresente graficamente seu resultado.

Compartilhe

1 Resposta

0 votos
respondida Out 23 por Philippe Azevedo (16 pontos)  
editado Out 23 por Philippe Azevedo

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.

A imagem será apresentada aqui.
A imagem será apresentada aqui.

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)

A imagem será apresentada aqui.

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)

A imagem será apresentada aqui.

    print('tamanho ' + str(len(pilha)))

tamanho 4

    saida = pilha.pop()

A imagem será apresentada aqui.

    saida = pilha.peek()
    print("Peek " + str(saida))
    pilha.push(25)

A imagem será apresentada aqui.

    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") 
...