Cannot import Queue in Python

  • 3

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

  • 3

    use following

    queue = collections.deque()


  • 1
    This post is deleted!

  • 1

    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

    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 = []
            mark = 0
            while len(travel) > mark: # Use mark to tell where is the head of the "queue"
                temp = []
                while len(travel) > mark:
                    mark += 1
                traversalList.append([node.val for node in temp])
                for node in temp:
                    if node.left:
                    if node.right:
            return traversalList

  • 0

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