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.
If we want to add to the queue, we must add to the end. This operation is called "enqueue".
Likewise, if we want to remove an element from a queue, we have to do so from the start. This operation is called "dequeue".
Queues are useful whenever we want to store things in order and get them back out in the same order:
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:
When we enqueue elements, we add them at the end, and increment the end variable:
Then, when we dequeue elements, we take them from the start and increment the start variable:
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.
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.
Copyright © 2020 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.