2.7. Queues

Hey you, stand in line behind!” Unfortunately, queues are ubiquitous in life. Queues form wherever many tasks have to be carried out by only a few or even one lonely worker.

Since programs model a part of the real world, it is not surprising that the queue is one of the elementary data structures, appearing in many problem definitions.

A queue is a data structure in which elements are stored in a linear sequence and in which insertion is allowed at one end of the sequence only, deletion, however, only at the other end. Figure 2.21 shows a queue.

Figure 2.21. A queue

A queue

So queues are very similar to stacks, with the difference that insertion of elements happens at the other side than deletion. To use the example with the plates in the cupboard from Section 2.4 once again: A good housewife always lines up her plates from behind. That means, she uses a queue, not a stack.

Who comes first grinds first”, as a German proverb goes. Because elements are always inserted at a fixed end of the sequence and removed at the other one, the first element which was brought in into the structure is always the first one which is pulled out again. One therefore says that queues work according to the FIFO principle (“first in first out”).

The element which will be deleted next is called the head of the queue, the element at the other end is called the tail. To remain solid with the notions used with stacks, in LEDA the head is also referred to as the top and a deletion is referred to as pop. Insertion is called append, not push, to make clear the difference in comparison with stacks.

LEDA offers the classes queue and b_queue as implementations for queues. The former class covers queues which can store an arbitrary number of elements. The second one is particularly useful if we know in advance that only a certain, bounded number of elements will ever be hold in the queue (“bounded queue”).

Here the same question arises as in the the introduction of stacks: Why shall we use queues if we can do everything with the type list anyway? The answers given in Section “What for shall we use a stack at all?” hold here likewise.

So let us have a look at queues in a typical situation.