9 Queues: Keeping information in the same order as it arrives
In this chapter
- introducing the queue abstract data type
- understanding FIFO policy
- implementing a queue with arrays and linked lists
- exploring the applications of simple queues
The containers we discuss next are queues, sometimes referred to as simple queues to distinguish them from priority queues, which we describe in chapter 10.
Like stacks, queues are inspired by our everyday experience and are widely used in computer science. They also work similarly to stacks, with a similar underlying mechanism, and they can also be implemented using arrays or linked lists to hold the data. The difference is in details that we will learn about in this chapter.
A queue is a container that, similarly to a stack, only allows the insertion and removal of elements in specific positions. What operations are available on a queue? What determines the internal state of a queue, and how does it behave?
Let’s first understand how queues work, and then, later in this section, define their interface.
First in, first out
While stacks use the LIFO (last in, first out) policy, queues abide by a symmetric principle, called FIFO, which stands for first in, first out. FIFO means that when we consume an element from a queue, the element will always be the one that has been stored the longest, and it is the only one we can remove.