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