"Double-ended queue" também é conhecida como deque. Ela se trata de uma coleção ordenada de itens similar às filas, porém com uma diferença. Além de possuir dois fins (frente e traseira), a natureza do deque é irrestrita no que tange a adicionar ou remover itens; i.e., novos itens podem ser adicionados tanto pela frente quanto pela traseira. Desta forma, a "double-ended queue" reúne características de pilhas e filas em uma única estrutura de dados. A figura abaixo mostra um deque de objetos.
Abstract data type (ADT) especifica um conjunto de métodos e sua semântica (o que cada método faz), mas não especifica a implementação das operações. Quando falamos em pilhas (stacks), observamos que tal estrutura de dados é ela mesma uma ADT. Existem distintos tipos de ADT, sendo cada tipo definido pelos métodos relacionados, que chamamos de interface. O stack ADT possui as seguintes operações:
--> init: inicializa a classe pilha (stack)
--> is_empty: checa se a pilha está vazia.
--> push: adiciona um novo item à pilha
--> pop: remove o último item adicionado da pilha e o retorna
Importante notar que ainda que as pilhas sejam uma estrutura LIFO (last in, first out) e as filas sejam FIFO (first in, first out), os deques não exigem tais ordenações.
Implementação em Python:
class Deque:
def __init__(self,stack1):
self.lista1 = stack1
self.lista2 = []
def is_empty(self):
self.stack1==[]
# Queremos adicionar "x" pela traseira
def add_traseira(self, x):
# O uso de 2 stacks faz com que um seja tratado como frente e outro como traseira.
# Enquanto o stack 1 não for vazio, retiro seus elementos (da direita para a esquerda)
# e os adiciono ao stack 2. Agora o stack 1 está vazio. Neste momento, adiciono o "x"
# que desejo, de modo que o stack 1 terá apenas o item "x" enquanto o stack 2 terá
# todos os outros outrora do stack 1.
while len(self.lista1) != 0:
self.lista2.append(self.lista1[-1])
self.lista1.pop()
self.lista1.append(x)
# Retornamos os itens que havíamos passado para a stack 2 de volta para a stack 1.
# Isto faz com que a inserção de "x" se dê pela traseira.
while len(self.lista2) != 0:
self.lista1.append(self.lista2[-1])
self.lista2.pop()
# Sendo stack 1 a frente, caso queiramos remover um item por aí, devemos checar se a
# stack está vazia
def remove_frente(self):
if len(self.lista1) == 0:
print("A lista está vazia.")
# Retorna o elemento que está mais à direita na stack 1
x = self.lista1[-1]
self.lista1.pop()
return x
# Enquanto o stack 1 não for vazio, retiro seus elementos (da direita para a esquerda)
# e os adiciono ao stack 2. Agora o stack 1 está vazio. Neste momento, adiciono o "x"
# que desejo, de modo que o stack 1 terá apenas o item "x" enquanto o stack 2 terá
# todos os outros outrora dostack 1.
# Aqui adicionaremos os elementos pela frente
def add_frente(self, x):
while len(self.lista1) != 0:
self.lista2.append(self.lista1[0])
self.lista1.pop(0)
self.lista1.append(x)
# Retornamos os itens que havíamos passado para a stack 2 de volta para a stack 1.
# Faremos isso de modo a colocá-los pela traseira. Assim, "x" é inserido pela frente.
while len(self.lista2) != 0:
self.lista1.insert(0,self.lista2[-1])
self.lista2.pop()
# Removamos o "x" pela traseira
def remove_traseira(self):
if len(self.lista1) == 0:
print("A lista está vazia.")
x = self.lista1[0]
self.lista1.pop(0)
return x
def tamanho(self):
return len(lista1) + len(lista2)
Façamos agora alguns exemplos. Primeiramente, vejamos a inserção de novos itens. Suponhamos que temos a seguinte lista que reúne os anos em que um gigante clube carioca foi campeão brasileiro de futebol: [1989, 1997]. Este clube em questão conquistou dois outros titulos: 1974 e 2000. Como adicionaríamos à lista?
x = [1989,1997]
d = Deque(x)
d.add_frente(2000)
d.add_traseira(1974)
print(d.lista1)
Façamos agora um exemplo de remoção de itens. No final da década de 1990, três clubes brasileiros ganharam em sequência a Copa Libertadores das Américas: [1997,1998,1999]. Destes três, um foi carioca (1998). Caso quiséssemos retornar apenas este valor, teríamos que eliminar as duas pontas da lista:
y = [1997,1998,1999]
e = Deque(y)
e.remove_traseira()
e.remove_frente()
print(e.lista1)
Quanto à complexidade do código, o acréscimo de novos itens à lista tem complexidade 2O(n), em que "n" é o total de elementos que estão na stack1. Isso se dá por conta do transporte dos "n" elementos da lista1 para a lista2 e depois o transporte de volta dalista2 para a lista1. No tocante à retirada de itens, a complexidade é O(1) porque, neste caso, apenas 1 item é usado por vez.