Question

Como implementar uma fila em python?

Answer 1

Você pode usar uma lista ou ainda adaptar diretamente uma lista para ser usada como uma fila, mas essa implementação é bastante ineficiente:

class Queue:
    def __init__(self):
        self.__queue=[]

    def __len__(self):
        return len(self.__queue)

    def is_empty(self):
        return len(self.__queue)==0

    def add(self,element):
        self.__queue.append(element)

    def pop(self):
        # Critical operation
        if(self.is_empty()):
            raise(Empty('Queue is empty')) 
        else:
            return self.__queue.pop(0)

    def first(self):
        if(self.is_empty()):
            raise(Empty('Queue is empty'))
        else:
            return self.__queue[0]        


if __name__ == '__main__':
    myQueue=Queue()

    if(myQueue.is_empty()):
        print( "Stack is empty")

    myQueue.add(1)
    myQueue.add(2)
    myQueue.add(3)    

    print (myQueue.pop())

    print ("What is the first element now?")
    print (myQueue.first())

    print ("What is the length now?")
    print (len(myQueue))

O melhor é usar uma lista de tamanho fixo utilizando a idéia de "array circular" e aumentar a lista apenas se tiver necessidade:

class Queue:
    DEFAULT_CAPACITY=2
    def __init__(self):
        self.__queue=[None]*Queue.DEFAULT_CAPACITY
        self.__size=0
        self.__front=0

    def __len__(self):
        return self.__size

    def is_empty(self):
        return len(self.__queue)==0

    def add(self,element):
        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()):
            raise(Empty('Queue is empty'))
        else:
            return self.__queue[self.__front]        

    def pop(self):
        # Critical operation
        if(self.is_empty()):
            raise(Empty('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            
            print ("Position of the first element", self.__front) # Delete in case of serious job
            return firstElement


    def __resize(self,newCapacity):
        print ("The queue has been resized") # Delete in case of serious work
        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


if __name__ == '__main__':
    myQueue=Queue()

    if(myQueue.is_empty()):
        print("Stack is empty")

    myQueue.add(1)
    myQueue.add(2)
    myQueue.add(3)    


    print("myQueue.pop()", myQueue.pop())

    print("What is the first element now?")
    print("myQueue.first()",myQueue.first())

    print("What is the length now?")
    print(len(myQueue))

    myQueue.add(5)
    myQueue.add(6)
    myQueue.add(7)    

    print("What is the length now?")
    print(len(myQueue))