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

Tirando e colocando um elemento de uma fila

0 votos
27 visitas
perguntada Dez 18, 2020 em Ciência da Computação por José Henriques Jr (1 ponto)  
Compartilhe

2 Respostas

0 votos
respondida Dez 18, 2020 por José Henriques Jr (1 ponto)  

Para está tarefa utilizaremos como referência o livro “Data Structures and Algorithms in Python –Michael T. Goodrich, Roberto Tamassia e Michael H. Goldwasser” para realizar o exercício C-6.29, p252.

Em ADT podemos tirar um elemento de uma fila, processá-lo e colocá-lo novamente na fila. utilizamos “dequeue” e “enqueue”, tirar e colocar em uma fila respectivamente. Para isso precisamos modificar a implementação ArrayQueue e incluir o método rotate().

Com base no livro primeirante vamos implementar uma classe para filas ArrayQueue.

class ArrayQueueRotate():
    DEFAULT_CAPACITY = 10

    def __init__(self):
        self._data = [None] * self.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def __len__(self):
        return self._size

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

A cima utilizamos a função init() que é um método reservado para classes em Python, podendo ser utilizado em um objeto criado a partir de uma classe, permitindo que está nova classe inicialize os atributos da classe “original”.

Já a função a len() retorna o comprimento do objeto podendo ser utilizada em qualquer objeto. E por fim comparamos uma lista com uma lista vazia para determinar se ela está vazia.

Após a implementação da classe precisamos modificá-la para implementarmos os métodos citados anteriormente.

def dequeue(self):
        if self.is_empty(): raise Empty('The queue is empty')
        answer = self._data[self._front]
        self._data[self._front] = None  #Help with GC
        self._front = (self._front + 1)%len(self._data)
        self._size -= 1
        return answer

    def enqueue(self, value):
        if self._size == len(self._data): self._resize(self._size * 2)
        self._data[(self._front + self._size)%len(self._data)] = value
        self._size += 1

    def _resize(self, capacity):
        new_array = [None]*capacity
        for i in range(self._size):
            new_array[i] = self._data[(self._front + i)%len(self._data)]
        self._data = new_array
        self._front = 0

    def rotate(self):
        if self.is_empty(): raise Empty('The array is empty')
        self._data[(self._front + self._size)%len(self._data)] = self._data[self._front]
        self._front = (self._front + 1)%len(self._data)

A função “first()” é usada para subconjunto de períodos iniciais de dados de série temporal com base em um deslocamento de data. No caso das funções “dequeue()” e “enqueue()” como mencionado anteriormente, elas tiram e colocam um elemento na fila e a função _resize altera o tamanho da classe.

Por fim usamos a função rotate() que basicamente pega o primeiro elemento da fila, tirar ele e botar ele por último.

def rotate(self):
        if self.is_empty(): raise Empty('The array is empty')
        self._data[(self._front + self._size)%len(self._data)] = self._data[self._front]
        self._front = (self._front + 1)%len(self._data)


AQR = ArrayQueueRotate()

for i in range(100):
    AQR.enqueue(i)


for i in range(300):
    print (AQR.first(), end = ', ')
    AQR.rotate()
0 votos
respondida Dez 18, 2020 por Felipe Yudi (46 pontos)  

Olá José Henriques

É só uma sugestão, mas eu colocaria o conteúdo da pergunta na pergunta e não no corpo da resposta.

Vi a sua solução. O código é muito interessante, mas acho que tem alguns problemas. Por exemplo, você mencionou na resposta que o método first()
"é usada para subconjunto de períodos iniciais de dados de série temporal com base em um deslocamento de data". Porém, esse método não está definido na classe.
Outro problema foi quando você levantou a excessão nos métodos dequeue e rotate.

if self.is_empty(): raise Empty('The queue is empty') 

Se eu não me engano, a excessão levantada deve pertencer à classe Exception (veja este link). Ela não pode ser simplemente Empty.

Deixo abaixo uma solução minha.

A implementação ArrayQueue é uma classe para filas que o autor do livro escreve no capítulo 6. Ela é:

