Queue (Implementation)

Implementation of Queues

Queues are implemented in many ways. They can be represented by using arrays, linked lists, or even stacks. But most commonly, an array is used because it’s 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.

As discussed in the previous lesson, a typical queue must contain the following standard methods:

• enqueue(value)
• dequeue()
• isEmpty()
• getFront()

You will take a look at these functions individually. But before that, start with constructing a class of queue. The class will consist of a doubly linked list that holds all the elements in the queue and the relevant functions.

The code given below shows how to construct a Queue class: