{"id":4529,"date":"2022-06-13T21:18:00","date_gmt":"2022-06-14T02:18:00","guid":{"rendered":"https:\/\/wanderin.dev\/?p=4529"},"modified":"2024-10-06T10:10:07","modified_gmt":"2024-10-06T15:10:07","slug":"a-queue-implementation-in-python","status":"publish","type":"post","link":"https:\/\/javierfeliu.me\/python-interview\/a-queue-implementation-in-python\/","title":{"rendered":"A Queue Implementation in Python"},"content":{"rendered":"\n

About this article<\/h2>\n\n\n\n

In this article, I’ll explore the queue<\/strong>, a linear data structure we can quickly implement in Python. <\/p>\n\n\n\n

This post is the second in a miniseries exploring the implementation of linear data structures. I based the series on my notes while studying for a Python technical interview.<\/p>\n\n\n\n

For quick access, here is the list of posts on this series:<\/p>\n\n\n\n

  1. A Stack Implementation in Python<\/a> <\/li>
  2. A Queue Implementation in Python (this article)<\/li>
  3. A Priority Queue Implementation in Python<\/a><\/li>
  4. Linked Lists Implementations In Python<\/a><\/li><\/ol>\n\n\n\n

    Introduction to queues<\/h2>\n\n\n\n

    In computer science, a queue is an abstract data type serving as a collection of items maintained in a sequence where items are added at one end and removed at the other<\/strong>. The operations of a queue make it a first-in, first-out<\/strong> data structure (FIFO).<\/p>\n\n\n\n

    Uses for queue<\/h2>\n\n\n\n

    In programming, you can use queues to implement applications and functionality that require FIFO data access. Some examples might be:<\/p>\n\n\n\n

    1. The keyboard buffer.<\/li>
    2. The printer queue.<\/li>
    3. The mail queue.<\/li>
    4. IO buffers.<\/li><\/ol>\n\n\n\n

      Queue methods<\/h2>\n\n\n\n

      Most queue implementations have the following methods:<\/p>\n\n\n\n

      1. queue.enqueue(x): <\/strong>adds an element to the back of the queue.<\/li>
      2. queue.dequeue():<\/strong> returns and removes the element at the front of the queue.<\/li>
      3. queue.peek():<\/strong> returns the element at the front of the queue.<\/li>
      4. queue.size():<\/strong> returns the number of elements in the queue.<\/li>
      5. queue.is_empty():<\/strong> returns True is the queue is empty.<\/li><\/ol>\n\n\n\n

        Queue implementation<\/h2>\n\n\n\n

        Python implements multi-producer, multi-consumer queues in the Lib\/queue.py module<\/strong>. For production applications requiring queues, you should import and use those implementations.<\/p>\n\n\n\n

        Since our purpose with this article is to study queues as preparation for a technical interview, we’ll do our implementation using the double-ended queue (deque)<\/strong> available from the collections module in Python. The reason for using deques instead of other data types like lists are:<\/p>\n\n\n\n

        1. In deques, appends and poplelfts<\/strong> are memory efficient and thread-safe.<\/li>
        2. In deques, appends and poplelfts have constant time complexity O(1)<\/strong><\/li><\/ol>\n\n\n\n

          Let’s go over our queue implementation using deques.<\/p>\n\n\n\n

          The Queue class<\/h3>\n\n\n\n

          We define a Queue class with a constructor that instantiates an empty deque and a __str__ method that returns a readable representation of the queue object. At the top of the module, we must import deque from collections.<\/p>\n\n\n\n