Can a queue be implemented using an array?


#1

Question

This exercise discusses using a linked list to implement a queue. Is it possible to use an array to implement a queue?

Answer

Yes, an array can be used to implement a queue. In languages where the array size must be declared, the implementation would be limited to a bounded queue. There are different ways to use an array to implement a queue. A straightforward method is to designate index 0 of the array as the head of the queue. Each time an element is removed from the queue, index 0 is made available and the array elements can be copied from their prior index to a lower one (for example index 1 to 0, index 2 to 1, index 3 to 2, etc.). An alternate method would be to keep a separate variable to track which index represents the head of the queue and another to track the tail of the queue. Care must be taken using this approach to handle the case where the queue wraps around the end of the array and back to the start.