Code Destine

Problem Statement

Design a Queue (FIFO) data structure using Dynamic Array. The Queue data structure will supports the following operations:

1. enqueue(N) :- It insert element N to the back of the queue.
2. dequeue() :- It removes and returns the element from the front of the queue.
3. peek() :- It returns (not remove) the element from the front of the queue.
4. isEmpty() :- It checks whether the queue is empty.
5. size() :- It return the total number of elements.
6. iterator() :- It returns the java iterator object for iterating through the elements of the queue.

Example 

Queue queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);  
queue.peek();  // returns 10
queue.dequeue();   // returns 10
queue.isEmpty(); // returns false

Solution

Dynamic array is an array whose size automatically increased when it gets too full and, its size gets decreased when it is too empty.

We have to implement a dynamic array using an array object provided in java language. For this first create the following three variables, these variables will help us to decide when the size of the array should be increased and when it should be decreased.

1. Initial capacity:- Size of the array during its creation.
2. Increase Factor:- Multiplication factor by which the array size is increased, for example, increase factor 2 means the size of the array is double every time it gets too full.
3. Decrease factor:- It decides when the size of the array should be decreased.

In the context of the queue data structure, the increment and decrement of array size work in the following way:

1. Increase size :- During the enqueue, operation checks if an array is 3/4 (75%) full if yes, then create a new array of size (the current size of array multiply by increase factor) and copy the elements from the old array to a new array.
2. Decrease size :- During the dequeue, operation check if the total number of elements in the array are less than the size of the array/the decrease factor, then create a new array of size (the current size of array multiply by increase factor) and copy the elements from the old array to a new array.

Each operation of the queue will work in the following way:

1. enqueue(N) :- It increase the value of tail variable by 1 and assign the element N at this index.
2. dequeue() :- It increase the value of head variable by 1 and return its value after making it null.
3. peek() :- It returns the value at head + 1 index.
4. isEmpty() :- If the difference of head and tail variable is less than 1, then returns true otherwise returns false.
5. size() :- It returns the difference of head and tail variables.
6. iterator() :- It returns the object of QueueIterator class.

Queue Interface

public interface Queue<T> extends Iterable<T> {

	public void enqueue(T t);
	
	public T dequeue();
	
	public T peek();
	
	public boolean isEmpty();
	
	public int size();
	
}

Queue Implementation

import java.util.Iterator;

public class DynamicArrayQueue<T> implements Queue<T> {

	private T[] arr;
	private int head;
	private int tail;
	
	private final int intialSize = 10; 
	private final int increasefactor = 2; 
	private final int decreasefactor = 4; 
	
	public DynamicArrayQueue() {
		this.arr = (T[])new Object[intialSize];
		this.head = -1;
		this.tail = -1;
	}
	
	@Override
	public void enqueue(T t) {
		if(tail == arr.length-1){
			if(size() >= (this.arr.length*3)/4){
				amortisedArray(increasefactor*this.arr.length);
			}else{
				resetQueueOnFull();
			}
		}
		arr[++tail] = t;
	}
	
	@Override
	public T dequeue() {
		if((tail-head) < 1){
			resetQueueOnEmpty();
		}else{
			T t = arr[++head];
			arr[head] = null;
			if(size() < this.arr.length/decreasefactor && this.arr.length > intialSize){
				amortisedArray(this.arr.length/increasefactor);
			}
			return t;
		}
		return null;
	}
	
	@Override
	public T peek() {
		if((tail-head) < 1){
			resetQueueOnEmpty();
		}else{
			return arr[head+1];
		}
		return null;
	}
	
	@Override
	public boolean isEmpty() {
		return tail-head<1;
	}

	@Override
	public int size() {
		return tail-head;
	}
	
	@Override
	public Iterator<T> iterator() {
		return new QueueIterator<T>(arr,head,tail);
	}
	
	private void resetQueueOnFull(){
		if(!(head == -1 && tail == arr.length-1)){
			int i = 0;
			for(i=head+1; i<=tail;i++){
				arr[i-(head+1)] = arr[i];
			}
			tail = tail-(head+1);
			head = -1;
		}
	}
	
	private void resetQueueOnEmpty(){
		this.head = -1;
		this.tail = -1;
	}
	
	private void amortisedArray(int size){
		T[] newArray = (T[])new Object[size];
		int count = head + 1;
		int i = 0;
		while(count <= tail){
			newArray[i] = this.arr[count];
			i++;
			count++;
		}
		this.arr = newArray;
		tail = tail-(head+1);
		head = -1;
	}
	
	private class QueueIterator<T> implements Iterator<T>{

		private T[] arr;
		private int head;
		private int tail;
		
		public QueueIterator(T[] arr, int head, int tail) {
			super();
			this.head = head;
			this.tail = tail;
			this.arr = arr;
		}

		@Override
		public boolean hasNext() {
			return tail-head>=1;
		}

		@Override
		public T next() {
			if((tail-head) < 1){
				System.out.println("Queue is empty");
			}else{
				return arr[++head];
			}
			return null;
		}		
	}
}

Similar Post

1. Height Checker
2. Relative Ranks
3. Rotate Array

That’s all for Design Queue Using Dynamic Array in Java, If you liked it, please share your thoughts in a comments section and share it with others too.