# Applications of Queue

#### Data Structures queue

A queue is a linear data structure that supports First-In-First-Out operation.In this article, we'll be discussing following algorithms and problems that can be solved directly by using queues:

Algorithms

1. CPU Scheduling(First-Come-First-Serve)
3. Level Order Traversal of a tree
4. Edmonds Karp Algorithm
5. Dinic's Algorithm
6. Fibonacci Heap

Problems

1. Maximum for each continuous subarray
2. Maximum amount that can be collected by selling spots
3. Odd even level difference

So, let us start with the case of FCFS CPU Scheduling algorithm -

# CPU Scheduling Algorithm(FCFS)

CPU Page replacement algorithm - FCFS(First-Come-First-Serve) is needed to decide which page needs to be replaced in the memory when a new page comes in. In this algorithm, the operating system keeps track of all pages in the memory in a queue. When a page needs to be replaced, the page at the front of the queue is selected for removal(queue follows FIFO,hence element at the front will be the oldest).

Algorithm -

1. Start traversing the pages.
• If a frame holds lesser pages than it's maximum capacity.
1. Insert pages into the set one by one until the size of set reaches capacity or all page requests are processed.
2. Update the pages in the queue to perform FIFO.
3. Increment page fault
• Else
If the current page is present in set, do nothing.
Else
1. Remove the first page from the queue.
2. Replace it with the current page in the string and store current page in the queue.
3. Increment page faults.
1. Return page faults.

Solution
For the sake of simplicity , let us use the queue interface so as to avoid the manual implementation part.

static int FIFO(int pages[], int n, int capacity)
{
//To maintain record of //existing pages
HashSet<Integer> s = new HashSet<>(capacity);
Queue<Integer> indexes = new LinkedList<>() ;   //to implement FIFO
int pf = 0;
for (int i=0; i<n; i++)                        // Start from initial page
{
if (s.size() < capacity)     // Check if more pages can be held in set
{
if (!s.contains(pages[i]))
{
pf++;                                   //Increment page faults
}
}
else                   // Now , since no more pages can be held
{                      //in that set , hence , FIFO
if (!s.contains(pages[i]))     // Check if current page is not
int val = indexes.peek();           //Dequeue the first page
indexes.poll();                  //from the queue
s.remove(val);                       // Remove the indexes page
s.add(pages[i]);                     // insert the current page
pf++;           // Increment page faults
}
}
}
return pf;
}



To-Do-
We can also find the number of page hits. one only needs to maintain a separate count. If the current page is already in the memory then that is counted as Page-hit. Try doing this yourself !

# Breadth First Search (BFS) Algorithm

Breadth first search is a graph traversal algorithm that starts traversing the graph from root node and visits all the neighbouring nodes. Then, it selects the nearest node and visits all the unvisited nodes. This process is carried on recursively until all nodes have been visited.

In this algorithm , we maintain a linear queue of the nodes to maintain the status of nodes in ready state. Following is the detailed BFS Algorithm-
Algorithm
Step 1: Set the status=1(ready state) for each node in G.
Step 2: Insert the first node A and set its status = 2(waiting state).
Step 3: Now, repeat steps 4 and 5 until queue is empty
Step 4: Dequeue a node, process it and set it's status = 3(processed state).
Step 5: Insert all the neighbours of N that are in the ready state(staus=1) and set their status = 2(waiting state)
(END OF LOOP)
Step 6: EXIT

Solution

private LinkedList<Integer> al[]; //Adjacency List for traversal
public int v=5; //number of vertex in graph
void traverse(int s)  //s is the starting vertex
{
//initially consider all the vertices as unvisited
boolean visit[] = new boolean[v];
visit[s]=true; // Mark the current node as visited

while (q.size() != 0)
{
s = q.poll();   // Remove a vertex from queue
System.out.print(s+" ");
Iterator<Integer> i = al[s].listIterator(); //to iterate
while (i.hasNext())
{
int n = i.next(); //neighbouring vertex of dequeued vertex
if (!visit[n])
{
visit[n] = true; //process them
}
}
}
}


