Queue Implementation Using Array

A queue is a linear data structure that follows an order i.e FIFO(First In First Out), where the element which is inserted at the first will come out first.

Unlike Stack, while implementing a queue, an element is inserted from one end and removed from another end.

Basically, there are 4 basic operations that are performed in the queue:

  • Enqueue: Addition of an element to the queue.
  • Dequeue: Removal of an element from the queue.
  • Front: Get the front element from the queue.
  • Display: Print all element of the queue.

In this example, we’ll see how to implement a queue using an array:

1. Java

public class QueueImpl {

	int[] queueArray;

	int front, rear, maxSize, nItems;

	public QueueImpl(int size) {
		this.queueArray = new int[size];
		this.maxSize = size;
		this.front = 0;
		this.rear = -1;
		this.nItems = 0;
	}

	public void insert(int value) {
		if(rear == maxSize - 1) { // if reached end of array while inserting. Set rear to -1 so that insertion can began from First index.
			rear = -1;
		}
		queueArray[rear++] = value;
		nItems++;
	}

	public void retrieve() {
		System.out.println(Arrays.toString(queueArray));
	}

	public int remove() { // remove element from front of the queue.
		int firstElement = queueArray[front];
		front++;
		if(front == maxSize) { // here we reached at last index of array.
			front = 0;
		}
		nItems--;
		return firstElement;
	}

	public int peekFront() {
		return queueArray[front];
	}

	public boolean isEmpty() {
		return (nItems == 0);
	}

	public boolean isFull() {
		return (nItems == maxSize);
	}
}

Performing Operations:

public class QueueApp {

	public static void main(String[] args) {
		QueueImpl impl = new QueueImpl(5);
		impl.insert(1);
		impl.insert(2);
		impl.insert(3);
		impl.insert(4);
		impl.insert(5);
		
		impl.retrieve();
	}
}

Output:

1 2 3 4 5

Queue Time Complexity:

The time complexity of the operations performed on Queue totally depends on how you implemented the Queue. Based on the above implementation below is the worst time complexity.

  • Enqueue: O(1) time
  • Dequeue: O(1) time
  • Display: O(N) time
  • Size: O(1) time.

Complete Java Solutions can be found here: Github Link

The complete list can be found here: Practise Programming Questions