Implementing Queue using Array

The core property of a Queue data structure is that it allows adding new elements only from one end and allows removal of elements only from the other end. The endpoint at which new elements are added is the tail/rear end of queue and the endpoint from which the elements are removed is the front end of queue.

An array can be used to create a queue abstract data structure by restricting addition of new elements only after the most recently added element. While removing an element, we remove the oldest element among all other elements. Below illustrations showcase this behavior:

Initialize an empty queue using an array which can hold 4 elements
- [ _, _, _, _ ]
Push element 4 into the queue
- [ 4, _, _, _ ]
- Now the front of the queue is 4
Push element 6 into the queue
- [ 4, 6, _, _ ]
- Now the front of the queue still 4
- Think of element 6 as behind element 4
Pop front/first element from the queue
- [ _, 6, _, _ ]
- Now the front element becomes 6
Add elements 8 and 9 to the queue
- [ _, 6, 8, 9 ]
- Element 6 is still the front of queue
Let’s pop front/first element from the queue
- [ _, _, 8, 9 ]
Now lets push element 10 into the queue
- Since there is no space after element 9. Here we need to consider an array as circular buffer and keep adding elements from the beginning
- [ 10, _, 8, 9 ]
- Element 8 is still the front end of queue

In order to track from where the front element and last elements of the queue are, we use 2 variables: front and rear. The front variable stores index at which the first element in the queue is and the rear stores the index where the last element in the queue is. Once front or rear index crosses the last index in the array, we reset it back to the first index.

Below is the implementation of Queue using an Array:


class Queue:
    def __init__(self, size):
        self.size = size
        # Initialize an array which can hold a maximum of 'size' elements
        self.queue = [None] * size
        self.front = -1  # Initialize front index
        self.rear = -1   # Initialize rear index

    def is_empty(self):
        # If front is -1, queue is empty
        if self.front == -1:
            return True
        else:
            return False

    def push(self, item):
        # Change the front index from -1 to 0 if the queue is empty
        if self.is_empty():
            self.front = 0

        # Increment rear end by 1
        self.rear = self.rear + 1
        # If we reach end of array, reset it to 0
        if self.rear == self.size:
          self.rear = 0

        self.queue[self.rear] = item

    def pop(self):
        if self.is_empty():
            print("Queue is empty. Cannot remove elements.")
            return None
  
        # Remove the element at front index
        item = self.queue[self.front]
        self.queue[self.front] = None
        
        # If both front and rear index coincide durint pop,
        # it means the queue is empty
        if self.front == self.rear:
            self.front = -1
            self.rear = -1
        else:
            self.front = self.front + 1
            if self.front == self.size:
                self.front = 0

        return item

    def front_element(self):
        if self.is_empty():
            print("Queue is empty.")
            return None

        return self.queue[self.front]


# Let's now test the Queue Implementation:
queue = Queue(5)
print("Is queue empty?", queue.is_empty())

queue.push(1)
queue.push(2)
queue.push(3)
queue.push(4)
queue.push(5)

print("Is queue empty?", queue.is_empty())
print("Front element:", queue.front_element())

print("Popped element: ", queue.pop())
print("Popped element: ", queue.pop())
print("Popped element: ", queue.pop())
print("Popped element: ", queue.pop())
print("Popped element: ", queue.pop())

print("Is queue empty?", queue.is_empty())