This implementation uses adjacency list representation of graphs.

To-Do

We can also traverse a graph by means of adjacency matrix. Try doing this yourself!

# Level Order Traversal of a tree

Level Order Traversal is one of the most used algorithms while dealing problems on trees. In level order traversal, we iterate through all levels of the tree one by one , traversing all the nodes at a specific level in a linear fashion.
Now , there can be two ways of implementing this. A naive approach is to recursively call two functions. One of them traverses all nodes at a given level and the other determines the height of the tree and traverse them level-wise.
However, the expected time-complexity of this method in worst-case is O(n * n). This can be further optimised to linear time complexity by using linear queues.
Let us first have a look at the detailed algorithm we are talking about and then, we'll move on to the implementation part!!!

Algorithm

1. Initialise a linear queue, q and push root of the tree to it's front.
2. Repeat steps 3-4 until queue is not empty.
3. Remove the node at the front of the queue and process it.
4. Push the children of the node to the queue.

Now, let's move on to the implementation part. Before moving on to the solution , try doing this yourself

void print(Node root)
{
if(root==null)
{
return;      //in case root is null , there is no node to traverse.
}
Queue<Node> q = new LinkedList<Node>();  //queue to hold nodes
while(!q.isEmpty())   //loop till queue is empty
{
int size = q.size();  //variable to store size of queue
for(int i=0;i<size;i++)
{
Node temp = q.remove();  //dequeue the first node
System.out.print(temp.data+" ");  //print data
if(temp.left!=null)       //Push it's children to queue
if(temp.right!=null)
}
}
}


To-Do
We can also find the depth of each nodes iteratively using this method.All you need to do is to maintain a separate variable to track changes in levels.Try implementing this yourself!!

# Edmonds Karp Algorithm

This algorithm is used for determining the maximum flow in a flow network.
In graph theory, a flow network is basically a directed graph that connects a Source(S), a Sink(T) and other nodes with edges.Every edge has it's own capacity which is the maximum limit of flow through this edge.

Edmonds-Karp algorithm is an extension to the Ford–Fulkerson algorithm but it is more efficient.
Time Complexity - O(V * E * E)
The only difference between Edmonds-Karp algorithm and Ford-Fulkerson is that it determines the next augmenting path using breadth-first search (bfs). In other words, this algorithm always chooses the shortest possible path for finding the maximum flow.

Implementation

static final int V = 6;
boolean bfs(int graph[][], int s, int t, int parent[])
{
boolean check[] = new boolean[V]; // array to check status
for(int i=0; i<V; ++i)
check[i]=false;   //mark all nodes as unvisited

q.add(s);  //push start/source vertex to queue
check[s] = true; //mark source node as traversed
parent[s]=-1;
while (q.size()!=0)
{
int u = q.poll();  //remove first vertex from queue
for (int v=0; v<V; v++)
{
if (check[v]==false && graph[u][v] > 0)
{
parent[v] = u;
check[v] = true;
}
}
}
return (check[t] == true);//return true once we reach sink
}
// Implement fold fulerson algo
int ff(int graph[][], int s, int t)
{
int u, v;
int Graph[][] = new int[V][V];//Create a residual graph and
for (u = 0; u < V; u++)          //fill it with same capacities
for (v = 0; v < V; v++)       //as original graph
Graph[u][v] = graph[u][v];

int parent[] = new int[V];   //to store path
int max_flow = 0;  // Initally, flow is not present

while (bfs(Graph, s, t, parent)) //if a path exists from source to sink
{
int pathFlow = Integer.MAX_VALUE;//to find minimum residual
for (v=t; v!=s; v=parent[v])     //capacity of edges
{
u = parent[v];
pathFlow = Math.min(pathFlow, Graph[u][v]);
}
for (v=t; v != s; v=parent[v])
{
u = parent[v];
Graph[u][v] -= pathFlow;
Graph[v][u] += pathFlow;
}
max_flow += pathFlow;  //add to overall flow
}
return max_flow;
}


# Dinic's Algorithm

Dinic's Algorithm is another algorithm based on Fold-Fulkerson algorithm which computes the maximum flow in a flow network.

