Compruebe si las secuencias push y pop dadas de Stack son válidas o no

Dadas las secuencias push[] y pop[] con valores distintos. La tarea es verificar si esto podría haber sido el resultado de una secuencia de operaciones de inserción y extracción en una pila inicialmente vacía. Devuelve «Verdadero» si de lo contrario devuelve «Falso».
Ejemplos: 
 

Input: pushed = { 1, 2, 3, 4, 5 }, popped = { 4, 5, 3, 2, 1 }
Output: True
Following sequence can be performed:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Input: pushed = { 1, 2, 3, 4, 5 }, popped = { 4, 3, 5, 1, 2 }
Output: False
1 can't be popped before 2.

Enfoque: si el elemento X ha sido empujado a la pila, verifique si el elemento superior en la secuencia pop[] es X o no. Si es X, ábralo ahora mismo; de lo contrario, se cambiará la parte superior de la secuencia push[] y las secuencias no serán válidas. Entonces, de manera similar, haga lo mismo para todos los elementos y verifique si la pila está vacía o no en el último. Si está vacío, imprima Verdadero ; de lo contrario, imprima Falso .
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of above approach
#include <iostream>
#include <stack>
 
using namespace std;
 
// Function to check validity of stack sequence
bool validateStackSequence(int pushed[], int popped[], int len){
     
    // maintain count of popped elements
    int j = 0;
     
    // an empty stack
    stack <int> st;
    for(int i = 0; i < len; i++){
        st.push(pushed[i]);
         
        // check if appended value is next to be popped out
        while (!st.empty() && j < len && st.top() == popped[j]){
            st.pop();
            j++;
        }
    }
     
    return j == len;
}
 
// Driver code
int main()
{
   int pushed[] = {1, 2, 3, 4, 5};
   int popped[] = {4, 5, 3, 2, 1};
   int len = sizeof(pushed)/sizeof(pushed[0]);
    
   cout << (validateStackSequence(pushed, popped, len) ? "True" : "False");
    
   return 0;
}
 
// This code is contributed by Rituraj Jain

// Java program for above implementation
import java.util.*;
 
class GfG
{
 
    // Function to check validity of stack sequence
    static boolean validateStackSequence(int pushed[],
                                        int popped[], int len)
    {
 
        // maintain count of popped elements
        int j = 0;
 
        // an empty stack
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < len; i++)
        {
            st.push(pushed[i]);
 
            // check if appended value
            // is next to be popped out
            while (!st.empty() && j < len &&
                    st.peek() == popped[j])
            {
                st.pop();
                j++;
            }
        }
 
        return j == len;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int pushed[] = {1, 2, 3, 4, 5};
        int popped[] = {4, 5, 3, 2, 1};
        int len = pushed.length;
 
        System.out.println((validateStackSequence(pushed, popped, len) ? "True" : "False"));
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Function to check validity of stack sequence
def validateStackSequence(pushed, popped):
    # maintain count of popped elements
    j = 0
 
    # an empty stack
    stack = []
 
    for x in pushed:
        stack.append(x)
 
        # check if appended value is next to be popped out
        while stack and j < len(popped) and stack[-1] == popped[j]:
            stack.pop()
            j = j + 1
 
    return j == len(popped)
 
 
# Driver code
pushed = [1, 2, 3, 4, 5]
popped = [4, 5, 3, 2, 1]
print(validateStackSequence(pushed, popped))

// C# program for above implementation
using System;
using System.Collections.Generic;
 
class GfG
{
 
    // Function to check validity of stack sequence
    static bool validateStackSequence(int []pushed,
                                        int []popped, int len)
    {
 
        // maintain count of popped elements
        int j = 0;
 
        // an empty stack
        Stack<int> st = new Stack<int>();
        for (int i = 0; i < len; i++)
        {
            st.Push(pushed[i]);
 
            // check if appended value
            // is next to be popped out
            while (st.Count != 0 && j < len &&
                    st.Peek() == popped[j])
            {
                st.Pop();
                j++;
            }
        }
 
        return j == len;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []pushed = {1, 2, 3, 4, 5};
        int []popped = {4, 5, 3, 2, 1};
        int len = pushed.Length;
 
        Console.WriteLine((validateStackSequence(pushed,
                        popped, len) ? "True" : "False"));
    }
}
 
// This code contributed by Rajput-Ji

<?php
// PHP implementation of above approach
 
// Function to check validity of stack sequence
function validateStackSequence($pushed, $popped, $len)
{
     
    // maintain count of popped elements
    $j = 0;
     
    // an empty stack
    $st = array();
    for($i = 0; $i < $len; $i++)
    {
        array_push($st, $pushed[$i]);
         
        // check if appended value is next
        // to be popped out
        while (!empty($st) && $j < $len &&
            $st[count($st) - 1] == $popped[$j])
        {
            array_pop($st);
            $j++;
        }
    }
     
    return $j == $len;
}
 
// Driver code
$pushed = array(1, 2, 3, 4, 5);
$popped = array(4, 5, 3, 2, 1);
$len = count($pushed);
     
echo (validateStackSequence($pushed,
                   $popped, $len) ? "True" : "False");
     
// This code is contributed by mits
?>

<script>
 
// Javascript implementation of above approach
 
function validateStackSequence( pushed, popped, len)
{
     
    // maintain count of popped elements
    var j = 0;
     
    // an empty stack
    var st=[];
    for(var i = 0; i < len; i++){
        st.push(pushed[i]);
         
        // check if appended value is next
        // to be popped out
        while (!st.length==0 && j < len &&
        st[st.length-1] == popped[j])
        {
            st.pop();
            j++;
        }
    }
     
    return j == len;
}
 
var pushed = [1, 2, 3, 4, 5];
   var popped = [4, 5, 3, 2, 1];
   var len = pushed.length;
    
  document.write( (validateStackSequence(pushed, popped, len)
  ? "True" : "False"));
 
 
// This code is contributed by SoumikMondal
 
</script>

True

Complejidad de tiempo: O(N), donde N es el tamaño de la pila.