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

Implementando uma fila (queue) com limite de capacidade opcional

+1 voto
20 visitas
perguntada Set 9 em Programação Computacional por Lucas Lourenço (51 pontos)  

Implementando uma fila (queue) com limite de capacidade opcional

Questão C-6.28 do livro "Data Structures and Algorithms in Python" de Michael T. Goodrich, Roberto Tamassia e Michael H. Goldwasser.

Modify the ArrayQueue implementation so that the queue’s capacity is limited to maxlen elements, where maxlen is an optional parameter to the constructor (that defaults to None). If enqueue is called when the queue is at full capacity, throw a Full exception (defined similarly to Empty).

Modifique a implementação de ArrayQueue de forma que a capacidade da fila esteja limitada a maxlen elementos, em que maxlen é um parâmetro opcional ao usuário (o default é None). Se enqueue for chamado quando a fila estiver em sua capacidade cheia, gere uma exceção de 'Cheia' (definida similarmente à exceçao 'Vazia').

Compartilhe

1 Resposta

0 votos
respondida Set 9 por Lucas Lourenço (51 pontos)  
editado Set 9 por Lucas Lourenço

Para responder à questão, vou me basear no código fornecido nos slides da aula 7, com algumas modificações. Primeiro, defini o método mágico call, para que se possa visualizar a fila sem ter que utilizar print. Por exemplo, após gerar um objeto da classe fila (a = Queue()), podemos visualizar o objeto com o comando a(). A segunda diferença foi que mantive a notação do livro do Goodrich e nomeei o método de adicionar elementos à fila de enqueue e o de retirar elementos de dequeue.

Partindo para a resposta, temos que permitir que o usuário defina a capacidade máxima da fila ao criar o objeto, mas esse parâmetro não precisa ser obrigatório. Assim, se não for escolhido um valor para maxlen, a classe se comporta como no código original. Isso pode ser implementado da seguinte maneira:

    def __init__(self, maxlen=None):.
        self.__maxlen=maxlen if maxlen is not None else None
        self.__queue=[None]*self.__maxlen if maxlen is not None else [None]*2

A seguir, é necessário criar uma exceção toda vez que se deseja acrescentar um elemento a uma fila que já esteja cheia. Antes, quando isso acontecia, dobrava-se a capacidade máxima da lista a partir da ideia de circularidade. Agora, devemos retornar uma mensagem avisando que a capacidade está em seu limite:

def enqueue(self,element):
    if self.__maxlen is not None and (self.__size==len(self.__queue)):
        print("Queue is at its full capicity") 

Por último, defino também um método que permite ao usuário aumentar a capacidade da fila sem ter que criar um novo objeto. Na verdade, esse método já estava incluso na classe, mas originalmente fora definido com dois underscores, o que significa que o método é privado e só pode ser utilizada dentro da classe. O que fiz foi simplesmente definir um novo método acessível ao usuário e que chame o método privado. Note que caso se forneça uma capacidade menor que o tamanho atual da fila, uma mensagem de erro é gerada:

def maxlen(self,newmaxlen): # Método para mudar a capacidade máxima de uma fila já criada
    self.__maxlen=newmaxlen
    self.__resize(newmaxlen) 

def __resize(self,newCapacity):
if newCapacity == None:
    self.__maxlen = newCapacity
elif newCapacity != None and newCapacity < self.__size:
    print ("New capacity below current capacity")
else:
    old=self.__queue
    self.__queue=[None]*newCapacity
    theElementPosition=self.__front
    for i in range(self.__size):
        self.__queue[i]=old[theElementPosition]
        theElementPosition=(1+theElementPosition)%len(old)
    self.__front=0

Código completo para a classe Queue com restrição de capacidade:

class Queue:
def __init__(self, maxlen=None): # Inicialização da classe. Se o usuário não escolher um comprimento máximo, a classe funciona exatamente como a função original.
    self.__maxlen=maxlen if maxlen is not None else None
    self.__queue=[None]*self.__maxlen if maxlen is not None else [None]*2 # Ou a fila assume o tamanho máximo ou tamanho 2, como antes.
    self.__size=0 
    self.__front=0 

def __call__(self): # Uma das formas de se "chamar" o elemento criado
    return self.__queue

def __len__(self):
    return self.__size

