Implementing an efficient queue in Python

Question

I have been trying to implement a queue in Python, and I've been running into a problem.

I am attempting to use lists to implement the Queue data structure, however I can't quite figure out how to make enqueue and dequeue O(1) operations.

Every example I have seen online, seems to just append the enqueue operation and remove the first element from the list for the dequeue operation. But this would make the dequeue operation O(n) (where n is the size of the list) correct?

Is there something basic I have missed? Or do you have to use LinkedLists to implement a Queue efficiently?

import unittest

class Queue:
    def __init__(self):
        self._queue = []
        self.size = 0
        self.maxSize = 10

    def enqueue(self, item):
        if self.size < self.maxSize:
            self._queue.append(item)

    def dequeue(self):
        '''
        Removes an item from the front of the list. Remove first element of
        the array
        '''
        first = self._queue[0]
        del self._queue[0]
        return first

Answer 1

As Uri Goren astutely noted above, the Python stdlib already implemented an efficient queue on your fortunate behalf: collections.deque.

What Not to Do

Avoid reinventing the wheel by hand-rolling your own:

• Linked list implementation. While doing so reduces the worst-case time complexity of your dequeue() and enqueue() methods to O(1), the collections.deque type already does so. It's also thread-safe and presumably more space and time efficient, given its C-based heritage.
• Python list implementation. As I note below, implementing the enqueue() methods in terms of a Python list increases its worst-case time complexity to O(n). Since removing the last item from a C-based array and hence Python list is a constant-time operation, implementing the dequeue() method in terms of a Python list retains the same worst-case time complexity of O(1). But who cares? enqueue() remains pitifully slow.

To quote the official deque documentation:

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.

More critically, deque also provides out-of-the-box support for a maximum length via the maxlen parameter passed at initialization time, obviating the need for manual attempts to limit the queue size (which inevitably breaks thread safety due to race conditions implicit in if conditionals).

What to Do

Instead, implement your Queue class in terms of the standard collections.deque type as follows:

from collections import deque

class Queue:
    '''
    Thread-safe, memory-efficient, maximally-sized queue supporting queueing and
    dequeueing in worst-case O(1) time.
    '''


    def __init__(self, max_size = 10):
        '''
        Initialize this queue to the empty queue.

        Parameters
        ----------
        max_size : int
            Maximum number of items contained in this queue. Defaults to 10.
        '''

        self._queue = deque(maxlen=max_size)


    def enqueue(self, item):
        '''
        Queues the passed item (i.e., pushes this item onto the tail of this
        queue).

        If this queue is already full, the item at the head of this queue
        is silently removed from this queue *before* the passed item is
        queued.
        '''

        self._queue.append(item)


    def dequeue(self):
        '''
        Dequeues (i.e., removes) the item at the head of this queue *and*
        returns this item.

        Raises
        ----------
        IndexError
            If this queue is empty.
        '''

        return self._queue.pop()

The proof is in the hellish pudding:

>>> queue = Queue()
>>> queue.enqueue('Maiden in Black')
>>> queue.enqueue('Maneater')
>>> queue.enqueue('Maiden Astraea')
>>> queue.enqueue('Flamelurker')
>>> print(queue.dequeue())
Flamelurker
>>> print(queue.dequeue())
Maiden Astraea
>>> print(queue.dequeue())
Maneater
>>> print(queue.dequeue())
Maiden in Black

It Is Dangerous to Go Alone

Actually, don't do that either.

You're better off just using a raw deque object rather than attempting to manually encapsulate that object in a Queue wrapper. The Queue class defined above is given only as a trivial demonstration of the general-purpose utility of the deque API.

The deque class provides significantly more features, including:

...iteration, pickling, len(d), reversed(d), copy.copy(d), copy.deepcopy(d), membership testing with the in operator, and subscript references such as d[-1].

Just use deque anywhere a single- or double-ended queue is required. That is all.

Answer 2

You can keep head and tail node instead of a queue list in queue class

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


class Queue:
    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None

    def enqueue(self, value):
        newNode = Node(value)
        if self.head is None:
            self.head = self.tail = newNode
        else:
            self.tail.next = newNode
            newNode.previous = self.tail
            self.tail = newNode
        self.length += 1

    def dequeue(self):
        item = self.head.item
        self.head = self.head.next 
        self.length -= 1
        if self.length == 0:
            self.tail = None
        return item

Answer 3

Queue implementation using list in Python, handling enqueue and dqueue as per inbuild queue data structure:

class queue:

    def __init__(self, max_size, size=0, front=0, rear=0):
        self.queue = [[] for i in range(5)] #creates a list [0,0,0,0,0]
        self.max_size = max_size
        self.size = size
        self.front = front
        self.rear = rear
    

    def enqueue(self, data):
        if not self.isFull():
            self.queue[self.rear] = data
            self.rear = int((self.rear + 1) % self.max_size)
            self.size += 1
        else:
            print('Queue is full')

    def dequeue(self):
        if not self.isEmpty():
            print(self.queue[self.front], 'is removed')
            self.front = int((self.front + 1) % self.max_size)
            self.size -= 1
        else:
            print('Queue is empty')

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

    def isFull(self):
        return self.size == self.max_size

    def show(self):
        print ('Queue contents are:')
        for i in range(self.size):
            print (self.queue[int((i+self.front)% self.max_size)])

        # driver program
        q = queue(5)
        q.enqueue(1)
        q.enqueue(2)
        q.enqueue(3)
        q.enqueue(4)
        q.enqueue(5)
        q.dequeue()
        q.show()