A queue is a data structure that takes its name from a physical queue, such as at a supermarket. Items are inserted into a queue at one end and removed at the other. This principle is often referred to as FIFO (which stands for First In First Out) because the first item into the queue is the first one out.
A queue is essential to any breadth first search. It can also be used to simulate things like a printer queue that operates on a "first come, first serve" basis.
There are a number of ways of implementating queues. One method that is fairly efficient is a circular queue. A slightly easier method is a bulk move queue. I sometimes use my own variety, in which I split the queue into two parts with an array for each. I remove items from the one and add to the other, and when the one I'm removing from is empty I swap the two. A queues can also be implemented as a linked list, but this isn't usually a good idea.
Last updated Sun Nov 28 22:04:38.0000000000 2004. Copyright Bruce Merry (bmerry '@' gmail dot. com).