00:00

Help Us Improve

We're sorry this tutorial wasn't helpful. Please tell us what we can do better.

Queue Implementation using Linked List

A Queue is a linear data structure to store and manipulate the data elements. A queue follows the concept of "First in, First out" (FIFO), where the first element inserted into the queue is the first one to be deleted from the queue.

A queue is open at both ends which enables insert operations to be performed at one end called REAR or TAIL and delete operations to be performed at another end called FRONT or HEAD.

Operations in Queue

  1. Enqueue: Add a new element to the end of the queue.

  2. Dequeue: Remove an element from the front of the queue.

  3. Peek or front: Retrieve the frontmost element in the queue without deleting it.

  4. rear: Returns the element at the end in the queue without deleting it.

  5. isFull: Checks if the queue is full.

  6. isEmpty: Checks if the queue is empty.

Example: Queue Implementation using Linked List in Java

Class: Node

Node.java 
class Node {
  int data;       // Store value
  Node next;      // Stroe address of next node

  // Initializing a node with data in the constructor
  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}

Class: Queue

QueueImplUsingLinkedList.java 
class Queue {
  // Pointer to the front and the rear of the linked list
  Node front, rear;

  // Constructor to initialize the front and rear
  Queue() {
    front = rear = null;
  }

  // Function to check the queue is empty
  boolean isEmpty() {
    if (front == null && rear == null) {
      System.out.println("Queue is Empty.");
      return true;
    }
    return false;
  }

  // Function to add an element to the queue
  void enqueue(int data) {

    // Create a new node
    Node node = new Node(data);

    // If queue is empty, the new node is both the front and rear
    if (rear == null) {
      front = rear = node;
      return;
    }

    // Add the new node at the end of the queue and change rear
    rear.next = node;
    rear = node;
  }

  // Function to remove an element from the queue
  void dequeue() {
    if (isEmpty()) {
      return;
    }

    // Store previous front and move front one node ahead
    front = front.next;

    // If front becomes null, then change rear also to null
    if (front == null) {
      rear = null;
    }
  }

  // Function to get the front element of the queue
  int getFront() {
    if (isEmpty()) {
      return Integer.MIN_VALUE;
    }
    return front.data;
  }

  // Function to get the rear element of the queue
  int getRear() {
    if (isEmpty()) {
      return Integer.MIN_VALUE;
    }
    return rear.data;
  }

  // Function to print queue elements
  void printQueue() {
    if (isEmpty()) {
      return;
    }
    while (front != null) {
      System.out.print(front.data + " ");
      // Move to the next node
      front = front.next;
    }
  }

}

public class QueueImplUsingLinkedList {
  public static void main(String[] args) {
    Queue queue = new Queue();

    // Enqueue (Insert) an elements into the queue
    queue.enqueue(10);
    queue.enqueue(20);

    System.out.println("Queue Front: " + queue.getFront());
    System.out.println("Queue Rear: " + queue.getRear());

    // Dequeue (Delete) an elements from the queue
    queue.dequeue();
    queue.dequeue();

    // Enqueue (Insert) an elements into the queue
    queue.enqueue(30);
    queue.enqueue(40);
    queue.enqueue(50);

    System.out.println("Queue Front: " + queue.getFront());
    System.out.println("Queue Rear: " + queue.getRear());

    // Print queue all elements of queue
    System.out.println("Queue elements: ");
    queue.printQueue();
  }
}
Output
Queue Front: 10
Queue Rear: 20
Queue Front: 30
Queue Rear: 50
Queue elements:
30 40 50