Como implementar em Python uma classe Deque utilizando duas Pilhas

Question

Descreva como implementar um deque (Abstract Data Type de fila dupla) utilizando duas pilhas como variáveis de instância. Quais são os tempos de execução dos métodos?

Answer 1

Para criar um deque utilizando duas pilhas como variáveis de instância iremos proceder da seguinte forma.
Primeiro, iremos definir uma Pilha, que é uma coleção de objetos que são inseridos e removidos de acordo com o princípio Primeiro que Entra Primeiro que Sai (LIFO - First In First Out).
Para isso, definir as operações usuais dessa classe utilizando os métodos já implementados para listas convencionais. As operações usuais serão: push (adiciona um elemento no topo da pilha); pop (remove e retorna o elemento no topo da pilha); top (indica o elemento no topo da pilha); is_empty (retorna True se a pilha não tem nenhum elemento); e len (retorna o número de elementos da pilha). Em python, podemos definir pilha da seguinte forma:

class Empty(Exception):
    pass


class Pilha:

    def __init__(self):
        'Create an empty stack'
        self.data=[]

    def __len__(self):
        return len(self.data)

    def is_empty(self):
        return len(self.data)==0

    def push(self,x):
        self.data.append(x)

    def top(self):
        if self.is_empty():
            raise Empty('A pilha está vazia')
        else:
            return self.data[-1]

    def pop(self):
        if self.is_empty():
            raise Empty('A pilha está vazia')
        else:
            return self.data.pop()

Tendo definido uma pilha e suas operações usuais, podemos passar à definição do deque. Iremos definir 4 atributos para esse objeto: duas pilhas, frontStack e endStack e n1 e n2, que irão corresponder ao número de elementos em cada uma das pilhas. A pilha frontStack será utilizada para adicionar ou retirar elementos pelo lado esquerdo (ou pela frente) do deque, enquanto a pilha endStack será utilizada para retirar elementos pelo lado direito (ou por trás) do deque. Em seguida serão definidos os seguintes métodos:

• is_empy: soma n1 e n2 e retorna True caso essa soma seja igual a zero, ou seja, caso não haja elemento em nenhuma das duas pilhas.
• appendfront: utiliza o método de push na pilha frontStack e soma 1 em n1, indicando que essa pilha tem um elemento a mais.
• append: utiliza o método de push na pilha endStack e soma 1 em n2, indicando que essa pilha tem um elemento a mais.
• transferidor: esse método inicia com uma variável booleana chamada reverse assumindo valor igual a False e então montaremos uma condicional da seguinte forma: caso essa variável tenha valor False, enquanto n2>0 será aplicado o método pop na pilha endStack, que eliminará e retornará o elemento no topo daquela pilha, e será aplicado o método push na pilha frontStack sendo o argumento o valor do método pop aplicado anteriormente. Portanto, enquanto reverse==False e n2>0, esse método irá retirar todos os elementos da pilha endStack e adicioná-los à pilha frontStack. Caso reverse==True e n1>0 então o método irá aplicar o mesmo procedimento à pilha frontStack, ou seja, enquanto n1>0, serão retirardos elementos dessa pilha e adicionados à pilha endStack. Resumindo, quando esse método for acionado, ele irá transferir todos os elementos de uma pilha para a outra.
• popfront: esse método será utilizado para retirar os elementos pela esquerda/ por cima do deque. Para isso iremos utilizar a pilha frontStack. Iremos considerar dois casos: pilha frontStack vazia ou não. Caso ela não esteja vazia simplesmente será aplicado o método pop na pilha frontStack, retornando o primeiro elemento dessa lista e reduzindo n1 em uma unidade. Caso n1==0 então teremos que considerar os elementos da lista endStack, n2. Caso n2==0, então as duas pilhas estão vazias e, consequentemente, também o deque está vazio. Caso n2>0 então será aplicado o método transferidor em endStack, de forma que todos os elementos dessa pilha serão transferidos para a pilha frontStack de forma que o elemento do topo da pilha endStack será agora o elemento da base da pilha frontStack e o elemento da base da pilha endStack será o elemento do topo da pilha frontStack. Então, iremos aplicar o método pop na pilha frontStack, retornando o elemento do topo dessa lista e reduzindo n1 em uma unidade.
• pop: esse método será utilizado para retirar os elementos pela direita/ por baixo do deque. Para isso iremos utilizar a pilha endStack. O procedimento será análogo ao anteriormente descrito, porém utilizando a pilha endStack. Caso ela esteja vazia, o método transferidor será aplicado na pilha frontStack transferindo todos os elementos dessa pilha para a pilha endStack e então iremos retirar o elemento do topo dessa pilha.
• first: retorna o primeiro elemento do deque. Caso a pilha frontStack não esteja vazia, aplica o método top e retorna o primeiro elemento dessa pilha (sem retirá-lo da pilha). Caso essa pilha esteja vazia, então se a pilha endStack não estiver vazia será aplicado o método transferidor sobre essa pilha, transferindo todos os elementos para a pilha frontStack e então será aplicado o método top na pilha frontStack, retornando o primeiro elemento do deque.
• str: por último, iremos utilizar o método especial str(self) para retornar uma representação em string do objeto. Iremos definir nesse método uma lista, chamada front_data, e utilizar list comprehension na lista frontStack.data, que é uma representação em lista da pilha frontStack. Em seguida, iremos utilizar o método reverse na lista front_data, que irá inverter a ordem dos elementos nessa lista. Após isso, será criada a lista all_data a partir da utilização de list comprehension em uma lista formada pela concatenação da lista front_data (já invertida) com a lista endStack.data. Por fim, será retornada uma representação em string da lista all_data. Com isso, conseguiremos observar se o objeto que estamos definindo de fato se comporta como um deque.

