Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Queue Basic Functions
3.
Working of Queue
4.
Implementation of Queue in Java
4.1.
Using arrays
4.2.
Using Queue Interface
4.2.1.
Priority Queue Interface
4.2.2.
LinkedList Interface
5.
Application of Queue
6.
Limitations
7.
Frequently Asked Questions
7.1.
Where can you find a queue in real life?
7.2.
What is the distinction between a stack and a queue?
7.3.
How many types of queues are there?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Queue Data Structure and Implementation in Java

Author Aditi
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

A queue is a linear data structure made up of a collection of objects that are arranged in a first-in-first-out order. This means that the first thing you put in will be the first thing you take out. Items are also removed in the order in which they were introduced.

Using a real-world scenario, we can relate a queue data structure to a line of people waiting for service. When one person is served, they go to the front of the line to serve the next person. They are assisted in the order that they arrive. Enqueue is the programming term for adding things to a queue, and dequeue is the term for removing items from a queue.

Queue Basic Functions

The following are some basic functions defined for a queue.

enqueue(): It's used to add an element to the back of the queue.

dequeue(): This method removes an element from the queue's front.

IsEmpty(): This method is used to determine whether or not the queue is empty.

IsFull(): This method is used to determine whether or not the queue is full.

peek(): It's used to get the front value without eliminating it from the equation.

Enqueue and dequeue operations in a queue utilizing an array have a complexity O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Working of Queue

The following is how queue operations work:

  • There are two pointers REAR AND FRONT
  • FRONT keeps track of the queue's first item.
  • REAR will monitor the queue's final element, 
  • FRONT and REAR are set to -1 initially.

 

Operation Enqueue

  • Check whether the queue is full.
  • Set the value of FRONT to 0 for the first element.
  • REAR index should be increased by one.
  • REAR points to a place where the new element should be added.
     

Operation Dequeue

  • Check whether the queue isn't full.
  • FRONT points to a value that is to be returned.
  • Rise 1 in the FRONT index
  • Set the values of FRONT and REAR to -1 for the final element.

Implementation of Queue in Java

Since we have known about the basic functions of queue and working of queue data structure. Now, it's time to see how to implement a queue using program source code in the Java programming language.

Using arrays

Queue can be implemented using arrays. But the main disadvantage is that the size of the queue will be fixed. Source code is given below displaying basic functions of queue:-

Code
class Queue {
 
    int len = 5;
    int items[] = new int[len];
    int front = -1;
    int rear = -1;
   
    boolean isFull(){
        if(rear == len - 1){
            return true;
        } else {
            return false;
        }
    }
   
    boolean isEmpty(){
        if(front == -1 && rear == -1){
            return true;
        } else {
            return false;
        }
    }
   
    void enQueue(int itemValue) {
        if(isFull()){
            System.out.println("Queue is full, Overflow condition");
        } else if(front == -1 && rear == -1){
            front = rear = 0;
            items[rear] = itemValue;
        } else{
            rear++;
            items[rear] = itemValue;
        }
    }
   
    void deQueue(){
        if(isEmpty()){
            System.out.println("Queue is empty. Nothing to dequeue. Underflow condition!!");
        } else if (front == rear){
            front = rear = -1;
        } else {
            front++;
        }
    }
   
    void display(){
        int i;
       
        if(isEmpty()){
            System.out.println("Queue is empty, underflow condition!!");
        } else {
            for(i = front; i <= rear; i++){
                System.out.println(items[i]);
            }
        }
    }
   
    void peak(){
        System.out.println("Front index value is: " + items[front]);
    }
   
  }

  public class Main
  {
    public static void main(String[] args) {
        Queue myQueue = new Queue();
       
        myQueue.enQueue(10);
        myQueue.enQueue(20);
        myQueue.enQueue(30);
        myQueue.enQueue(40);
        myQueue.enQueue(50);
        
        myQueue.display();
        myQueue.peak();
        
        System.out.println("After Dequeue Operation:-");
        myQueue.deQueue();
        myQueue.peak();
        myQueue.display();       
    }
}

Output:-

10
  20
  30
  40
  50
  Front index value is: 10
  After Dequeue Operation:-
  Front index value is: 20
  20
  30
  40
  50

Using Queue Interface

The Queue interface, which is part of Java Collections, has two implementations:

