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). 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.

package queue;

/**
 * Implementation of a Queue.
 * The inner array acts as a Ring Buffer, which makes this a circular queue.
 */
public class Queue<T> {

    /**
     * Position of the front element
     */
    private int front;
    /**
     * Position of the rear element
     */
    private int rear;
    /**
     * Size, number of elements in the queue
     */
    private int size;
    /**
     * Inner array, the actual queue.
     */
    private T[] arr;

    /**
     * Constructor, init. array and positions
     *
     * @param size The size of the queue.
     */
    public Queue(int size) {
    }

    /**
     * Placing item x in the queue.
     *
     * @throws IllegalStateException Queue is full
     */
    public void enqueue(T x) {

    }

    /**
     * Removing the front element from the queue.
     *
     * @return The front element of the queue
     * @throws java.util.NoSuchElementException Queue is empty
     */
    public T dequeue() {

    }

    /**
     * @return The front element of the queue.
     * @throws java.util.NoSuchElementException Queue is empty
     */
    public T front() {

    }

    /**
     * @return The rear element of the queue
     * @throws java.util.NoSuchElementException Queue is empty.
     */
    public T rear() {

    }

    /**
     * @return True if queue is empty (size = 0), false otherwise.
     */
    public boolean isEmpty() {

    }

    /**
     * @return True if queue is full (size = arr.length), false otherwise.
     */
    public boolean isFull() {

    }

    /**
     * @return Size (number of elements).
     */
    public int size() {

    }
}

If you read the class comments, you might have noticed that two new terms have 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 that can contain a total of five 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 have been executed, the queue will look like this:

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).

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

package queue;

import java.util.NoSuchElementException;

/**
 * Implementation of a Queue.
 * The inner array acts as a Ring Buffer, which makes this a circular queue.
 *
 * @author Anders Engen Olsen
 */
public class Queue<T> {

    /**
     * Position of the front element
     */
    private int front;
    /**
     * Position of the rear element
     */
    private int rear;
    /**
     * Size, number of elements in the queue
     */
    private int size;
    /**
     * Inner array, the actual queue.
     */
    private T[] arr;

    /**
     * Constructor, init. array and positions
     *
     * @param size The size of the queue.
     */
    public Queue(int size) {
        front = rear = -1;
        this.size = 0;
        arr = (T[]) new Object[size];
    }

    /**
     * Placing item x in the queue.
     *
     * @throws IllegalStateException Queue is full
     */
    public void enqueue(T x) {
        if (isFull())
            throw new IllegalStateException("Queue is full");

        if (isEmpty()) {
            front = rear = 0;
            arr[0] = x;
        } else {
            rear++;
            if (rear > arr.length - 1)
                rear = 0;
            arr[rear] = x;
        }

        size++;
    }

    /**
     * Removing the front element from the queue.
     *
     * @return The front element of the queue
     * @throws java.util.NoSuchElementException Queue is empty
     */
    public T dequeue() {
        if (isEmpty())
            throw new NoSuchElementException("Queue is empty");

        // Storing current front object.
        if (front > arr.length - 1)
            front = 0;
        T val = arr[front];

        // Updating the front position.
        front++;

        // Decrease size
        size--;

        return val;
    }

    /**
     * @return The front element of the queue.
     * @throws java.util.NoSuchElementException Queue is empty
     */
    public T front() {
        if (isEmpty())
            throw new NoSuchElementException("Queue is empty");

        return arr[front];
    }

    /**
     * @return The rear element of the queue
     * @throws java.util.NoSuchElementException Queue is empty.
     */
    public T rear() {
        if (isEmpty())
            throw new NoSuchElementException("Queue is empty");

        return arr[rear];
    }

    /**
     * @return True if queue is empty (size = 0), false otherwise.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * @return True if queue is full (size = arr.length), false otherwise.
     */
    public boolean isFull() {
        return size == arr.length;
    }

    /**
     * @return Size (number of elements).
     */
    public int size() {
        return size;
    }
}

I have also written a simple unit test in JUnit.

import org.junit.Before;
import org.junit.Test;

import static org.junit.Assert.*;

import queue.Queue;

import java.util.NoSuchElementException;

public class QueueTest {

    private Queue<Integer> queue;

    @Before
    public void setUp() {
        queue = new Queue<>(5);
    }

    @Test
    public void testEmptyQueueReturnsTrue() {
        assertTrue(queue.isEmpty());
    }

    @Test
    public void testEmptyQueueHasSizeZero() {
        assertEquals(0, queue.size());
    }

    @Test(expected = NoSuchElementException.class)
    public void testDequeueEmptyQueueThrowsException() {
        queue.dequeue();
    }

    @Test(expected = NoSuchElementException.class)
    public void testGetFrontEmptyQueueThrowsException() {
        queue.front();
    }

    @Test(expected = NoSuchElementException.class)
    public void testGetRearEmptyQueueThrowsException() {
        queue.rear();
    }

    @Test(expected = IllegalStateException.class)
    public void testExceptionThrownWhenFull() {
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
        }
    }

    @Test
    public void testQueueWrappingAround() {
        for (int i = 1; i <= 3; i++) {
            queue.enqueue(i);
        }

        assertEquals(1, (int) queue.dequeue());
        assertEquals(2, (int) queue.dequeue());

        for (int i = 4; i <= 6; i++) {
            queue.enqueue(i);
        }

        assertEquals(3, (int) queue.front());
        assertEquals(6, (int) queue.rear());

        for (int i = 3; i <= 6; i++) {
            assertEquals(i, (int) queue.dequeue());
        }

        assertTrue(queue.isEmpty());
    }


    @Test
    public void testInsertTwoElementsAndDequeue() {
        queue.enqueue(1);
        queue.enqueue(2);

        assertEquals(1, (int) queue.dequeue());
        assertEquals(2, (int) queue.dequeue());
    }

}

Happy coding!

If you enjoyed this article and want to learn more about Java Collections, check out this collection of tutorials and articles on all things Java Collections.