Queue Data Structure

Intro

Queue is a LIFO (First In First out) based data structure. That means the element we add first will be the first one to be removed from the queue.
It is just like a queue (line) of people waiting to enter the cinema. People that got there first, will be the first to enter the cinema.

Implementing the Queue data structure in Java

For the Queue, we use the Linked List as a backed data structure and we keep track of the first element (front) and last element (rear) for easy and quick access.

The basic structure of the Queue class:

public class Queue<T> {

  private Node<T> front;
  private Node<T> rear;
  private int size;

  public Queue() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

}

class Node<T> {
  public T data;
  public Node next;

  public Node(T data) {
    this.data = data;
    this.next = null;
  }
}

A method called enqueue - for adding an element to the queue:

public void enqueue(T data) {
  Node<T> newNode = new Node<>(data);

  if (size == 0) {
    front = newNode;
  } else {
    rear.next = newNode;
  }

  rear = newNode;
  size++;
}

If the queue has only one element, then both the front and rear will point to it.

Let's implement a method for removing the element - dequeue():

public T dequeue() {
  if (size == 0) {
    throw new NoSuchElementException("The queue is empty");
  }

  T data = front.data;
  front = null;

  if (front.next == null) {
    rear = null;
  }

  size--;
  return data;
}

Here is the complete Queue class:

public class Queue<T> {

  private Node<T> front;
  private Node<T> rear;
  private int size;

  public Queue() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  public void enqueue(T data) {
    Node<T> newNode = new Node<>(data);

    if (size == 0) {
      front = newNode;
    } else {
      rear.next = newNode;
    }

    rear = newNode;
    size++;
  }

  public T dequeue() {
    if (size == 0) {
      throw new NoSuchElementException("The queue is empty");
    }

    T data = front.data;
    front = null;

    if (front.next == null) {
      rear = null;
    }

    size--;
    return data;
  }

  public void show() {
    if (front == null) {
      throw new NoSuchElementException("The queue is empty");
    }

    Node<T> current = front;

    while (current != null) {
      System.out.println(current.data);
      current = current.next;
    }
  }

}

class Node<T> {
  public T data;
  public Node next;

  public Node(T data) {
    this.data = data;
    this.next = null;
  }
}

Queue data structure - analysis

Time complexity for both operations (enqueue and dequeue) is O(1) since we are handling only the elements at the beggining (front) or at the end of a queue (rear), no operations on the middle elements  hence no iteration needed.