# Implementing Queue using Array

Implementing Queue data structure 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())

``````