Queues are used to model data structures in computer programming. Both linear and circular queues involve a series of data items being stored using a "first in first out" system. This means that the first item added to the queue is the first to be removed from it, with the last item added also last to be removed. In abstract terms, items are added to the rear of a queue and removed from the front. However, this is implemented differently in circular and linear queues. The differences between these two queue types have implications for memory, efficiency and processing.
First in first out
In both linear and circular queues, the "first in first out" rule applies. All new items added to either a linear or a circular queue join the queue at the rear, as in real-life queues. The only item that can be removed from a queue at any time is the one at the front. In this sense, both linear and circular queues are accessible only at either end. Within computer programming, this access is managed by keeping pointers to the front and rear of the queue. These pointers keep a record of the location in memory at which the front and rear items are stored. Where the other items are in relation to these two depends on whether the queue is circular or linear.
Underlying linear structure
Programming languages provide a range of storage options in which developers can manage queues. For example, a programmer could use an array structure to store either a linear or a circular array. For a linear array, the first item in the queue could initially be stored at the first position in the array structure, which has a zero index. If the queue had ten items in it, the last item in the queue would initially be at position nine. When an item was removed from the queue, from position zero, the front pointer would move to position one. When an item was added to the queue, the rear pointer would also be incremented by one.
Underlying circular structure
If a program uses an array structure to store a circular queue, the queue would appear to behave in the same way externally, but the implementation details would be different. For example, with a circular queue, if an item was removed from the front and another added to the rear, rather than the front and rear pointers both incrementing, the item added to the rear of the queue could actually be placed at position zero, which was where the item at the front had originally been stored. This way, the front and rear pointers would still be incremented to keep track of where the front and of the queue was, but when each reaches the end of the structure, it would be set back to the start of the array and move forward from there.
Using an array to store a queue is a good example of when circular arrays can offer an improvement in terms of the storage resources a program uses. If each time items are added to a queue, the back of the queue extends, this means that the overall amount of memory allocated to the queue could continue increasing, even if items are being removed from the front. This could mean that the overall length of the queue remains the same but the memory it requires keeps getting bigger. Circular queues allow programs to reuse the same locations in memory as items are removed and added. If the queue remains roughly the same length, this way it does not require more memory as items are added and removed.
Although circular queues improve on memory when compared with linear queues, they do require a different algorithm within the program that is managing access to the items. For example, with a linear queue, the front and rear pointers are simply incremented each time an item is added or removed. However, with a circular queue, an algorithm must be implemented that makes each pointer move back to the start of the allocated storage structure whenever it reaches the end.
- Epoxy/Photodisc/Getty Images