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.
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:
In short, Queue operations follow the below steps:
- Two pointers called FRONT and REAR are used to keep track of the first and last elements in the queue.
- When initializing the queue, we set the value of FRONT and REAR to -1.
- 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.
- 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
// A class to define a Queue class Queue { int front, rear, size; int capacity; int array[]; public Queue(int capacity) { this.capacity = capacity; this.size = 0; this.front = -1; this.rear = capacity - 1; array = new int[this.capacity]; } // Queue is full? boolean isFull(Queue queue) { return (queue.size == queue.capacity); } // Queue is empty? boolean isEmpty(Queue queue){ return (queue.size == 0); } // Add an item to the queue.It changes rear and size void enqueue( int item) { if (isFull(this)) return; this.rear = (this.rear + 1)%this.capacity; this.array[this.rear] = item; this.size = this.size + 1; if (this.front == -1) this.front = 0; System.out.println(item+ " enqueued to queue"); } // Remove an item from queue. It changes front and size int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.array[this.front]; this.array[this.front] = 0;//remove item from array this.front = (this.front + 1)%this.capacity; this.size = this.size - 1; return item; } // Get front of queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.array[this.front]; } // Get rear of queue int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.array[this.rear]; } // Display the queue public String toString(){ StringBuffer buf = new StringBuffer(); for (int item: array){ if (item !=0){ buf.append(item); buf.append(","); } } return buf.toString(); } } // Main class public class QueueTest { public static void main(String[] args) { Queue queue = new Queue(100); queue.enqueue(5); System.out.println(queue.toString()); queue.enqueue(10); System.out.println(queue.toString()); queue.enqueue(20); System.out.println(queue.toString()); queue.enqueue(40); System.out.println(queue.toString()); System.out.println("\n"); System.out.println(queue.dequeue() + " dequeued from queue"); System.out.println(queue.dequeue() + " dequeued from queue"); System.out.println("Front item is " + queue.front()); System.out.println("Rear item is " + queue.rear()); System.out.println(queue.toString()); } } |
The above program print the output below:
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
