Queue Data Structure and its applications

Queue Data Structure and its applications
Queue Data Structure and its applications

A queue is an abstract data type generally used in the same way as the name suggests.

In Queue the insertion of elements occur at the rear end and deletion occurs at the front end, works in (FIFO) manner.

Inserting in the Queue in the rear end is known as Enqueue and Deleting from the Queue from the front end is called Deque. Queue supports access of the elements in the queue from both the ends of the structure. Now we can implement it using various other data structures like arrays, linked list, STL of CPP programming.

Let us first see the linked-list implementation:

Code:

#include <iostream>

using namespace std;
struct listnode {
int data;
listnode *next;
};
struct Queue{
struct listnode *front;
struct listnode *rear;
};
//creating a new empty queue
struct Queue *CreateQueue{
Queue *Q;
listnode *temp;
Q = new Queue;
temp = new listnode;
Q->front = Q->rear = NULL;
return Q;
}
//return 0 if the queue is not empty else returns 1
int isEmpty(Queue *Q){
return (Q->front() == NULL);
}
//inserting a new data in the queue
void EnQueue(Queue *Q,int data){
struct listnode *newNode = new listnode;
newNode->data = data;
newNode->next = NULL;
if(Q->rear)Q->rear->next = newNode;
Q->rear = newNode;
if(Q->front == NULL)
Q->front = Q->rear;
}
int DeQueue(Queue *Q){
int data = 0;
listnode *temp ;
temp = Q->front;
data = temp->data;
Q->front = Q->front->front;
free(temp); //freeing the temporary variable
return data;
}

Applications of Queue:

Implementation of a stack using two queues.

One of it is used to store the elements and other is used to store the elements in reverse order temporarily.

Let us see the algorithm of the above:

//Push – check whether queue Q1 is empty or not if Q 1is empty then EnQueue the element into the Q2 otherwise EnQueue into Q1.
//Pop- Transfer n-1 elements into the other Queue and delete last from queue for performing pop operation.
->If queue Q1 is not empty then transfer n-1 elements from Q1 to Q2 and then DeQueue the last element from Q1.
->If Q2 is not empty the transfer n-1 elements from Q2 to Q1 and dequeue last element Q2.
Let us see the code implementation-

class MyStack {
public:
/** Initialise your data structure here. */
MyStack() {

}
queue<int> q1;
/** Push element x onto stack. */

void push(int x) {
q1.push(x);
}

/** Removes the element on top of the stack and returns that element. */
int pop() {
int len = q1.size();
for(int i = 0; i < len – 1; i++) {
int tmp = q1.front();
q1.pop();
q1.push(tmp);
}
int res = q1.front();
q1.pop();

return res;

}

/** Get the top element. */
int top() {
return q1.back();
}

/** Returns whether the stack is empty. */
bool empty() {
return q1.empty();
}
};

Now let us see another use of it in CPU task Scheduling. The problem statement is as follows:

Given a character’s array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

int leastInterval(vector& tasks, int n) {

    int timeElapsed = 0;
    priority_queue<pair<int, int>> pq;
    queue<pair<int, int>> wait;
    vector<int> freq(26,0);

    for(char ch : tasks)
        freq[ch - 'A']++;
    for(int i=0; i<26; i++)
        if(freq[i] > 0)
            pq.push({freq[i],0});

    while(!pq.empty() || wait.size() != 0)
    {
        if(!pq.empty())
        {
            pair<int,int> curr = pq.top();
            pq.pop();
            if(--curr.first > 0)
            {
                curr.second = timeElapsed + n;
                wait.push(curr);
            }
        }

        while(wait.size() != 0 && wait.front().second == timeElapsed)
        {
            pair<int, int> canChoose = wait.front();
            wait.pop();
            canChoose.second = 0;
            pq.push(canChoose);
        }

        timeElapsed++;
    }
    return timeElapsed;
}

Another variant of the queue is Deque i.e. Doubly Ended Queue which supports accessing and operations on both the sides of the data structure. Insertion and deletion can be done on both the ends of it. Let us see the usage of deque:

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

vector maxSlidingWindow(vector& nums, int k) {
int i = 0;
int n = nums.size();
deque dq; //dq is the deque using stl
vector v;
for(;i<k;i++){
while(!dq.empty() && nums[dq.back()] <= nums[i])
dq.pop_back();
dq.push_back(i);
}
for(;i<n;i++){
v.push_back(nums[dq.front()]);
while(!dq.empty() && dq.front() <= (i-k))
dq.pop_front();
while(!dq.empty() && nums[dq.back()]<=nums[i])
dq.pop_back();
dq.push_back(i);
}
v.push_back(nums[dq.front()]);
return v;
}

We also use queue in the Graph traversal (BFS):

Let us see how:

#include <bits/stdc++.h>

using namespace std;
struct Graph {
int V;
int E;
int** Adj;
};
struct Graph createAdjMatrix(int V,int E) { struct Graph G = new Graph;
G->V = V;
G->E = E;
G->Adj = new int*[G->V];
for(int i = 0;iV;i++)
{
G->Adj[i] = new int[G->V];
for(int j = 0;jV;j++)
G->Adj[i][j] = 0;
}
for(int i = 0;iE;i++)
{
int u,v;
cin>>u>>v;

    G->Adj[u][v] = 1;
    G->Adj[v][u] = 1;
}
return G;    

}
void BFS(struct Graph* G,int u,bool* visited){
queue q;
q.push(u);
visited[u] = true;

while(!q.empty()){
    int currentVertex = q.front();
    q.pop();
    cout<<currentVertex<<" ";

    for(int i = 0;i<G->V;i++)
    {
        if(i==currentVertex)
            continue;
        if(!visited[i] && G->Adj[currentVertex][i])
        {
            q.push(i);
            visited[i] = true;
        }
    }
}

}
void BFSutil(struct Graph* G)
{
bool* visited = new bool[G->V];
for(int i = 0;iV;i++)
visited[i] = false;

for(int i = 0;i<G->V;i++)
    if(!visited[i])
        BFS(G,i,visited);

}
int main() {
int V, E;
cin >> V >> E;
struct Graph *G = createAdjMatrix(V,E);

BFSutil(G);

return 0;
}

Another variant of it is a priority queue. It is widely used in complex problems as it provides some features in very less time. This is a type of Queue where the data is inserted in order of some condition like we need to get the minimum of a range of numbers in constant time from a stream of data, hence, in this case, the data being inserted is inserted in such a way that the front always contains the current minimum from the stream of data. This is also called minheap and can be constructed to store maximum also along with customised conditions which makes it very popular.

Let us see a problem statement:

A string S of lowercase letters is given. Then, we may make any number of moves. In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string. Return the lexicographically smallest string we could have after any number of moves.

Let us see the use:

It’s a very famous problem of kth smallest number:

Given an array of intervals arr[] of size N, the task is to find the Kth largest element among all the elements within the intervals of the given array.

Let us see the implementation:

bool operator()(const int & a, const int & b)
{
return a>b;
}

};
class Solution {
public:
int findKthLargest(vector& nums, int k) {
priority_queue,compare>queue;
for(int i=0;iqueue.top()){
queue.pop();
queue.push(nums[i]);
}
}
return queue.top();
}

Hope this article helps aspiring programmers. To read more about Data Structures, click here.

By Aniruddha Guin