What is a Queue?

Today I’ll cover the queue, which is a linear data structure. The workings of the queue are very intuitive and easy to understand, as it works just as a regular queue (i.e. in the grocery store).

Unlike stacks,which follow the LIFO principle (Last In First Out), a queue follows the FIFO principle (First In First Out). Said in other words;

In a Queue data structure we remove the least recently inserted item.

If you ever get confused, just compare the data structure to a line at the grocery store. The one who has been waiting the longest, should be expedited first.

There are four basic operations that a queue should support:

  • enqueue(): The enqueue method add an item to the queue.
  • dequeue(): The dequeue method removes the least recently inserted item from the queue.
  • front(): The front method returns the item at the front of the queue (the next one to be removed when calling the dequeue method)
  • rear(): The rear method returns the item at the end of the queue, the most recently inserted item.

Apart from these four basic operations, we’ll also certainly benefit from some helper methods:

  • size(): Returning the number of items in the queue.
  • isFull(): True if the queue is full.
  • isEmpty(): True if the queue is empty.

We’ll also need some private variables, both for keeping track of positions in the queue, and an inner array for the actual queue:

  • front: The current position of the front element.
  • rear: The current position of the rear element.
  • size: The current size of the queue (number of items).
  • array: An inner array, containing the actual items in the queue.

We’ll also make our class generic, avoiding the general examples where you can only insert native int “objects” into the Queue.

A code skeleton for our Queue is presented out below. The skeleton is heavily commented.

If you read the class comments, you might have noticed that two new terms has been introduced: Ring Buffer and Circular Queue.

We want our inner array to act as a ring buffer, which means that if either front or rear reach the last position of the array, we’ll reconnect it back to the start of the array.

To explain why we should create a circular queue, we’ll first explain the problem we’ll encounter if we’re just creating a linear queue.

Assuming you have a queue which can contain a total of 5 elements. The following operations are performed on the queue:

  • enqueue(1). Front = 0, rear = 0.
  • enqueue(2). Front = 0, rear = 1.
  • enqueue(3). Front = 0, rear = 2.
  • dequeue(). Front = 1, rear = 2.
  • dequeue(). Front = 2, rear = 2.
  • enqueue(4). Front = 2, rear = 3.
  • enqueue(5). Front = 2, rear = 4.

After those operations has executed, the queue will look like this:

Visualization of the queue data structure

As you see, there are 2 available spots in the queue, index 0 and 1.
But, if the queue isn’t circular, what will happen if we try to enqueue the number 6? 

If you guessed that the queue will report back as being full, you are correct!
To tackle this problem, we need to make the queue circular. We want both front and rear to reset back to position 0 if the end of the queue has been reached (assuming the queue isn’t full).

Visualization of a queue data structure in java

Allright, let’s write a complete our code skeleton, and write a circular queue. Please refer to the comments for clarification.

I have also written a simple Unit test in JUnit.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *