Queue implementation in Python

Posted on Edited on In , Views:

What is queue

Like stack, queue is also a linear data structure in which the items are stored in a First-In-First-Out(FIFO)manner.

The queue may include the following key functions.

  • enqueue() - add an item to the end of the queue
  • dequeue() - remove the front item
  • size() - return the number of items in queue
  • peek() - return the front item
  • is_empty() - check if the queue is empty

How to implement

There are various ways to implement a queue in Python. In this post, we will learn how to implement it with the following ways.

  • list
  • collections.deque
  • queue.Queue
  • linked list

using list

In Python, list is like dynamic array. The items in list are stored contiguously in memory. Thus, the random access to list is as fast as array. However, inserting/deleting item in front of the queue is slow because it requires shifting other items with time complexity O(n).

st = []
st.append(1)
st.append(2)
st.append(3)
print("stack size: {}".format(len(st)))
print(st.pop(0))
print(st.pop(0))
print(st.pop(0))
print("stack size: {}".format(len(st)))

using collections.deque

deque is pronounced “deck” and stands for “double-ended queue”. It is built upon a doubly linked list which allows insert/remove nodes from both ends with constant time O(1). Deque is the prefered method to implement a queue in Python. Note that deque is not thread-safe.

from collections import deque

st = deque()
st.append(1)
st.append(2)
st.append(3)
print("stack size: {}".format(len(st)))
print(st.popleft())
print(st.popleft())
print(st.popleft())
print("stack size: {}".format(len(st)))

using queue.Queue

If you need multi-threading, you can use queue.Queue module. However, it comes at a performance cost to achieve the thread-safety.

from queue import Queue

st = Queue()
st.put(1)
st.put(2)
st.put(3)
print("stack size: {}".format(st.qsize()))
print(st.get())
print(st.get())
print(st.get())
print("stack size: {}".format(st.qsize()))

using linked list

You also can implement your own queue with the linked list data structure.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None


class MyQueue:
    def __init__(self):
        self.front = self.rear = None
        self.size = 0

    def get_size(self):
        return self.size

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

    def enqueue(self, val):
        n = Node(val)
        if self.rear == None:
            self.front = n
            self.rear = n
        else:
            self.rear.next = n
            self.rear = n

        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("empty stack")

        val = self.front.val
        self.front = self.front.next
        self.size -= 1
        return val

    def __str__(self):
        curr = self.front
        st_str = ""
        while curr:
            st_str += str(curr.val) + "->"
            curr = curr.next
        return st_str[:-2]


qu = MyQueue()
qu.enqueue(1)
qu.enqueue(2)
qu.enqueue(3)
print("queue: {}".format(qu))
print("queue size: {}".format(qu.size))
print(qu.dequeue())
print(qu.dequeue())
print(qu.dequeue())
print("queue size: {}".format(qu.size))