Queue

From GPWiki
Jump to: navigation, search

A queue resembles a stack in that it's defining operations are the adding and removing of elements. Where in a stack the removal order is LIFO (last in, first out), in a queue it is FIFO (first in, first out).

Implementing a queue is not entirely trivial. A linked list is a good candidate for the underlying data structure, but incurs quite a bit of overhead.

Some languages, notably .net, have the queue class already implemented.

If you know a maximum size for the queue you can also use a static array and keep two pointers/indices into it, one for the point where you are currently adding elements, and one for the point where you are removing them. When these get to the end of the array they wrap around to the beginning (sometimes this is called a circular buffer). Adding an element involves putting it at the position indicated by the 'end pointer' and incrementing that pointer. Removing an element consists of incrementing the 'start pointer' and returning the element it used to point at. When the 'end pointer' catches up with the 'start pointer' the queue is full. If you use a dynamic array and some creative code to decide when and how to resize the array you can even do this without the size limitation.