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

Double-ended queues ADT (deques)

0 votos
35 visitas
perguntada Dez 1, 2020 em Dados e Bases de Dados por Luiz Filippe (21 pontos)  

Descreva como implementar a "double-ended queue ADT" usando dois stacks como variáveis de instância. Qual é a complexidade para rodar este código?

REFERÊNCIA DA QUESTÃO: GOODRICH, Michael T.; TAMASSIA, Roberto; GOLDWASSER, Michael H. "Data Structures & Algorithms in Python". Nova Jersey: John Wiley & Sons, 2013.
(Capítulo 6, questão C-6.26)

Compartilhe

1 Resposta

0 votos
respondida Dez 1, 2020 por Luiz Filippe (21 pontos)  

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

A imagem será apresentada aqui.

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.

...