Back to DSA Course

Queue is a linear data structure somewhat similar to Stack. Unlike Stack, a Queue is open at both ends. One end is always used to insert data(enqueue) and the other end is used to remove data(dequeue).

Properties of Queue

It follows FIFO(First In First Out) method.

For example, Implementation of billing Counter.

Why do we use queues?

As queues follows FIFO method, they are used when we need to work on data-items in exact sequence of their arrival. Every operating system maintains queues of various processes. Priority queues and breadth first traversal of graphs are some examples of queues.

Common Operations of Queue

• Enqueue: Add an element to the end of the queue; O(1)
• Dequeue: Remove an element from the front of the queue; O(1)
• IsEmpty: Check if the queue is empty
• IsFull: Check if the queue is full
• Peek: Get the value of the front of the queue without removing it; O(1)
• Searching for an element in the Queue: O(n)

A Queue is typically implemented with a doubly linked list.

Linear Queue (Array Implementation)

package com.praveen.queue.linearqueue.array;

public class QueueByArray {

	int[] arr;
	int topOfQueue;
	int beginningOfQueue;

	public QueueByArray(int size) {
		this.arr = new int[size];
		this.topOfQueue = -1;
		this.beginningOfQueue = -1;
		System.out.println("Successfully created an empty queue of size: " + size);
	}

	public void enQueue(int value) {
		if (isQueueFull()) {
			System.out.println("Queue overflow error!!");
		} else if (isQueueEmpty()) { // If the queue is empty then we need to initialize beginning index
			beginningOfQueue = 0;
			topOfQueue++;
			arr[topOfQueue] = value;
			System.out.println("Successfully inserted " + value + " in the queue");
		} else { // if the queue already has some elements in it then no need to initialize
					// beginning index
			topOfQueue++;
			arr[topOfQueue] = value;
			System.out.println("Successfully inserted " + value + " in the queue");
		}
		printQueue();
	}

	public void printQueue() {
		if (!isQueueEmpty()) {
			System.out.println("Queue now ...");
			for (int i = beginningOfQueue; i <= topOfQueue; i++) {
				System.out.println(arr[i] + "   ");
			}
			System.out.println();
		} else {
			System.out.println("Queue is empty !");
		}
	}

	public void deQueue() {
		if (isQueueEmpty()) {
			System.out.println("Queue underflow error!!");
		} else {
			System.out.println("Dequeing value from Queue...");
			System.out.println("Dequeued: " + arr[beginningOfQueue] + " from queue");
			beginningOfQueue++;
			if (beginningOfQueue > topOfQueue) { // If last element in the Queue is Dequeued
				beginningOfQueue = topOfQueue = -1;
			}
		}
		printQueue();
		System.out.println();
	}

	public boolean isQueueEmpty() {
		if ((beginningOfQueue == -1) || (beginningOfQueue == arr.length))
			return true;
		else
			return false;
	}

	public boolean isQueueFull() {
		if (topOfQueue == arr.length - 1) {
			return true;
		} else {
			return false;
		}

	}

	public void peekOperation() {
		if (!isQueueEmpty()) {
			System.out.println(arr[beginningOfQueue]);
		} else {
			System.out.println("The queue is empty!!");
		}
	}

	public void deleteQueue() {
		arr = null;
		System.out.println("Queue is successfully deleted !");
	}

}

Drawbacks

• Memory Wastage : The space of the array which is used to store queue elements can never be reused to store the elements of that queue because the elements can only be inserted at rear and elements can be deleted from front, so after the deletion(dequeue) all the space before first can never be filled.
• Array Size : There might be situations in which we may need to extend the queue to insert more elements if we use an array to implement queue, it will be almost impossible to extend the array size, therefore deciding the correct array size is always a problem.

What is Circular Queue?

Dequeue operation causes blanks cells in Linear Queue(Array Implementation) so in order to avoid this, we need to go with Circular Queue.

Circular Queue is also a linear data structure which follows the principal of FIFO but instead of ending the queue at last position, it again starts from the first position after the last, hence making the queue behave like a circular data structure.

Front and Rear move circularly i.e.. Rear = (Rear+1) % size.

Circular Queue(Array Implementation)

package com.praveen.queue.circularqueue.array;

public class CircularQueueByArray {

	int[] arr;
	int topOfQueue;
	int size;
	int start;

