Cannot import Queue in Python


  • 3
    A

    Looks like I cannot "import Queue", and Queue is not automatically imported


  • 2
    S

    use following

    queue = collections.deque()

    queue.appendleft()
    queue.pop()


  • 1
    S
    This post is deleted!

  • 1
    S

    If I remember correctly, list in python can be treated like a stack but not a queue.
    To be more explicit, list in python has amortized constant time append() and pop().
    Doing pop(0) to get the left most element is a linear time operation and should be strongly discouraged.


  • 0
    V

    As list.pop(0) in python means a linear time, I used a mark to simulate queue
    Just remember where you have been and ignore the elements before mark

    And my solution accepted is

    def levelOrder(self, root):
            if not root:
                return []
            traversalList = []
            travel = []
            travel.append(root)
            mark = 0
            while len(travel) > mark: # Use mark to tell where is the head of the "queue"
                temp = []
                while len(travel) > mark:
                    temp.append(travel[mark])
                    mark += 1
                traversalList.append([node.val for node in temp])
                for node in temp:
                    if node.left:
                        travel.append(node.left)
                    if node.right:
                        travel.append(node.right)
            return traversalList

  • 0
    P

    As sashimee suggested, use collections.deque(). And you will get FIFO effect from appendleft() and pop()

        # import collections   # looks to be automatically imported already 
        q = collections.deque()
        q.appendleft(1)
        q.appendleft(2)
        q.appendleft(3)
    
        q.pop()  # 1
        q.pop()  # 2
        q.pop()  # 3
    

    As for the workaround of using list() and pop(0) to realize a queue, it's strongly discouraged. (you can refer to a good article 'Efficiency of using a Python list as a queue' on stackoverflow)

    Though list objects support similar operations, they are optimized for fast fixed-length operations and
    incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

    Conclusion: use collections.deque() instead of list() for a FIFO queue


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.