In this post, we will show you how to implement Java Queue using Array with an example.
A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at another end (front). The first element to be inserted is the first one to be deleted. Hence, it is called the First in First out (FIFO) or Last in Last out (LILO) list.
Queue Concepts
- When an element is inserted in a queue, the concept is called EnQueue.
- When an element is removed from the queue, the concept is called DeQueue.
- DeQueueing an empty queue is called underflow (treat as Exception).
- EnQueuing an element in a full queue is called overflow (treat as Exception).
Queue Operations
Let's list out basic operations associated with queues −
- enqueue() − add (store) an item to the queue.
- dequeue() − remove (access) an item from the queue.
Few more functions are required to make the above-mentioned queue operation efficient. These are −
- peek() − Gets the element at the front of the queue without removing it.
- isFull() − Checks if the queue is full.
- isEmpty() − Checks if the queue is empty.
Java Queue Implementation using Array
Let's create MyQueue generic class and the following content to it:
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.EmptyStackException;
public final class MyQueue {
private static final int DEFAULT_CAPACITY = 10;
private int front; // elements are removed or peeked from the front
private int rear; // elements are added in the rear
private int count; // size of the queue
private int capacity; // capacity of the queue (this is doubled when is exceeded)
private E[] queue; // the array that sits behind the queue
// constructor to initialize the queue
MyQueue() {
// we use Java Reflection since Java doesn't allow us to instantiate a generic array
queue = (E[]) Array.newInstance(
Object[].class.getComponentType(), DEFAULT_CAPACITY);
count = 0; // initially, the size of the queue is 0
front = 0; // the index of the first element is 0
rear = -1; // initially, there is no element in the queue
capacity = DEFAULT_CAPACITY; // initially, the capacity is of 10 elements
}
// add an element 'e' in the queue
public void enqueue(E e) {
// if the queue is full, we double its capacity
if (isFull()) {
ensureCapacity();
}
// adding the element in the rear of the queue
rear = (rear + 1) % capacity;
queue[rear] = e;
// update the size of the queue
count++;
}
// remove and return the front element from the queue
public E dequeue() {
// if the queue is empty we just throw a meaningful exception
if (isEmpty()) {
throw new EmptyStackException();
}
// extract the element from the front
E e = queue[front];
queue[front] = null;
// set the new front
front = (front + 1) % capacity;
// decrease the size of the queue
count--;
return e;
}
// return but not remove the front element in the queue
public E peek() {
// if the queue is empty we just throw a meaningful exception
if (isEmpty()) {
throw new EmptyStackException();
}
return queue[front];
}
// size of the queue
public int size() {
return count;
}
// check if the queue is empty or not
public boolean isEmpty() {
return size() == 0;
}
// check if the queue is full or not
public boolean isFull() {
return size() == capacity;
}
// used internally for doubling the queue capacity
private void ensureCapacity() {
int newSize = queue.length * 2;
queue = Arrays.copyOf(queue, newSize);
// setting the new capacity
capacity = newSize;
}
}
Let's create Main class to test above Queue implementation logic:
public class Main {
public static void main(String[] args) {
MyQueue stack = new MyQueue();
stack.enqueue(25);
stack.enqueue(35);
stack.enqueue(15);
System.out.println("Size: " + stack.size());
System.out.println("Peek: " + stack.peek());
System.out.println("Size: " + stack.size());
System.out.println("Pop: " + stack.dequeue());
System.out.println("Size: " + stack.size());
System.out.println("Peek: " + stack.peek());
System.out.println("Size: " + stack.size());
System.out.println("Push 17");
stack.enqueue(17);
System.out.println("Peek: " + stack.peek());
System.out.println("Size: " + stack.size());
System.out.println("Pop: " + stack.dequeue());
System.out.println("Size: " + stack.size());
System.out.println("Pop: " + stack.dequeue());
System.out.println("Size: " + stack.size());
System.out.println("Push 55");
stack.enqueue(55);
System.out.println("Size: " + stack.size());
System.out.println("Peek: " + stack.peek());
System.out.println("Size: " + stack.size());
System.out.println("Pop: " + stack.dequeue());
System.out.println("Size: " + stack.size());
System.out.println("Pop: " + stack.dequeue());
System.out.println("Size: " + stack.size());
System.out.println("Is empty? " + stack.isEmpty());
}
}
Output:
Size: 3 Peek: 25 Size: 3 Pop: 25 Size: 2 Peek: 35 Size: 2 Push 17 Peek: 35 Size: 3 Pop: 35 Size: 2 Pop: 15 Size: 1 Push 55 Size: 2 Peek: 17 Size: 2 Pop: 17 Size: 1 Pop: 55 Size: 0 Is empty? true