A queue in computer science is not unlike one in everyday life; it's a collection of items that will be dealt with one at a time. If it helps, imagine the items as people lining up to get into a concert (though the data is not always stored linearly in practice). The simplest form for this queue to take would be first-in-first-out (FIFO) which is exactly what it says - the first person in the queue is the first person to get into the concert venue, and so on. However, this is not the only order people can enter in; some kind people queuing up might let big-time fans get in ahead of them, or some in the queue could have VIP passes that allow them entry first. Alternatively, the staff might admit concert-goers by the seat numbers on their ticket, regardless of who was there first, to reduce traffic in the venue. In this case, each person's seat number acts as their priority value, and this structure of queue is known as a priority queue. In general, the method of determining which item in a queue will be dealt with next is called the queuing discipline.
Example of the FIFO queuing discipline
Some common implementation methods for queues1 include:
- the linked queue which uses a linked list and pointers to the first and last items
- the circular buffer which uses an array and keeps track of the indices of the first and next array elements instead
Any implementation should allow for the three basic queue operations:
- add (enqueue) an item
- remove (dequeue an item
- check if the queue is empty
An implementation for a priority queue must of course also make room for a priority value that can be checked often and quickly.
Reference:
1. Downey, A.B., (). 'Queues and Priority Queues'. In: (ed), How To Think Like A Computer Scientist With Java. 1st ed. Java Directory: oopweb.com. ch.16.
Top image credit: Neil Rickards
© BrainMass Inc. brainmass.com April 30, 2024, 4:49 am ad1c9bdddf