Tendo descrito como implementar, partiremos agora para o código em Python que de fato implementa um deque utilizando duas pilhas como variáveis de instância.

class DequecomPilhas():

    def __init__(self):
        self.frontStack=Pilha()
        self.endStack=Pilha()
        self.n1=0
        self.n2=0

    def is_empty(self):
        return (self.n1 + self.n2) == 0


    def appendfront(self, elemento):            
        self.frontStack.push(elemento)
        self.n1 += 1


    def append(self, elemento):                
        self.endStack.push(elemento)
        self.n2 += 1


    def transferidor(self, reverse = False):
        if reverse == False:
            while self.n2 >0:
                self.frontStack.push(self.endStack.pop())
                self.n2 -= 1
                self.n1 += 1
        else:
            while self.n1 >0:
                self.endStack.push(self.frontStack.pop())
                self.n1 -= 1
                self.n2 += 1


    def popfront(self):
        if self.n1 == 0:
            print('Transfere da pilha endStack para a frontStack')
            if self.n2 == 0: 
                raise Empty('O Deque está vazio!')
            self.transferidor()  
        x = self.frontStack.pop()
        self.n1 -= 1
        return x


    def pop(self):
        if self.n2 == 0:
            if self.n1 == 0: 
                raise Empty('O Deque está vazio!')
            print('Transfere da pilha frontStack para a endStack')
            self.transferidor(reverse = True)  
        x = self.endStack.pop()
        self.n2 -= 1
        return x

    def first(self):
        if self.n1 == 0:
            if self.n2 == 0:
                raise Empty('O Deque está vazio!')
            print('Transfere da pilha endStack para a frontStack')
            self.transferidor()            
        return self.frontStack.top()


    def __str__(self):
        front_data=[x for x in self.frontStack.data]
        front_data.reverse()
        all_data=[x for x in (front_data + self.endStack.data)]
        return(str(all_data))


if __name__=='__main__':
    Q = DequecomPilhas()
    for i in range(5):
        Q.append(i)
    for i in range(5,7):
        Q.appendfront(i)
    print(Q,Q.n1,Q.n2) #frontStack: 2 elementos; endStack: 5 elementos
    print(Q.pop()) # retorna o último elemento do deque
    print(Q.popfront()) # retorna o primeiro elemento do deque
    print(Q.popfront()) # retorna o primeiro elemento do deque
    print(Q,Q.n1,Q.n2)  # Agora, frontStack não tem nenhum elemento
    print(Q.popfront()) # Transferiu todos os elementos da pilha endStack para a frontStack e retornou o primeiro elemento dessa pilha
    print(Q,Q.n1,Q.n2)  # Agora, frontStack não tem nenhum elemento
    print(Q.pop())  # A pilha endStack tinha ficado vazia. Todos os elementos de frontStack foram transferidos para endStack e retorou o primeiro dessa pilha, que é o último do deque
    print(Q,Q.n1,Q.n2)  # Agora, frontStack não tem nenhum elemento

As operações push e pushfront terão tempo de execução igual a O(1). As operações pop e popfront, por outro lado, podem ter tempo de execução igual a O(1) ou O(n). Caso seja necessário aplicar o método transferidor, será necessário mover cada elemento da pilha antes de retirá-lo da pilha para a qual os elementos foram transferidos. Nesse caso, o tempo de execução será igual a O(n). Caso não seja necessário aplicar o método transferidor, pop e popfront terão tempo de execução igual a O(1).