class ArrayQueue(object):
    DEFAULT_CAPACITY = 10

    def __init__(self):
        #Cria um fila vazia
        self._data = [None]*ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def __len__(self):
        #Retorna o numero de elementos da fila
        return self._size

    def is_empty(self):
        #Retorn True se a fila esta vazia
        return self._size == 0

    def first(self):
        #Retorna sem remover o primeiro elemento
        if self.is_empty():
            raise Exception("Queue is empty")
        return self._data[self._front]

    def dequeue(self):
        #Remove o retorna o primeiro elemento
        if self.is_empty():
            raise Exception("Queue is empty")
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1)%len(self._data)
        self._size -= 1
        return answer

    def enqueue(self, e):
        #Adiciona um elemento ao fim da fila
        if self._size == len(self._data):
            self._resize(2*len(self._data))
        avail = (self._front + self._size)%len(self._data)
        self._data[avail] = e
        self._size += 1

    def _resize(self, cap): 
        #Aumenta o tamanho da fila para maior que len(self) 
        old = self._data
        self._data = [None]*cap
        walk = self._front
        for k in range(self._size): 
            self._data[k] = old[walk]
            walk = (1+walk)%len(old)
        self._front = 0

Vamos modificar essa classe para introduzir dois novos métodos. Primeiro vamos reescrever o método print para que possamos imprimir as listas e ver o que está acontecento. Depois vamos escrever o método rotate(). A classe modificada é:

class ArrayQueue(object):
    DEFAULT_CAPACITY = 10

    def __init__(self):
        #Cria um fila vazia
        self._data = [None]*ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def __len__(self):
        #Retorna o numero de elementos da fila
        return self._size

    def is_empty(self):
        #Retorn True se a fila esta vazia
        return self._size == 0

    def first(self):
        #Retorna sem remover o primeiro elemento
        if self.is_empty():
            raise Exception("Queue is empty")
        return self._data[self._front]

    def dequeue(self):
        #Remove o retorna o primeiro elemento
        if self.is_empty():
            raise Exception("Queue is empty")
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1)%len(self._data)
        self._size -= 1
        return answer

    def enqueue(self, e):
        #Adiciona um elemento ao fim da fila
        if self._size == len(self._data):
            self._resize(2*len(self._data))
        avail = (self._front + self._size)%len(self._data)
        self._data[avail] = e
        self._size += 1

    def _resize(self, cap): 
        #Aumenta o tamanho da fila para maior que len(self) 
        old = self._data
        self._data = [None]*cap
        walk = self._front
        for k in range(self._size): 
            self._data[k] = old[walk]
            walk = (1+walk)%len(old)
        self._front = 0

    def __str__(self):
        #Imprime a fila
        separator = ", "
        return "[" + separator.join([str(i) for i in self._data]) + "]"

    def rotate(self):
        #metodo que equivale a enqueue(dequeue))
        if self.is_empty():
            raise Exception("Queue is empty")

        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1)%len(self._data)

        avail = (self._front + self._size -1)%len(self._data)
        self._data[avail] = answer

O método str nos permite imprimir a fila de maneira similar a uma lista em Python. A vantagem é que ele mostra também os slots ainda não ocupados. Já o método rotate() é a resposta o exercício. Note que ele é quase uma combinação dos métodos enqueue() e dequeue(), mas é mais eficiente, pois não é necessário modificar _size.

Podemos testar o método rotate() com o seguinte código:

if __name__ == "__main__":

    fila1 = ArrayQueue()
    fila1.enqueue("a")
    fila1.enqueue("b")
    fila1.enqueue("c") 
    print("###fila1###")
    print(fila1)
    print("###enqueue(dequeue))###")
    fila1.enqueue(fila1.dequeue())
    print(fila1)

    fila2 = ArrayQueue()
    fila2.enqueue("a")
    fila2.enqueue("b")
    fila2.enqueue("c") 
    print("###fila2###")
    print(fila2)
    print("###rotate()###")
    fila2.rotate()

Criamos uma fila chamada fila1 e colocamos as strings "a", "b" e "c". Imprimimos a fila e depois usamos enqueue(dequeue()). Depois criamos outra fila chamada fila2 e colocamos os mesmos elementos. Aplicamos então o método rotate() e verificamos que o resultado final é o mesmo que usar enqueue(dequeue()). O output é:

###fila1###
[a, b, c, None, None, None, None, None, None, None]
###enqueue(dequeue))###
[None, b, c, a, None, None, None, None, None, None]
###fila2###
[a, b, c, None, None, None, None, None, None, None]
###rotate()###
[None, b, c, a, None, None, None, None, None, None]
...