Queue is a special type of data structure, which is designed to hold elements before processing and process elements in a FIFO (first-in-first-out) manner. It’s part of java collections framework. In this tutorial, we will learn Queue implementation in Java using an array.
Basic Queue Functions
A Queue must have the following functions:
enqueue(obj)
– insert element to the queue.dequeue()
– remove and return the least recent item from the queue.isEmpty()
– returns true if the queue is empty, else false.
Queue Implementation in Java
We can implement basic Queue functions using an array.
Here is the complete code to implement a Queue 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 |
package com.journaldev.java; public class MyQueue { public static final int DEFAULT_SIZE = 5; private Object data[]; private int index; public MyQueue() { data = new Object[DEFAULT_SIZE]; } public MyQueue(int size) { data = new Object[size]; } public boolean isEmpty() { return index == 0; } public void enqueue(Object obj) throws Exception { if (index == data.length - 1) { throw new Exception("Queue is full. Dequeue some objects"); } this.data[index] = obj; this.index++; } public Object dequeue() throws Exception { if (isEmpty()) throw new Exception("Queue is empty"); Object obj = this.data[0]; for (int i = 0; i < this.index - 1; i++) { data[i] = data[i + 1]; } this.index--; return obj; } } |
Important Points
- There are two constructors – one to create a Queue with default size, the other one is used to specify the queue size.
- We are using a private integer variable “index” to manage the queue elements.
- We are using an Object array so that we can hold any type of object in the Queue. We can use generics here too but I am avoiding that to keep the program simple.
- If the queue is full, the enqueue() will throw an exception with proper message.
- If the queue is empty and we call the dequeue() function, an exception is raised.
Implementation Limitations
The Queue methods are not synchronized and it’s not thread-safe. There is a chance of data inconsistency if you use this implementation in a multi-threaded environment.
Test Program to Check Queue Implementation
Let’s test our queue implementation with some calls to enqueue() and dequeue() functions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
MyQueue queue = new MyQueue(); queue.enqueue("1"); System.out.println(queue.dequeue()); queue.enqueue("2"); queue.enqueue("3"); queue.enqueue("4"); System.out.println(queue.dequeue()); queue.enqueue("5"); queue.enqueue("6"); // queue.enqueue("7"); // queue.enqueue("8"); |
Output:
1 2 3 |
<span style="color: #008000;"><strong><code>1 2 </code></strong></span> |
If you uncomment the last two lines, the queue will get full and an exception will be raised.
1 2 3 4 |
Exception in thread "main" java.lang.Exception: Queue is full. Dequeue some objects at com.journaldev.java.MyQueue.enqueue(MyQueue.java:25) at com.journaldev.java.MyQueue.main(MyQueue.java:56) |
Conclusion
A Queue is one of the simplest data structures. We can implement it using an array or a list.