Queues

Overview

As we saw, stacks are "Last In First Out" (LIFO) data structures. This means that the last thing added to the stack is the first thing that is removed.

If we do the opposite of this, and remove the first thing we added instead of the last, then we get a queue. A queue is a "First In First Out" (FIFO) data structure.

You can think of a queue as a list of objects waiting in line. Queues always have a start and an end. Objects are added at the end of the queue, and removed from the start. The following image depicts a queue.

There are three objects in a row. The first is labelled 'end' and the last is
labelled 'start' — A queue

If we want to add to the queue, we must add to the end. This operation is called "enqueue".

After enqueueing an object, the new object gets added to the end of the
queue — Enqueueing an object

Likewise, if we want to remove an element from a queue, we have to do so from the start. This operation is called "dequeue".

After dequeueing, the object at the start is removed — Dequeueing an object

Applications of Queues

Queues are useful whenever we want to store things in order and get them back out in the same order:

Buffering data.
- Output.
- Inter-Process Communication.
- Networking.
Simulating lines.
Scheduling tasks.
Handling multiple clients (servers).

Implementation with an Array

Like stacks, queues can be implemented using either an array or a linked list. Since queues add at one end, and remove from the other, they are a little more complicated to implement than stacks.

In our array, we have to keep track of the start and the end. Initially, we start both of these at negative one as the queue is empty:

There is an empty array. The variables start an end are both
equal to -1 — An empty array queue

When we enqueue elements, we add them at the end, and increment the end variable:

After enqueueing 4 values, the array contains those values, in the order
they were enqueued. The start is 0, and the end is 3 — Enqueueing items

Then, when we dequeue elements, we take them from the start and increment the start variable:

After calling dequeue twice, the two items at the start are removed.
The start is now 2, and the end is still 3. — Dequeueing items

The tricky part of implementing a queue with an array, is that the start and then end can both wrap around the end of the array. If we enqueue 4 more things in the example above, we will need to loop the end back to 0.

ArrayQueue.java shows an implementation of this idea. The main method of this program uses the queue for a buffer of sorts. It stores values read from the user until there are 10, at which point it prints them out.

Implementation with a Linked List

Queues can also be implemented with a linked list. Because queues require us to access both ends of a data structure, this would be done most efficiently with a doubly-linked list.

The enqueue method would simply add an element at one end of the linked list, and the dequeue method would remove an element from the other end. We have seen code to do both of these things.