Implementing the Queue Data Structure
Queues are a type of data structure that manages data in a first in first out format. This means that the first thing that enters the queue is the first thing that is removed from the queue. They are used in a variety of applications, such as simulation, and process management. Queues follow the same general structure as stacks, in the sense that they use a single Node object to keep track of all the data contained within them. For that matter, we can use the exact same Node we wrote for our stack object in the implementation of the queue. The key difference lies in how we insert the values into the structure.
Consider a situation where we want to make a queue of integers. If we were to insert the values 2, 3, and 4 in the order given, we would get a queue like below.
If we wanted to insert a new value, say the number 5, we would need to add it to the end of the queue.
If we want to remove a value from the queue, we would remove the first value in the queue, since the first value is the first value removed.
As you can see, when we add values to the queue, we need to place them at the end of the queue. When we remove values from the queue, we need to remove it from the beginning of the queue. There are a few different options for how we can program this logic. The most basic way to do this is to keep track of what is in front of the queue and what is at the end of the queue. When we want to remove, we update the front to be the next value in the queue, like popping off a stack. When we want to insert, we update the next value of the current rear of the queue, then update the rear itself to point to the new last value.
To achieve this, we use the same Node structure as our stack object.
For our queue object, we will have two properties called front and rear. The front property will track the current front of the queue and the rear property keeps track of the last element in the queue. We will have three methods, add, remove, and peek. Add will put a new value on the end of the queue, remove will remove the first value from the queue, and peek will show the first value in the queue without removing it.
There are some similarities between the queue and stack implementation. The peek and remove are the same, since they both deal with the first value in the structure. When we insert values into the queue, we have two cases that we need to handle. If the queue is currently empty (the front is null), we update the front and rear to be the same value, the one just inserted. If there is a front value, then we just need to update the rears next value to be the one inserted, and then update the rear to point to the new last value.
To illustrate this, here is an example that uses the queue data structure.
The diagram below illustrates how this code execution works.
This gives you a basic idea of how to implement a queue in Java. Once you understand stacks, you can easily apply the logic to queues as well, making the implementation easy. You will find that as you continue learning data structures, there emerges general patterns on how each structure is implemented. These patterns will make it easy to implement the structures whenever you need to.