Queue is a linear datastructure that stores elements with first in first out(FIFO) ordering. That is, the element which gets added to the queue leaves before all the elements added after it.

The most typical example is a real world queue, where you line to get into a public transit or at a movie theater, people get out of the queue prior to all the others who enter after them.

Queue is one of the most used data structure in computer science and is used in various operations or algorithms like,

• CPU Scheduling Algorithms
• Tree Traversals
• Process Synchronization or Message Delivery Systems

Most of the modern day systems communicate with each other using message queues where one system enqueue's or inserts the message to the queue and other system listens to it and deque's the message. There are various implementations of this type like Apache Kafka, Rabbit MQ, IBM MQ etc.

Queue data structure provides the following methods,

• Enqueue
  Adds a element to the rear of the queue
• Deque
  Removes the element at the front of the queue
• isEmpty
  Returns true if queue is empty or false if it's not
• Front
  Returns the front element of the queue
• Rear
  Returns the rear element of the queue.

Implementation

A queue is typically implemented using an array or linked list. When you use an array, the elements has to be moved during enqueue or deque operations to make room for the new elements which can be expensive.

Ideally we will need a constant operation time for inserting and deleting which can be acheived by using a linked list with references available to head and end of the tail.

Using a linked list, we will use the below psuedo code for various queue operations,

Psuedo Code

• Enqueue

  if tail is null
      create new node, assign head and tail to it
  else
      create a new node, assign its next to tail
      assign tail to the new node
  

• Deque

  if head is null
      return null
  else
      store the head value in a temp
      assign head to it's next
      return temp value
  

• isEmpty

    return if head is null

• Front

    if head is null
       return null
    else
        return head's value

• Rear

    if rear is null
       return null
    else
        return rear's value

Below is the full java implementation of queue using linkedlist,

/*
 * Author: Venkatesh,Thallam
 * 
 * Queue data structure implementation using single linked list
 */
 
/*
 * Node Definition for the underlying linked list we use to implement stack
 * */
class Node {
	int val;
	Node next;

	Node(int val) {
		this.val = val;
	}
}

public class QueueImplementation {

	Node head, tail;

	QueueImplementation() {
		head = null;
		tail = null;
	}

	public static void main(String[] args) {
		QueueImplementation queue = new QueueImplementation();
		queue.enqueue(10);
		queue.enqueue(15);
		queue.enqueue(25);
		queue.dequeue();
		System.out.println("queue front is " + queue.front());
		System.out.println("queue rear is " + queue.rear());
		System.out.println("queue size is " + queue.size());
		queue.dequeue();
		queue.dequeue();
		System.out.println("queue size is " + queue.size());
	}

	/*
	 * Adds an element to the rear of the queue
	 */
	public void enqueue(int val) {
		if (tail == null) {
			head = tail = new Node(val);
		} else {
			Node newnode = new Node(val);
			tail.next = newnode;
			tail = newnode;
		}
	}

	/*
	 * Removes an element at the front of the queue and returns the element
	 */
	public Integer dequeue() {
		if (head != null) {
			head = head.next;
		}
		return null;
	}

	/*
	 * Checks if the queue is empty or has elements.
	 */
	public boolean isEmpty() {
		return head == null;
	}

	/*
	 * Returns the number of elements of the queue
	 */
	public int size() {
		int count = 0;
		Node temp = head;
		while (temp != null) {
			count++;
			temp = temp.next;
		}
		return count;
	}

	/*
	 * Returns the front element of the queue
	 */
	public Integer front() {
		if (head != null)
			return head.val;
		else
			return null;
	}

	/*
	 * Returns the rear element of the queue.
	 */
	public Integer rear() {
		if (tail != null)
			return tail.val;
		else
			return null;
	}

}

Time Complexity

The time complexity for each of the queue operations is below,

• Enqueue - O(1)
• Deque - O(1)
• isEmpty - O(1)
• Front - O(1)
• Rear - O(1)
• Size - O(n), since this requires checking all values of stack.