	public CircularQueueByArray(int size) {
		this.arr = new int[size];
		this.size = size;
		this.topOfQueue = -1;
		start = -1;
		System.out.println("Successfully created an empty queue of size: " + size);
	}

	public void enQueue(int value) {
		if (arr == null) {
			System.out.println("Array is not yet created. Please create one first.");
		} else if (isQueueFull()) {
			System.out.println("\nQueue overflow error!!");
		} else {
			initializeStartOfArray();
			if (topOfQueue + 1 == size) { // if top is already at last cell of array, then reset it to first cell
				topOfQueue = 0;
			} else {
				topOfQueue++;
			}
			arr[topOfQueue] = value;
			System.out.println("\nSuccessfully inserted " + value + " in the queue");
		}
	}

	public void initializeStartOfArray() {
		if (start == -1) {
			start = 0;
		}
	}

	public void deQueue() {
		if (isQueueEmpty()) {
			System.out.println("Queue underflow error!!");
		} else {
			System.out.println("\n---------------------------------------------");
			System.out.println("Before Dequeue..");
			printArray();
			System.out.println("\nDequeing value from Queue...");
			System.out.println("Dequeued: " + arr[start] + " from queue");
			arr[start] = 0; // initialize the unused cell to 0
			if (start == topOfQueue) { // if there is only 1 element in Queue
				start = topOfQueue = -1;
			} else if (start + 1 == size) { // if start has reached end of array, then start again from 0
				start = 0;
			} else {
				start++;
			}
		}
		System.out.println("After Dequeue..");
		printArray();
		System.out.println("---------------------------------------------");
	}

	public boolean isQueueEmpty() {
		if (topOfQueue == -1)
			return true;
		else
			return false;
	}

	public boolean isQueueFull() {
		if (topOfQueue + 1 == start) { // If we have completed a circle, then we can say that Queue is full
			return true;
		} else if ((start == 0) && (topOfQueue + 1 == size)) { // Trivial case of Queue being full
			return true;
		} else {
			return false;
		}
	}

	public void peekOperation() {
		// if stack is not empty, return the value on top of stack
		if (!isQueueEmpty()) {
			System.out.println("\nPeeking value from queue...");
			System.out.println(arr[start]);
		} else {
			System.out.println("The queue is empty!!");
		}
	}

	public void deleteStack() {
		System.out.println("\n\nDeleting the entire Queue...");
		arr = null;
		System.out.println("Queue is successfully deleted !");
	}

	// Print entire array
	public void printArray() {
		System.out.println("Array now...");
		for (int i = 0; i < size; i++) {
			System.out.print(arr[i] + "  ");
		}
		System.out.println("\nStart = " + start);
		System.out.println("End = " + topOfQueue);
	}

}

Implementation of Queue using List

package com.praveen.queue.list;

import com.praveen.linkedlist.SingleLinkedList;

public class QueueByLinkedList {

	SingleLinkedList list;

	// constructor
	public QueueByLinkedList() {
		list = new SingleLinkedList();
	}

	public void enQueue(int value) {
		if (list.getHead() == null) {
			list.createSingleLinkedList(value);
		} else {
			// push a value on last of queue, update list tail too
			list.insertInLinkedList(value, list.getSize());
		}
	}

	public int deQueue() {
		int value = -1;
		if (isQueueEmpty()) {
			System.out.println("Queue underflow error!!");
		} else {
			value = list.getHead().getValue();
			list.deletionOfNode(0);
		}
		return value;
	}

	public int peek() {
		if (!isQueueEmpty())
			return list.getHead().getValue();
		else {
			System.out.println("The queue is empty!!");
			return -1;
		}
	}

	public boolean isQueueEmpty() {
		if (list.getHead() == null)
			return true;
		else
			return false;
	}

	public void deleteStack() {
		list.setHead(null);
	}

}

When to Use/Avoid Queue

When to Use

• Helps to manage the data in a particular way(FIFO)
• Not easily corrupted(No one can insert the data in middle)

When to Avoid

• Random Access not possible(If we have done some mistake it is costly to rectify)

Applications of Queue

• CPU scheduling, Disk Scheduling
• When data is transferred asynchronously between two processes.The queue is used for synchronization. For example: IO Buffers, pipes, file IO, etc.
• Handling of interrupts in real-time systems.
• Call Center phone systems use Queues to hold people calling them in order.