A queue is a data structure which stores items in sequence, in which we add items at the bottom of the queue, and we remove items from the top of the stack.
Notice that the items are thus available in the order in which they were originally added. Queues are sometimes referred to as "Last In, Last Out" (LILO) or "First In, Fast Out" (FIFO) data structure.
The idea of a queue should be easy to visualize. Suppose you are waiting in line for the service of a teller at a bank. You enter the line at the back and the next customer to be served will be the one at the front. The idea of a queue is "wait your turn".
The data stored in a queue may be of various kinds: integers, characters, strings, floating-point numbers, structs, etc., or pointers to items stored elsewhere. If we use the idea of a template class, we can create a queue which works for various types of data. (See the web page on "template functions and classes".)
Queue operations
Suppose we have a queue of integers. The operations normally provided for a queue are the following:
Create a new queue.
Get rid of a queue.
Insert an int at the bottom of the queue.
Remove an int from the top of the queue.
Look at the int at the top of the queue.
Return true if the queue is empty and false otherwise.
Return true if the queue is full and false otherwise.
Optionally, we may also have a counter of the number of items in the queue; the counter would be incremented and decremented as needed by the Push and Pop operations. If we have a counter, we probably also have a function to give us the value of the counter.
Normally, the user will check the Empty function before attempting to use the Pop operation, and likewise check the Full function before attempting to use the Push operation. (If we pop an empty queue or push an item onto a full queue, this is an error.)
The user does not need to know how the queue in implemented; he or she simply uses the queue operations, that is, the public interface.
How is a queue implemented?
A queue may be implemented in various ways:
Depending on the choice, some operations may be slower or faster, or may use more or less memory.
We will usually implement the queue as a class, so the Initialize and Dispose operations may correspond to the constructor and destructor.
If we use a linked list or a dynamically-sized array, the Full function may simply always return false, as we can always enlarge the queue (as long as we do not run out of memory).
Double-Ended Queues
A variation on the idea of a queue is a deque or double-ended queue. In a deque, we can add items at either end, and we can remove items at either end. Thus we would have operations such as:
It should be clear what each of these does.
A deque can be implemented in several ways: