Verifique si todos los elementos de la array están presentes en una pila dada o no

Dada una pila de enteros S y una array de enteros arr[] , la tarea es verificar si todos los elementos de la array están presentes en la pila o no.

Ejemplos:

Entrada: S = {10, 20, 30, 40, 50}, arr[] = {20, 30}
Salida: Sí
Explicación:
Los elementos 20 y 30 están presentes en la pila.

Entrada: S = {50, 60}, arr[] = {60, 50}
Salida: Sí
Explicación:
Los elementos 50 y 60 están presentes en la pila.

Enfoque: La idea es mantener la frecuencia de los elementos de la array en un Hashmap . Ahora, mientras la pila no esté vacía, siga extrayendo los elementos de la pila y reduzca la frecuencia de los elementos del Hashmap . Finalmente, cuando la pila esté vacía, verifique que la frecuencia de cada elemento en el mapa hash sea cero o no. Si se encuentra que es cierto, escriba Sí. De lo contrario, imprima No.

A continuación se muestra la implementación del enfoque anterior:

// C++ program of the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to check if all array
// elements is present in the stack
bool checkArrInStack(stack<int>s, int arr[],
                                  int n)
{
    map<int, int>freq;
     
    // Store the frequency
    // of array elements
    for(int i = 0; i < n; i++)
        freq[arr[i]]++;
         
    // Loop while the elements in the
    // stack is not empty
    while (!s.empty())
    {
        int poppedEle = s.top();
        s.pop();
         
        // Condition to check if the
        // element is present in the stack
        if (freq[poppedEle])
            freq[poppedEle] -= 1;
    }
    if (freq.size() == 0)
        return 0;
         
    return 1;
}
 
// Driver code
int main()
{
    stack<int>s;
    s.push(10);
    s.push(20);
    s.push(30);
    s.push(40);
    s.push(50);
     
    int arr[] = {20, 30};
     
    int n = sizeof arr / sizeof arr[0];
     
    if (checkArrInStack(s, arr, n))
        cout << "YES\n";
    else
        cout << "NO\n";
}
 
// This code is contributed by Stream_Cipher

// Java program of
// the above approach
import java.util.*;
class GFG{
 
// Function to check if all array
// elements is present in the stack
static boolean checkArrInStack(Stack<Integer>s,
                               int arr[], int n)
{
  HashMap<Integer,
          Integer>freq = new HashMap<Integer,
                                     Integer>();
   
  // Store the frequency
  // of array elements
  for(int i = 0; i < n; i++)
    if(freq.containsKey(arr[i]))
      freq.put(arr[i], freq.get(arr[i]) + 1);
  else
    freq.put(arr[i], 1);
 
  // Loop while the elements in the
  // stack is not empty
  while (!s.isEmpty())
  {
    int poppedEle = s.peek();
    s.pop();
 
    // Condition to check if the
    // element is present in the stack
    if (freq.containsKey(poppedEle))
      freq.put(poppedEle, freq.get(poppedEle) - 1);
  }
  if (freq.size() == 0)
    return false;
  return true;
}
 
// Driver code
public static void main(String[] args)
{
  Stack<Integer> s = new Stack<Integer>();
  s.add(10);
  s.add(20);
  s.add(30);
  s.add(40);
  s.add(50);
 
  int arr[] = {20, 30};
  int n = arr.length;
 
  if (checkArrInStack(s, arr, n))
    System.out.print("YES\n");
  else
    System.out.print("NO\n");
}
}
 
// This code is contributed by 29AjayKumar

# Python program of
# the above approach
 
# Function to check if all array
# elements is present in the stack
def checkArrInStack(s, arr):
  freq = {}
   
  # Store the frequency
  # of array elements
  for ele in arr:
    freq[ele] = freq.get(ele, 0) + 1
   
  # Loop while the elements in the
  # stack is not empty
  while s:
    poppedEle = s.pop()
     
    # Condition to check if the
    # element is present in the stack
    if poppedEle in freq:
      freq[poppedEle] -= 1
       
      if not freq[poppedEle]:
        del freq[poppedEle]
  if not freq:
    return True
  return False
 
# Driver Code
if __name__ == "__main__":
  s = [10, 20, 30, 40, 50]
  arr = [20, 30]
   
  if checkArrInStack(s, arr):
    print("YES")
  else:
    print("NO")
      

// C# program of
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to check if all array
// elements is present in the stack
static bool checkArrInStack(Stack<int>s,
                            int []arr, int n)
{
  Dictionary<int,
             int>freq = new Dictionary<int,
                                       int>();
   
  // Store the frequency
  // of array elements
  for(int i = 0; i < n; i++)
    if(freq.ContainsKey(arr[i]))
      freq[arr[i]] = freq[arr[i]] + 1;
  else
    freq.Add(arr[i], 1);
 
  // Loop while the elements in the
  // stack is not empty
  while (s.Count != 0)
  {
    int poppedEle = s.Peek();
    s.Pop();
 
    // Condition to check if the
    // element is present in the stack
    if (freq.ContainsKey(poppedEle))
      freq[poppedEle] = freq[poppedEle] - 1;
  }
  if (freq.Count == 0)
    return false;
  return true;
}
 
// Driver code
public static void Main(String[] args)
{
  Stack<int> s = new Stack<int>();
  s.Push(10);
  s.Push(20);
  s.Push(30);
  s.Push(40);
  s.Push(50);
  int []arr = {20, 30};
  int n = arr.Length;
 
  if (checkArrInStack(s, arr, n))
    Console.Write("YES\n");
  else
    Console.Write("NO\n");
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program of the above approach
 
// Function to check if all array
// elements is present in the stack
function checkArrInStack(s, arr, n)
{
    var freq = new Map();
     
    // Store the frequency
    // of array elements
    for(var i = 0; i < n; i++)
    {
        if(freq.has(arr[i]))
            freq.set(arr[i], freq.get(arr[i])+1)
        else   
            freq.set(arr[i], 1)
    }
         
    // Loop while the elements in the
    // stack is not empty
    while (s.length!=0)
    {
        var poppedEle = s[s.length-1];
        s.pop();
         
        // Condition to check if the
        // element is present in the stack
        if (freq.has(poppedEle))
            freq.set(poppedEle, freq.get(poppedEle)-1);
    }
    if (freq.size == 0)
        return 0;
         
    return 1;
}
 
// Driver code
var s = [];
s.push(10);
s.push(20);
s.push(30);
s.push(40);
s.push(50);
 
var arr = [20, 30];
 
var n = arr.length;
 
if (checkArrInStack(s, arr, n))
    document.write( "YES");
else
    document.write( "NO");
 
 
 
</script>

YES

Complejidad temporal: O(N)
Espacio auxiliar: O(N)