Java Program to Implement the Queue Data Structure

July 28, 2023

Java Queue Interface

The Java Queue interface is a part of the Java Collections Framework and provides an ordered collection of elements that follow the FIFO (First-In-First-Out) principle.
It extends the Collection interface and adds methods for inserting, removing, and examining the elements in the queue.
- You must be familiar with following topics to understand the correspond example Such as: Java Queue Interface and Java Generics.
To understand the Java Program to Implement the Queue Data Structure, Read the Complete Article.

Steps to Implement the Queue Data Structure.

Here are the steps to Implement the Queue Data Structure.
- Decide on the implementation method, whether to use the built-in LinkedList class or create a custom Queue class.
- If using the built-in LinkedList class, import it using import java.util.LinkedList;.
- Create a LinkedList instance to represent the queue.
- Add elements to the queue using the add() or offer() method.
- Remove elements from the queue using the remove() or poll() method.
- Retrieve the first element of the queue without removing it using the peek() method.
- Optionally, implement additional methods to get the size of the queue or check if it is empty.
- If creating a custom Queue class, define the methods for enqueueing, dequeueing, peeking, and other desired functionality.
- Test the implementation to ensure that it works correctly.

Java Queue Interface:

The Queue interface extends the Collection interface and provides methods for adding elements to the end of the Queue, removing elements from the front of the Queue, and inspecting the elements at the front and back of the Queue.

In Java, there are several classes that implement the Queue interface, such as LinkedList, PriorityQueue, and ArrayDeque. Each implementation has its own characteristics and usage scenarios.

Java Generics:

Java Generics is a feature introduced in Java 5 that allows you to write code that works with a variety of data types.

With Java Generics, you can define classes, interfaces, and methods that can work with different types of data, without having to write separate code for each data type.

Generics are implemented using angle brackets (< and >) and can be used to create generic classes, interfaces, and methods.

Generics provide several benefits which Includes:

Improved type safety: Generics provide compile-time type checking, which helps to prevent type errors at runtime.
Reusability: Generics allow you to write code that can be used with different data types, reducing the need to write duplicate code.
Code clarity: Generics make the code more readable and easier to understand, as the type of data being used is explicitly specified.

Introduction to java

enhanced-for-loop

enum-inheritance

Switch Statement in Java

Abstraction in Java

Let’s look at the Java Program to Implement the Queue Data Structure to perform certain operations.

Example 1: Java Program to implement Stack

Run

public class Main {

    private Object[] arr;
    private int top;
    private int capacity;

    public Main(int size) {
        arr = new Object[size];
        capacity = size;
        top = -1;
    }

    public void push(T item) {
        if (isFull()) {
            throw new IllegalStateException("Stack is full");
        }
        arr[++top] = item;
    }

    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        T item = (T) arr[top];
        arr[top--] = null;
        return item;
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return (T) arr[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == capacity - 1;
    }

    public int size() {
        return top + 1;
    }

    public static void main(String[] args) {
        Main stack = new Main(4);
        stack.push(15);
        stack.push(25);
        stack.push(50);
        System.out.println("Size of stack: " + stack.size());
        System.out.println("Top element: " + stack.peek());
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Size of stack: " + stack.size());
        System.out.println("Top element: " + stack.peek());
    }
}

Output

Size of stack: 3
Top element: 50
Popped element: 50
Size of stack: 2
Top element: 25

Explanation:

This implementation uses an array to store the elements of the Stack.

The push operation adds the item to the top of the Stack by incrementing the top variable and storing the item in the array.

The pop operation removes the top element of the Stack by retrieving it from the array, setting the corresponding array element to null, and decrementing the top variable.

The peek operation simply retrieves the top element of the Stack without removing it.

The isEmpty and isFull methods check if the Stack is empty or full, respectively.

The size method returns the current number of elements in the Stack.

Example 2 :Java Program to Implement Stack

Run

import java.util.*;

public class Main
{

  public static boolean isBalanced (String str)
  {
    Stack < Character > stack = new Stack <> ();
    for (int i = 0; i < str.length (); i++)
      {
	char ch = str.charAt (i);
	if (ch == '(' || ch == '{' || ch == '[')
	  {
	    stack.push (ch);
	  }
	else if (ch == ')' || ch == '}' || ch == ']')
	  {
	    if (stack.isEmpty ())
	      {
		return false;
	      }
	    char top = stack.pop ();
	    if ((ch == ')' && top != '(') || (ch == '}' && top != '{')
		|| (ch == ']' && top != '['))
	      {
		return false;
	      }
	  }
      }
    return stack.isEmpty ();
  }

  public static void main (String[]args)
  {
    String str1 = "([])(){}";
    String str2 = "([)]";
    System.out.println (str1 + " is balanced: " + isBalanced (str1));
    System.out.println (str2 + " is balanced: " + isBalanced (str2));
  }
}

Output

([])(){} is balanced: true
([)] is balanced: false

Explanation:

This program uses a Stack to check if the parentheses in the given string are balanced.

The isBalanced method iterates over each character in the string, and when it encounters an opening parentheses, it pushes it onto the Stack.

When it encounters a closing parentheses, it pops the top element from the Stack and checks whether the popped element matches the closing parentheses.

If the parentheses are not matched, the method returns false.

In the main method, two strings are tested to check whether they are balanced or not.

The first string contains balanced parentheses, while the second string contains unbalanced parentheses.

Example 3: Java Program to Implement stack using Queue interface.

Run

import java.util.LinkedList;
import java.util.Queue;

public class Main {

    private Queue q1 = new LinkedList();
    private Queue q2 = new LinkedList();
    private int size = 0;

    public void push(T item) {
        q1.add(item);
        size++;
    }

    public T pop() {
        if (size == 0) {
            throw new IllegalStateException("Stack is empty");
        }
        while (q1.size() > 1) {
            q2.add(q1.remove());
        }
        T item = q1.remove();
        size--;
        Queue temp = q1;
        q1 = q2;
        q2 = temp;
        return item;
    }

    public T peek() {
        if (size == 0) {
            throw new IllegalStateException("Stack is empty");
        }
        while (q1.size() > 1) {
            q2.add(q1.remove());
        }
        T item = q1.remove();
        q2.add(item);
        Queue temp = q1;
        q1 = q2;
        q2 = temp;
        return item;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        Main stack = new Main();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("Size of stack: " + stack.size());
        System.out.println("Top element: " + stack.peek());
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Size of stack: " + stack.size());
        System.out.println("Top element: " + stack.peek());
    }
}

Output

Size of stack: 3
Top element: 30
Popped element: 30
Size of stack: 2
Top element: 20

Explanation:

This implementation uses two Queues to simulate a Stack.

The push operation simply adds the item to q1, while the pop and peek operations first move all but the last element of q1 to q2 and return the last element.

The size and isEmpty methods simply use the size variable, which is updated with every push and pop operation.

In the main method, the StackUsingQueue class is instantiated, and several push, pop, peek, size, and isEmpty operations are performed to test the implementation.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Java Program to Implement the Queue Data Structure

Java Queue Interface

Steps to Implement the Queue Data Structure.

Generics provide several benefits which Includes:

Let’s look at the Java Program to Implement the Queue Data Structure to perform certain operations.

Example 1: Java Program to implement Stack

Output

Example 2 :Java Program to Implement Stack

Output

Example 3: Java Program to Implement stack using Queue interface.

Output

Prime Course Trailer

Related Banners

Get over 200+ course One Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription