Queue (Implementation)

Implementation of Queues

Queues are implemented in many ways. They can be represented by using lists, Linked Lists, or even Stacks. But most commonly lists are used as the easiest way to implement Queues.

With typical arrays, however, the time complexity is O(n) when dequeuing an element from the beginning of the queue. This is because when an element is removed, the addresses of all the subsequent elements must be shifted by 1, which makes it less efficient. With linked lists and doubly linked lists, the operations become faster.

Here, we will use a doubly-linked list to implement queues.

A typical Queue must contain the following standard methods:

• enqueue(element)
• dequeue()
• is_empty()
• front()
• rear()

We will take a look at these functions individually, but, before that, let’s construct a class of Queue called MyQueue and create an object of this class with queue_obj name. The class consists of relevant functions for the queue and a data member called items. The data member is a doubly-linked list that holds all the elements in the queue. The code given below shows how to construct a Queue class.