It is more efficient than both Fold-Fulkerson and Edmonds-Karp algorithm.
Time Complexity - O(E * V * V)
Let us have a quick look at the detailed algorithm.

Algorithm

1. Create a residual graph G and fill it with the same capacities as original graph.
2. Do BFS of G to construct a level graph and check if a greater flow is found.
a) If more flow is not possible, then return.
b) Send multiple flows in G using level graph until blocking flow is reached.

Implementation

 static boolean dinicBfs(List<Edge>[] graph, int src, int dest, int[] dist) {
Arrays.fill(dist, -1);
dist[src] = 0;
int[] Q = new int[graph.length];
int sizeQ = 0;
Q[sizeQ++] = src;
for (int i = 0; i < sizeQ; i++) {
int u = Q[i];
for (Edge e : graph[u]) {
if (dist[e.t] < 0 && e.f < e.cap) {
dist[e.t] = dist[u] + 1;
Q[sizeQ++] = e.t;
}
}
}
return dist[dest] >= 0;
}

static int dinicDfs(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
if (u == dest)
return f;
for (; ptr[u] < graph[u].size(); ++ptr[u]) {
Edge e = graph[u].get(ptr[u]);
if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
int df = dinicDfs(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
if (df > 0) {
e.f += df;
graph[e.t].get(e.rev).f -= df;
return df;
}
}
}
return 0;
}

public static int maxFlow(List<Edge>[] graph, int src, int dest) {
int flow = 0;
int[] dist = new int[graph.length];
while (dinicBfs(graph, src, dest, dist)) {
int[] ptr = new int[graph.length];
while (true) {
int df = dinicDfs(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
if (df == 0)
break;
flow += df;
}
}
return flow;
}


# Fibonacci Heap

A fibonacci heap is another implementation of heaps that have min-heap or max-heap property. It uses fibonacci numbers and is used to implement priority queues in efficient running time.

Amortized time complexities of Fibonacci Heap

Operation Time Complexity
Find minimum element Θ(1)
Delete minimum element O(Log n)
Insert element Θ(1)
Decrease key Θ(1)
Merge Θ(1)

Implementation

class FibNode
{   //structure of node
FibNode child, left, right, parent;
int element;
public FibNode(int element)  //constructor for initialising
{
this.right = this;
this.left = this;
this.element = element;
}
}

class FibHeap
{
private FibNode root;  //root node
private int count;
public FibHeap()       //constructor for initialisation
{
root = null;
count = 0;
}

public boolean isEmpty()       //if heap is empty or not
{
return root == null;
}

public void clear()       //clear heap contents
{
root = null;
count = 0;
}

public void insert(int data)  //to insert an element
{
FibNode node = new FibNode(data);  //new node to insert
node.element = data;

if (root != null)
{
node.left = root;
node.right = root.right;
root.right = node;
node.right.left = node;
if (data < root.element)
root = node;
}
else
root = node;
count++;
}
}


# Maximum for each continuous subarray

Given an array and an integer K, find the maximum value for each and every continuous subarray of size k.

Examples :
Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3}, K = 4
Output: 3 4 5 5 5
There can be multiple approaches for this question , let us have a quick look at each of them and analyse their time complexitites.

Approach 1: Naive Approach
We can run two loops. In the outer loop,we will generate all subarrays of size K and in the inner one, we will find the maximum of the current subarray.
Time Complexity- O(N * K)

Approach 2-: Binary Search Tree

• Pick first k elements and create a Self-Balancing Binary Search Tree (BST).
• Run a loop from i = 0 to n – k
1. Print the maximum element from the BST.
2. Delete arr[i] from BST and insert arr[i+k] into the BST.
Time Complexity- O(N * Log k)

Approach 3: Dequeue
We use the concept of sliding window technique here and create a Dequeue, Q of size k to store elements of current window only in such a way that it is greater than all other elements on the left side of itself.in this way, Q is always sorted and the maximum element can be retrieved immediately from the front of the queue.
Time Complexity: O(n)

Solution-