1. Queue queue = new LinkedList();
2. Queue queue = new PriorityQueue();

The Queue interface is implemented by two classes: LinkedList and PriorityQueue. We can't make an instance of the Queue because it's an interface. As a result, we create a LinkedList and PriorityQueue instance and attach it to the queue interface.

add(): This method adds a particular element to the queue's end. Because the return type is boolean, it returns true if the element is successfully added and false otherwise.

element(): This method returns the queue's initial entry.

remove(): This function removes the queue's first entry.

poll(): This function is similar to remove(), except if the queue is empty, the poll returns null.

peek() is similar to element(), but the only difference is that element returns null if the queue is empty, whereas the peek method returns null.

Priority Queue Interface

import java.util.*;
public class Main
{
   public static void main(String[] args)
   {
      Queue<Integer> queue = new PriorityQueue<Integer>();
       
      //Adding elements to the Queue
      queue.add(10);
      queue.add(20);
      queue.add(30);
      queue.add(40);
      queue.add(50);
 
      System.out.println("Elements in Queue: "+ queue);

      System.out.println("Removed element: "+ queue.remove());

      System.out.println("Front: "+ queue.element());
       
      System.out.println("poll(): "+ queue.poll());

      System.out.println("peek(): "+ queue.peek());

      System.out.println("Add new element: "+ queue.add(60));

      System.out.println("Elements in Queue: " + queue);
   }
}

Output

Elements in Queue: [10, 20, 30, 40, 50]
Removed element: 10
Front: 20
poll(): 20
peek(): 30
Add new element: true
Elements in Queue: [30, 40, 50, 60]

LinkedList Interface

import java.util.*;

public class Main
{

  public static void main (String[]args)
  {

    Queue < Integer > queue = new LinkedList <> ();

    //Adding elements to the Queue
    queue.add (10);
    queue.add (20);
    queue.add (30);
    queue.add (40);
    queue.add (50);

    System.out.println ("Elements in Queue:" + queue);

    System.out.println ("Removed element: " + queue.remove ());

    System.out.println ("Front: " + queue.element ());

    System.out.println ("poll(): " + queue.poll ());

    System.out.println ("peek(): " + queue.peek ());

    System.out.println ("Add new element: " + queue.add (60));

    System.out.println ("Elements in Queue: " + queue);
  }
}

Output

Elements in Queue:[10, 20, 30, 40, 50]
Removed element: 10
Front: 20
poll(): 20
peek(): 30
Add new element: true
Elements in Queue: [30, 40, 50, 60]

Application of Queue

The following are some of the applications of a queue.

  • Scheduling of CPUs and Disks
  • Interrupt handling in real-time systems.
  • Queues are used in call center phone systems to keep people calling in the order.
  • A queue is used in network equipment such as routers and switches. A mail queue, which is a directory that holds data and controls files for mail messages, is another application of a queue.
  • When numerous programs are running in the main memory, this is called multi-programming. These programs must be arranged, and these multiple programs are organized as queues.

Limitations

There are disadvantages of using Queue data structures and they are as follows:-

  • Insertion and deletion of components from the middle are time-consuming processes.
  • A new element can only be added to a traditional queue once the previous elements have been removed.
  • It takes O(N) time to search for an element.
  • A queue's maximum size must be determined beforehand when implemented using array.

Frequently Asked Questions

Where can you find a queue in real life?

In the real world, here are some examples of queues: a ticket line, an escalator, and a vehicle wash.

What is the distinction between a stack and a queue?

The main distinction between Stack and Queue Data Structures is that Stack uses a LIFO(Last In First Out) data structure whereas Queue uses a FIFO(First In First Out) data structure. 

How many types of queues are there?

There are mainly four types: Simple Queue, Circular Queue, Priority Queue and De-queue(Double-ended queue).

Conclusion

In this article, we have extensively defined a queue and its structure in the Java programming language. Finally, we looked at using arrays and queue interfaces in Java to construct the queue data structure.

We hope this blog has helped you enhance your knowledge regarding queue data structure. You can also consider our Online Coding Courses such as the DSA in PythonC++ DSA CourseDSA in Java Course to give your career an edge over others.

Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Implementation Of Queue in Java using Array and Generics
Next article
FIFO (First-In-First-Out) approach in Programming
Live masterclass