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 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-

blog banner 1
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 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();
}

Frequently Asked Questions

What is the application of queues?

Queues find their application in real life within serving requests such as a printer queue, CPU scheduling and calling systems.

What are queues in data structure?

A queue is a data structure that follows the property of first in first out. It is the interconnection of nodes containing all kinds of data.

What are queue and their types in data structure?

A queue is a data structure that follows the property of first in first out. There are four kinds of queues available – simple queue, circular queue, priority queue and double ended queue.

What is a queue and write the application of queue?

A queue is a data structure that follows the property of first in first out. Queues are applied in places where data has to be stored but not processed immediately. Some examples include – CPU scheduling, printer queue, phone calling system etc.

What is the application of stack and queue?

Stacks and queues are used for multiple purposes. Some of which include – arithmetic expression evaluation, function-call abstraction, M/M/1 queue, load balancing etc.

What are the applications of the priority queue?

Priority queues are used for a lot of computer operations. Dijkstra’s shortest path algorithm, Prim’s algorithm, Huffman code, Heap sort are some of the algorithms which utilise priority queues. Apart from this, priority queues are also utilised in operating system functionalities such as priority scheduling, load balancing and interrupt handling.

How do I start learning DS and algorithms?

After mastering one programming language, the next step is to use that language to implement data structures. Starting from linear data structures, move towards advanced topics but don’t just study topics theoretically. Simultaneous implementation is important. To get a defined path, taking an online course is recommended.

Which language is best for DS and Algo?

Most competitive programmers use C++ because of its efficiency for DSA. That being said, the language is just a medium and any language that you are affluent with is appropriate for you to implement DSA.

How do I prepare for DS and algorithms?

Practicing as many problems as you can find and that too consistently is the key to mastering DSA. Online platforms like CodeStudio, LeetCode, Codeforces have a pool of problems of all types, practicing which will help you master DSA.

How long will it take to learn data structures and algorithms?

On a generic note, mastering DSA will take around 3-4 months. A good foundation is important so do not rush through it, be patient and take your time because the pace of learning is different for every learner.

Is Python good for Data Structures?

Python is considered to be a good language to start with if you are a beginner. Moreover, in terms of speed, there is no better language than Python. In the aspects of speed, convenience and syntax, python is a good language for Data Structures.

Is Python good for algorithms?

Algorithms are not written with the medium of programming languages. They are essentially written in a syntax which is considered to be the closest to Python due to Python’s closeness to the English language.

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