Stacks: Validate stack operations

Problem Statement:

You are given 2 sequence of operations, push and pop.

You need to return true if it is result of a sequence of push and pop operations on an initially empty stack

Example

Input: push = [1,2,3,4,5], pop = [4,5,3,2,1]
Output: True

push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Solution

The solution is simple.

We will use stack to solve the problem.

We take an empty stack.
Then push the elements from the push array one by one.
Then each time, we pop out of the top element from stack if it is same as the current one of popped;
In the end, we we’ll check if stack is empty.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 

using namespace std;

bool validate_stack_sequences(vector<int>& pushed, vector<int>& popped) 
{
    stack<int> stack;
    int i = 0;
    for (int x : pushed) {
        stack.push(x);
        while (stack.size() && stack.top() == popped[i]) {
            stack.pop();
            i++;
        }
    }
    return stack.size() == 0;
}

int main()
{
    vector<int> push = {1,2,3,4,5};
    vector<int> pop = {4,5,3,2,1};

    if(validate_stack_sequences(push, pop))
    {
        cout<<"True"<<endl;
    } else {
        cout<<"False"<<endl;
    }

    return 0;
}

Output:

True