# Introduction to Queue and Implementation using Linked List

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.

### Subscribe to Let's Talk Algorithms

Get the latest posts delivered right to your inbox