Stack: Check if a queue can be sorted into another queue using a stack

You are given a queue having first n natural numbers.

You need to check if the given queue elements can be arranged in increasing order in another queue using a stack.

Input {5, 1, 2, 3, 4}

Output : Yes

Pop 5 and push into the stack.

Pop all the elements from the given queue and push into another queue and pop 5 from the stack and push into the second queue.

1. Initialize the element = 1

2. If the front element of the queue or the top element of the stack has element

if yes, increment the element by 1 and repeat step 2.

else, pop front of queue and push into the stack. If the popped element is greater than the top of the stack, return No.

Time Complexity: O(n)

Space Complexity: O(n)

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

bool solution(int n, queue<int>& q)
{
    stack<int> st;
    int expected = 1;
    int fnt;

    while (!q.empty()) 
    {
        fnt = q.front();
        q.pop();

        if (fnt == expected)
            expected++;

        else 
        {
            if (st.empty()) 
            {
                st.push(fnt);
            }

            else if (!st.empty() && st.top() < fnt) 
            {
                return false;
            }

            else
                st.push(fnt);
        }

        while (!st.empty() && st.top() == expected) 
        {
            st.pop();
            expected++;
        }
    }

    if (expected - 1 == n && st.empty())
        return true;

    return false;
}

int main()
{
    queue<int> q;
    q.push(5);
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);

    int n = q.size();

    (solution(n, q) ? (cout << "Yes") :
                         (cout << "No"));

    return 0;
}

Output

Yes