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 occurs 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 to the elements in the queue from both ends of the structure. Now we can implement it using various other data structures like arrays, linked lists, STL of CPP programming.

Learn one of the most powerful and portable programming languages C++ and become eligible to apply for the positions at Google, Microsoft, Facebook, Amazon, etc.

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.

Compile your code in one of the easy-to-use programming languages, JAVA. The course will train you to become the next face of JAVA Developer who will be equipped with the knowledge of Data Structures and Algorithms with the right understanding of the rich API and powerful development tools of programming.

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.

Python Foundation with Data Structures & Algorithms course will train with the core programming concepts with Python. You will become eligible to apply for positions at Google, Microsoft, Facebook, and more. The course is available in the English language.

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 K^th 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();
}

Frequently Asked Questions

Key Takeaways

Queues are data structures that resemble real-life queues and support entry from one end and exit from another end. They have several real-life applications which involve the implementation of a stack using two queues, CPU task scheduling, graph traversals etc.

Data structures pave a way for solving real-life issues and queues are responsible for solving problems that involve the addition of data first followed by later processing of data. One should understand queues before moving on to more complex data structures such as graphs and trees as there are cases when queues are needed for their implementation.

Queues are also an important data structure in view of interview preparations and placement. It is therefore imperative to become an expert with queues, understand what goes underneath the hood and where you can apply your learnings. 

Happy Learning!

By Aniruddha Guin