static void printMax(int arr[], int n, int k)
{
// Dequeue to store indexes of elements in every window
int i;
//Process first k elements
for (i = 0; i < k; ++i)
{
// delete smaller elements of previous window
while (!Q.isEmpty() && arr[i] >= arr[Q.peekLast()])
Q.removeLast();
}
// Process other elements
for (; i < n; ++i)
{
System.out.print(arr[Q.peek()] + " "); //greatest element
// delete elements of previous window
while ((!Q.isEmpty()) && Q.peek() <= i - k)
Q.removeFirst();

while ((!Q.isEmpty()) && arr[i] >= arr[Q.peekLast()])
Q.removeLast();
Q.addLast(i);  // Insert current element at the rear of Qi
}
System.out.print(arr[Q.peek()]); // Print greatest element
}


# Maximum amount that can be collected by selling spots

Given an integer N and an array spots[] where N is the number of customers standing to secure their spots for the coming event and seat[i] is the number of vacant spots in the ith row. The task is to find the maximum amount the owner can get by selling them. Price of a spot is equal to the maximum number of empty spots among all the rows.

Example:
Input: seats[] = {1, 2, 4}, N = 3
Output: 9

This problem can be solved by using a priority queue to record the count of empty spots for every row and print the greatest among them.
Algorithm -

1. Initialise a priority queue q.
2. Traverse the input array and insert all the elements in the queue.
3. Initialize two variables sold and ans to store the number of sold tickets and total amount collected.
4. Now, while sold < N and q.top() > 0 , delete the top element from the queue and add top element of the queue to ans.
5. Now, decrement that top value and insert it again to the queue.
6. Repeat these steps until all the spots have been sold.
7. Print ans.

Solution -

 int M=3; //size of input array
static int s[]={1,2,4}; //input array
public static int Amount(int M, int N)
{

// Priority queue to store count of empty spots
PriorityQueue<Integer> q =
new PriorityQueue<Integer>(Collections.reverseOrder());
for (int i = 0; i < M; i++)
{
q.add(s[i]); // Insert every element to q
}

int sold = 0; // To store the total number of spots sold
int ans = 0; // To store the amount collected
while (sold < N && q.peek() > 0)
{
ans = ans + q.peek(); //update the collected amount
int temp = q.peek();
q.poll();
q.add(temp - 1);      //decrement and insert
sold++;              //increment sold
}
return ans;
}


# Odd even level difference

Given a binary tree , we have to compute the difference between sum of nodes at odd and even level.

Example -
Input:

              2
/    \
4      8


Output: -10(2-(4+8))

Approach:
We can use level order traversal of tree to compute this.Initialise two variables for storing odd and even sums. On traversing through each level , we check if it's odd or even and update even or odd sum accordingly.
Time Complexity: O(N), where N is the number of levels.

Solution -

static int dif(Node node)
{
if (node == null)
return 0;
Queue<Node> q = new LinkedList<>();//for level order traversal
int l = 0;    //level
int e = 0, o = 0;  //even and odd sum
while (q.size() != 0) //till queue is not empty
{
int s = q.size();
l++;
while (s > 0) {
Node temp = q.remove();
if (l % 2 == 0)
{
e += temp.data; //even level
}
else
{
o += temp.data; //odd level
}
if (temp.left != null)
{
}
if (temp.right != null)
{
}
s--;
}
}
return (o - e);
}


To-Do-

The snake game available in nokia games serves as the perfect example where queues can be used.
Thegame starts with the snake kept at (0,0) with size = 1 unit.A list of food's positions is given to you. As the snake eats his food, he grows in size by 1 unit.Each food appears one by one on the screen.On eating one food, score gets incremented by 1 unit.
Try implementing this yourself!
Hint
We can use a queue to track the snake positions.

With this article at OpenGenus, you must be having a clear idea of cases where queues serve to be of great importance , so go ahead and use it in your programs. Happy Coding!

#### Shruti Rawal

Android developer || Data Structures and Algorithms enthusiast || Smart India Hackathon 2020 || Student at National Institute of Technology (NIT), Raipur