Imagine a line that moves only forward. A linear queue stores items in an array, adds new items toward larger indexes, and removes items from the front. Once the rear reaches the array’s end, the queue is treated as full—even if earlier positions became empty. section 9.7 section 9.18
A linear queue follows these practical rules:
- Enqueue adds an element to the back, while dequeue removes and returns the element at the front. section 9.18
- Dequeuing leaves holes at the beginning of the array, so usable space shrinks as the rear advances. section 9.7
- An array allocated for n elements supports only n insertions before the rear reaches its end, even after removals. section 9.7
Why the space disappears
Suppose a queue uses an array with eight positions. After several dequeues, the first positions are empty, but newly enqueued elements continue toward larger indexes. When the rear reaches position seven, the linear queue is full; reclaiming the holes would require moving the remaining elements. section 9.7
This design is simple but usually impractical. Moving elements toward the start reclaims space but costs O(n) each time; a circular queue instead wraps its indexes around the array and reuses freed positions. section 9.7 section 9.9
