Implementing Queue using array in Java

In the previous post I discussed about java.util.Queue interface in Java and the operations that can be performed on it. This post provides queue implementation using an array, a diagrammatic representation of queue using array, code implementation. It also discusses the time and space complexity of the code implemented, problems with the current approach and the solution for the same.

Prerequisites :

Knowledge of Java, basic data structures, working of array and understanding of time and space complexity.

Check java.util.Queue interface in Java to know about the operations that can be performed on the queue.

Explanation :

In a queue data structure the insertion and deletion is performed at the back and at the front of the queue respectively. It performs these operations in FIFO i.e First In First Out manner.

To implement a queue using an array, create an array of size N. Maintain two variables as pointers i.e front and rear. The front pointer will point to the first element in the array or in other words, it will store the index position of the first element in the array. And the rear pointer will point to the last element in the array or in other words, it will store the index position of the last element stored in the array.

Initially the head and rear both variables will be initialized to -1 indicating that the queue is empty.

Common queue operations :

1. Enqueue operation : This indicates addition of a new element to the queue. The new element is added at the back of the queue. The addition can only be performed when the queue is not full i.e rear < N. If the queue is not full the rear variable is incremented by 1 and the element is added to that index of the array/queue i.e arr[rear].
2. Dequeue operation : This indicates deletion of an element from the queue where the element is deleted from the front end i.e arr[front]. This operation can be performed only when the queue is not empty i.e rear >=0. If the queue is not empty then the element at the front index can be deleted and all the remaining elements have to be shifted to left by one position.
3. Front operation : This operation returns the front element of the queue i.e arr[front].
4. Display all elements : This operation displays all the elements present in the queue from the index front to rear index.

Diagrammatic representation :

Algorithm :

1. Create an array queue of size N.
2. Declare two variables front and rear and initialize them with -1.
3. For the enqueue operation, check if the queue is full i.e rear == N-1. If the queue is full, throw a queue overflow error. If the queue is not full then increment rear variable by 1 and store the element at queue[rear].
4. For the dequeue operation, check if the queue is empty i.e rear == -1. If the queue is empty, throw a queue underflow error. If the queue is not empty, then remove the first element rear[front] and shift remaining elements to the left by 1 position and make the element queue[rear] as 0 indicating that no element is stored at that position and decrement rear by 1.

Code implementation :

public class QueueUsingArray {

	int queue[];
	int N;
	int front, rear;

	QueueUsingArray() {
		N = 5;
		queue = new int[N];
		front = -1;
		rear = -1;

	}

	/* method which inserts a new element to the queue */
	void enqueue(int data) {
		if (isFull()) {
			System.out.println("Queue is full. Cannot insert " + data);

		} else {
			if (rear == -1) { // means inserting first element
				rear++;
				front++;

			} else {
				rear++;

			}
			queue[rear] = data;

			System.out.println("Element enqueued = " + queue[rear]);
		}
	}

	/* method which removes an element from the queue */
	void dequeue() {
		if (isEmpty()) {
			System.out.println("Queue is empty");

		} else if (front == rear) { // means there is only 1 element

			System.out.println("Element dequeued = " + queue[front]);
			front = -1;
			rear = -1;

		} else {
			System.out.println("Element dequeued = " + queue[front]);
			for (int i = 0; i <= rear - 1; i++) {
				queue[i] = queue[i + 1];
			}
			// store 0 at that position to indicate there is no element
			queue[rear] = 0;

			rear--;

		}
	}

	/* method which checks if the queue is full */
	boolean isFull() {
		return rear == N - 1;
	}

	/* method which checks if the queue is empty */
	boolean isEmpty() {
		return rear == -1;
	}

	/* method which displays all the elements of the queue */
	void display() {
		System.out.print("Queue elements are = ");
		for (int i = front; i <= rear; i++) {
			System.out.print(queue[i] + " ");

		}
		System.out.println();
	}

	public static void main(String[] args) {
		QueueUsingArray q = new QueueUsingArray();
		q.enqueue(1);
		q.enqueue(2);
		q.enqueue(3);
		q.enqueue(4);
		q.enqueue(5);
		q.enqueue(6);
		q.dequeue();
		q.dequeue();
		q.dequeue();
		q.enqueue(6);
		q.display();
		q.isEmpty();
		q.isFull();

	}

}

Code output :

Element enqueued = 1
Element enqueued = 2
Element enqueued = 3
Element enqueued = 4
Element enqueued = 5
Queue is full. Cannot insert 6
Element dequeued = 1
Element dequeued = 2
Element dequeued = 3
Element enqueued = 6
Queue elements are = 4 5 6

Time and space complexity :

Time complexity of the enqueue operation is constant time i.e O(1) because the number of operations/steps required to enqueue an element is the same irrespective of the size of the queue. Even if the size of the queue gets large the time remains constant.

Time complexity of the dequeue operation is O(N) i.e linear time, since we need to shift all the elements to the left by 1 position when an element is dequeued from the front of the queue.

Space complexity of the above implemented code is O(N) because we use an array of size = N.

Problems with above implementation :

The dequeue operation requires shifting all the elements to the left. This is not an issue for smaller values of N. But for large values, this operation gives poor performance. Imagine if N has the value of 100000, every dequeue operation will require thousands of shifts.

Solution to the above problem :

Time required for a dequeue operation can be improved by using Circular queue or a linked list as a queue which will be discussed in the next post.

Link to the above code on my github profile, Queue using array.

Thank you for reading. I hope it helped you to learn some useful concept about queue data structure implementation. Your feedback is highly appreciated.