What is a Queue?
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.