Queue Data Structure: How To Start Using In 10 Minutes

A queue is an important data structure that works on the principle of FIFO. FIFO stands for First In First Out. This means that the first elements which is going to get inserted is going to be the first element to get removed. We can imagine a queue as a group of people waiting to get in the cinemas or some shop. The first person who stand in the queue is the person to enter the hall or the shop.

Queues are one of the most useful data structures which are used frequently in computer science. Let us look at the operations that are done on a queue.

Enqueue: The operation which inserts an element into a queue is called enqueue. It inserts an item at the last.
Dequeue: This operation which removes an element from a queue is called dequeue. It removed an items from the front of the queue.
Empty? : This operation return a boolean true or false. It return true if the queue is empty else it gives false.
Full? : This operation as well returns a boolean true or false. It returns true if the queue is full else returns a false.
Peek: This operation gives out the element at a given position.

Implement Queue using Java

We start by creating the main class QueueArray and declare three global variables arr[], front and back with the initial value of -1 and size (here we keep it as 6). This size will define the size of the queue.

public class QueueArray {

	static int size = 6;
	static int arr[] = new int[size];
	static int front = -1, back = -1;

}

Push/ Enqueue an element in queue

public static void enqueue(int element) {
	if(back == size - 1) {
		System.out.println("Queue is full");
	} else {
		back++;
		arr[back] = element;
		if(front == -1) {
			front = 0;
		}
	}
}

Here, in the above method we start by checking if the back pointer is equal to that of the size – 1. This will signify that the queue is full and will print Queue full which is condition when a queue is full. If this condition is not met, we increase the back pointer by 1 and insert an element in the queue at the back position. Along with that if the front pointer is still set as -1, we make it 0, because it should start pointing to the first element of the queue (at the 0th index).

Remove/ Dequeue an element from queue

public static void dequeue() {
	if(front > back || front == -1) {
		System.out.println("Queue is empty");
	} else {
		front++;
	}
}

In the dequeue method first we check if the front pointer is having the value of -1 or it’s value is more the back pointer. If it is the case, we print that the queue is empty. This is known as the Queue Underflow condition. If that is not the case, we simply increase the front pointer by 1. As a result, the top pointer starts to point in the second item in the queue.

Check if queue is empty or full

We check if the queue is empty or full by checking the value of the front and back pointer. If the front pointer is equal to -1 i.e it’s starting value or front value is greater than the back we consider the queue to be empty else if the value of back pointer is equal to the predefined size of queue – 1 (we subtract 1 as index of array starts from 0), we consider it full.

Print the values of a queue

public static void display() {
	System.out.println("Printing the queue");
         if(front == -1) {
		System.out.println("Queue underflow");
		return;
	}
	for(int i=front;i<=back;i++) {
		System.out.println(arr[i]);
	}
}

The above method prints the elements of the queue. For this we start to loop the array from the front pointer and go till back pointer. This prints the elements of the queue.

Final Java Program

public class QueueArray {
	
	static int size = 6;
	static int arr[] = new int[size];
	static int front = -1, back = -1;

	public static void main(String[] args) {
		display();
		System.out.println("Inserting items in queue");
		enqueue(1);
		enqueue(2);
		enqueue(3);
		enqueue(4);
		enqueue(5);
		display();
		System.out.println("Removing elements from queue");
		dequeue();
		dequeue();
		display();
	}
	
	public static void enqueue(int element) {
		if(back == size - 1) {
			System.out.println("Queue is full");
		} else {
			back++;
			arr[back] = element;
			if(front == -1) {
				front = 0;
			}
		}
	}
	
	public static void dequeue() {
		if(front > back || front == -1) {
			System.out.println("Queue is empty");
		} else {
			front++;
		}
	}
	
	public static void display() {
		System.out.println("Printing the queue");
                  if(front == -1) {
			System.out.println("Queue underflow");
			return;
		}
		for(int i=front;i<=back;i++) {
			System.out.println(arr[i]);
		}
	}

}

Output

Printing the queue
Queue underflow
Inserting items in queue
Printing the queue
1
2
3
4
5
Removing elements from queue
Printing the queue
3
4
5

In the above code we introduce the main method to run and execute the queue operation methods. We start the printing the empty queue first, then we push some elements and again print the queue. Again we pop the elements and again print the queue.

Note: We can perfect the code much more by adding the logic to make front and back as -1 if the last item in the queue is dequeued. Try on implementing this logic by self.

Time Complexity of queue

The time complexity of the queue operations (enqueue and dequeue) has the complexity of O(1) in case of enqueue and O(n) in case of dequeue. This is since accessing array elements by index takes constant time. Read more about time complexity and Asymptotic notations here.

Queue Data Structure: How To start using in 10 Minutes