def maxlen(self,newmaxlen): # Método para mudar a capacidade máxima de uma fila já criada
    self.__maxlen=newmaxlen
    self.__resize(newmaxlen)

def is_empty(self):
    return self.__size==0

def enqueue(self,element):
    if self.__maxlen is not None and (self.__size==len(self.__queue)): # A primeira exceção é a de capacidade cheia. Caso não esteja no limite, o código funciona como antes.
        print("Queue is at its full capicity")
    else: 
        if (self.__size==len(self.__queue)):
            self.__resize(2*len(self.__queue))  
        position=(self.__front + self.__size)%len(self.__queue) 
        self.__queue[position]=element
        self.__size=self.__size+1 

def first(self):
    if(self.is_empty()):
        print('Queue is empty')
    else:
        return self.__queue[self.__front]

def dequeue(self): # Maxlen não interfere no dequeue, que segue igual
    if(self.is_empty()):
        print('Queue is empty')
    else:
        firstElement=self.__queue[self.__front]
        self.__queue[self.__front]=None 
        self.__front=(self.__front+1)%len(self.__queue)
        self.__size=self.__size-1
        if 0 < self.__size < len(self.__queue)//4: 
            self.__resize(len(self.__queue)//2)
        print ("Position of the first element", self.__front) 
        return firstElement

def __resize(self,newCapacity):
    if newCapacity == None:
        self.__maxlen = newCapacity
    elif newCapacity != None and newCapacity < self.__size:
        print ("New capacity below current capacity")
    else:
        old=self.__queue
        self.__queue=[None]*newCapacity
        theElementPosition=self.__front
        for i in range(self.__size):
            self.__queue[i]=old[theElementPosition]
            theElementPosition=(1+theElementPosition)%len(old)
        self.__front=0

Testando alguns comandos:

if __name__=="__main__":   
    a=Queue(5)
    a()
    a.enqueue(3)
    a.enqueue(4)
    a.enqueue(5)
    a.enqueue(6)
    a.enqueue(7)
    # Agora, a fila está cheia. Note:
    a.enqueue(8)

    # Se o usuário quiser alterar a capacidade da fila sem ter que recriar o objeto, basta usar o método maxlen:
    a.maxlen(10)
    a.maxlen(None)
comentou Set 11 por daniel cunha (11 pontos)  

Oi Lucas,

Gostei bastante da sua resposta princiapalmente pela boa sacada da criacao do call que forcece uma intuicao visual da fila ao usuario e pela boa ideia da parametrizacao do maxlen.

Com vistas a contribuir, deixo aqui uma proposta de resolucao alternativa de modo complementar a sua. Aqui temos que declarar a capacidade maxima ja na largada.

 class Empty(Exception): pass
 class Full(Exception): pass

 class Queue():
DEFAULT_CAPACITY = 10
def __init__(self, maxlen=100): # ao abrir a funcao o usuario vai poder definir o max
    self._data = [None]*self.DEFAULT_CAPACITY
    self._size = 0
    self._front = 0
    self._maxlen = maxlen

def __len__(self):
    return self.__size

def __call__(self): # Uma das formas de se "chamar" o elemento criado
    return self._data

def is_empty(self):
    return self.__size==0

def enqueue(self,element):
    if self._size == self._maxlen: raise Full(f"Queue is at its full capicity of {self._maxlen}")
    if self._size == len(self._data): self._resize(min(self._size * 2, self._maxlen)) 
    self._data[(self._front + self._size)%len(self._data)] = element
    self._size += 1

def first(self):
    if self.is_empty(): raise Empty('The queue is empty')
    return self._data[self._front]

def dequeue(self): # Maxlen não interfere no dequeue, que segue igual
    if self.is_empty(): raise Empty('The queue is empty')
    firstElement = self._data[self._front]
    self._data[self._front] = None  
    self._front = (self._front + 1)%len(self._data)
    self._size -= 1
    return firstElement

def __resize(self,newCapacity):

    theElementPosition = [None]*newCapacity
    for i in range(self._size):
        theElementPosition[i] = self._data[(self._front + i)%len(self._data)]
    self._data = theElementPosition
    self._front = 0

Usando o mesmo teste, temos que:

 if __name__=="__main__":   
   max_fila = Queue(3)
   max_fila.enqueue(0)
   max_fila.enqueue(1)
   max_fila.enqueue(2)
   max_fila.enqueue(3)
   max_fila()
...