Check If A Queue Can Be Sorted Into Another Queue Using A Stack

Problem statement

Given a queue having N numbers . Numbers in the queue is a permutation of first N natural numbers (1 to N) . You have to find out whether this queue can be sorted in increasing order in another queue using a single stack following the below constraints :

• Only pop is allowed on the first queue
• Only push is allowed on the second queue
• Push and pop both is allowed on the stack
• Only one stack can be used , and recursion is not allowed

Examples :

Sample input : Queue => {5 , 4 , 1 , 2 , 3}
Sample output: YES
Explanation : push 5 and 4 into the stack from the first queue .
push 1 , 2 , 3 into the second queue .
pop stack elements and push 4 and 5 into the second queue .

Sample input : Queue => {1, 5, 3,4,2}
Sample output: NO

Sample input : Queue => {5 , 1, 3 , 2 , 4}
Sample output: YES

Approach

Given queue is a permutation of first N natural numbers i.e it contains all numbers from 1 to N exactly once . So if it is possible to sort these numbers into another queue then we already know that our second queue will look like {1 , 2 , 3, ….. , N-1 , N} . So we need to push first 1 , then next 2 , next 3 and so on . If we are not able to push numbers in this order , then it is not possible to sort the queue .

If the front of the queue is not the required next number that we want to push into the second queue , then we will push it into the stack temporarily . At the end ,our stack should also be in monotonic decreasing order .

Algorithm for sorting a queue into another queue using a stack

1. Let us first create a req_next variable and initialize it to 1. This req_next variable denotes what is the next number that we require to push into the stack .

2. If the front of the given queue is the same as req_next , pop it from the queue and push it into the second queue and increment the req_next.

3. If the top of the stack is the same as req_next , pop it from the stack and push it into the second queue and increment the req_next.

4. If none of the above conditions is true , then we need to pop the front of the given queue and push into the stack .

5. Keep repeating 2 – 4 until the given queue is empty .

6. Now we will pop each element from the stack

   • If the top of the stack is the same as req_next , pop it from the stack and push it into the second queue and increment the req_next.
   • Else print “No” , because it is not possible to sort the queue into another queue

7. If we have successfully pushed all N elements into the second queue , then print “YES” because we sorted the given queue into another queue using a single stack .

Dry run for the above algorithm

#include <bits/stdc++.h>
using namespace std;

// Check If A Queue Can Be Sorted Into Another Queue Using a Single stack 
bool checkIfAQueueCanBeSorted(queue<int> &q){
	stack<int> st;
	int req_next=1;
	
	// queue<int> q2;
	while(!q.empty()){
		if(q.front() == req_next){
			// q2.push(q.front());
			q.pop();
			req_next++;
		}
		else if(!st.empty() && st.top() == req_next){
			// q2.push(st.top();
			st.pop();
			req_next++;
		}
		else{
			st.push(q.front());
			q.pop();
		}
	}
	
	while(!st.empty()){
		if(st.top() == req_next){
			// q2.push(st.top());
			st.pop();
			req_next++;
		}
		else{
			return false;
		}
	}
	return true;
}

int main() {
    queue<int> q1;
    q1.push(5);
    q1.push(1);
    q1.push(3);
    q1.push(2);
    q1.push(4);
    
   
    if(checkIfAQueueCanBeSorted(q1)){
    	cout<<"YES"<<endl;
    }
    else cout<<"NO"<<endl;
    
    queue<int> q2;
    q2.push(1);
    q2.push(5);
    q2.push(3);
    q2.push(4);
    q2.push(2);
    
    
    if(checkIfAQueueCanBeSorted(q2)){
    	cout<<"YES"<<endl;
    }
    else cout<<"NO"<<endl;
    
    
	return 0;
}

Time complexity : O(N)
Space complexity : O(N)

This article tried to discuss How to Check if a queue can be sorted into another queue using a stack. Hope this blog helps you understand and solve the problem. To practice more problems you can check out at Prepbytes.