How do you implement a queue using an array?

You can implement a queue using an array by maintaining two indices, front and rear, to add and remove elements.

A queue is a data structure that follows the First-In-First-Out (FIFO) principle. This means that the element that is added first will be the one that gets removed first. To implement a queue using an array, you need to maintain two indices, front and rear. The front index points to the start of the queue (where elements are removed from), and the rear index points to the end of the queue (where elements are added).

To initialise the queue, set both front and rear indices to -1. When adding (enqueue) an element, check if the queue is empty (front and rear indices are -1). If it is, set both indices to 0 and add the element at that position in the array. If the queue is not empty, increment the rear index by 1 and add the element at the new rear position.

When removing (dequeue) an element, first check if the queue is empty. If it is, there are no elements to remove and you can return an error or a specific value to indicate this. If the queue is not empty, remove the element at the front index. Then, check if this was the last element in the queue (front and rear indices are the same). If it was, reset both indices to -1 to indicate an empty queue. If it was not the last element, increment the front index by 1.

It's important to note that this implementation can lead to inefficient use of space in the array. Once an element is removed, its space in the array is not reused. This can be solved by using a circular queue, where the front and rear indices wrap around to the start of the array when they reach the end.

In terms of complexity, both enqueue and dequeue operations are O(1), as they involve a constant number of steps. However, this implementation requires O(n) space, where n is the capacity of the queue.