Queue: Given a queue, check if queue can be sorted using stack

Problem Statement:

Given a queue that has first n natural numbers.

You need to check if the queue can be sorted in ascending order using stack.

Return true, if it can be sorted, else return false.

Below are the operations allowed:

Push into the stack
Pop into the stack
Dequeue from queue
Push into the queue

Example:

Input: Q [] = [5, 1, 2, 3, 4]

Output: True

The output is true because, er pop 6 from the queue and push into the stack.

Then pop the elements from the queue and then pop 6 from stack.

Now all the elements are sorted.

Solution Explanation:

As from the question it is clear that it will have first n natural numbers.

Take a temp variable “exp_val” to check the next expected value and initialize to 1.

Now check if the top of the stack or the front of queue is equal to expected value,

if yes, then increment the exp_val to 1 and repeat the above step.

else pop from queue and push into stack

else return false if front of queue is greater than top of the stack.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

bool solution(queue<int> &q)
{

	stack<int> st;
	int req_next=1;

	while(!q.empty())
	{

		if(q.front() == req_next)
		{
			q.pop();
			req_next++;
		}

		else if(!st.empty() && st.top() == req_next)
		{
			st.pop();
			req_next++;
		}
		else
		{
			st.push(q.front());
			q.pop();
		}
	}
	
	while(!st.empty())
	{
		if(st.top() == req_next)
		{
			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(solution(q1))
    	cout<<"True"<<endl;
    else 
    	cout<<"False"<<endl;

	return 0;
}

Output

True