Answer in Short
Queue can be implemented using an Array, Stack or Linked List.The easiest way of implementing a queue is by using an Array. Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of arrayExplanation
969
0
==> Implementation of Queue--
- Queue can be implemented using an Array, Stack or Linked List.
- The easiest way of implementing a queue is by using an Array.
- Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of array from 0).
- As we add elements to the queue, the rear keeps on moving ahead, always pointing to the position where the next element will be inserted, while the front remains at the first index.
- When we remove element from Queue, we can follow two possible approaches (mentioned [A] and [B] in above diagram).
- In [A] approach, we remove the element at front position, and then one by one move all the other elements on position forward.
- In approach [B] we remove the element from front position and then move front to the next position.
- In approach [A] there is an overhead of shifting the elements one position forward every time we remove the first element.
- In approach [B] there is no such overhead, but whenever we move head one position ahead, after removal of first element, the size on Queue is reduced by one space each time.
.png)