STPAR : Street Parade

STPAR : Street Parade

Link for the Problem : STPAR

SOLUTION:

In the above problem, you have to find whether is it possible to arrange the given sequence of number in increasing sorted order or not by using the side lane. As from side lane, the vehicle entering first will leave in the last, so it follows LIFO order which makes it stack.

IMPLEMENTATION:

1.) Initialize a variable j=1;
2.) Now traverse in the array, for the ith element, first push it in the stack.
3.) While top of the stack equals j, Now pop the stack and increase j by 1.
4.) After processing above for every element of the sequence, if there is any element present in the stack, then the answer will be 'no'.
else if stack is empty then the answer will be 'yes'.

CODE:
#include <bits/stdc++.h>
using namespace std;
int main()
{
    while(1)
    {
        int n;
        scanf("%d",&n);
        if(n==0)
        break;
        int a[n],i,k;
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        stack <int> st;
        int f=0,j=1;
        for(i=0;i<n;i++)
        {
            st.push(a[i]);
            while(st.size())
            {
                if(st.top()==j)
                {
                    j++;
                    st.pop();
                }
                else
                break;
            }
        }
        if(st.size()>0)
        printf("no\n");
        else
        printf("yes\n");
    }
    return 0;

}