Array-Based Queue Implementation
You'll learn how to build a working queue using a fixed-size array and two tracking pointers.
The Core Idea
A queue follows FIFO (first-in, first-out), like a line at a coffee shop. Using an array, we can implement this by keeping track of two positions: where the front of the queue is (where we remove items) and where the rear is (where we add new items).
Think of it like a row of parking spaces. The front pointer marks which space holds the first customer waiting, and the rear pointer marks where the next arriving customer should park.
How It Works
When you create an array-based queue with fixed size (say, 10 slots), you initialize:
front = 0(or -1 for an empty queue)rear = -1(no items yet)array[10](your storage)
Enqueue (add to rear):
- Increment
rear - Place the new item at
array[rear]
Dequeue (remove from front):
- Retrieve the item at
array[front] - Increment
front
The Wrap-Around Problem
Here's the catch: as you enqueue and dequeue, both pointers move rightward. Eventually, rear hits the end even though spaces at the start might be empty! The solution? Circular array logic using modulo (%): when rear reaches the end, wrap it back to index 0 if there's space.
Space Considerations
- Fixed capacity means you must handle "queue full" conditions
- Wasted space can occur without circular wrapping
- Simple to implement but inflexible compared to linked structures
Key Takeaway: An array-based queue uses front and rear pointers to track FIFO order within a fixed-size array, typically requiring circular logic to reuse space efficiently.