Queue Data Structure in Java, easy in 5 minutes

The post walks you through all about the Queue data structure in Java, including queue concept and queue implementation using java language. A Queue is a linear structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO). It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket.

Queue Data Structure in Java

In programming terms, putting an item in the queue is called an “enqueue” and removing an item from the queue is called “dequeue”.

Queue Data Structure Specifications

A queue data structure allows the following operations:

  • Enqueue: Add element to end of queue. If the queue is full, then it is said to be an Overflow condition.
  • Dequeue: Remove element from front of queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
  • IsEmpty: Check if queue is empty
  • IsFull: Check if queue is full
  • Peek: Get the value of the front of queue without removing it

How Queue Works

First, please see the below picture to know how Queue works:

Queue Data Structure in Java, Queue operations on dequeue and enqueue

In short, Queue operations follow the below steps:

  1. Two pointers called FRONT and REAR are used to keep track of the first and last elements in the queue.
  2. When initializing the queue, we set the value of FRONT and REAR  to -1.
  3. Enqueue an element, we increase the value of REAR index and place the new element in the position pointed to by REAR . Before enqueing, we check if queue is already full. When enqueing the first element, we set the value of FRONT to 0.
  4. Dequeue an element, we return the value pointed to by FRONT and increase the FRONT index. Before dequeuing, we check if queue is already empty. When dequeing the last element, we reset the values of FRONT and REAR to -1.

Use of Queue:
Queue is used when things don’t have to be processed immediatly. So Queue is used for the following kind of scenarios.

  • When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
  • When data is transferred asynchronously between two processes. Examples include IO Buffers, pipes, file IO, etc.

Implementing Queue Data Structure in Java

Here, we implement a queue using array in java.

The above program print the output below:

Queue Data Structure in Java

Time Complexity: Time complexity of all operations like enqueue(), dequeue(), isFull(), isEmpty(), front() and rear() is O(1) time. Because there is no loop in any of the operations.

That’s all about Queue data structure in Java.

References

Queue Data Structure in Java
Data Structures and Algorithms Tutorial in Java

Please share it if you found this useful
Hide Buttons