# Check if stack contains given array element present or not

The problem is to check whether a stack contains all the elements present in a given array or not. We are given a stack of integers and an array of integers. The task is to determine if all the elements of the array are present in the stack.

## Problem Statement

Given a stack `s` and an array `arr`, the task is to check if all the elements of the array `arr` are present in the stack `s`.

## Example

Consider the following stack and arrays:

``````Stack s:   5 3 7 10 8 1
Array arr1:  1 7 3
Array arr2:  10 15 5 0
``````

For `arr1`, all the elements (1, 7, and 3) are present in the stack `s`, so the output will be "Array element exists in Stack".

For `arr2`, some elements (10 and 5) are present in the stack `s`, but others (15 and 0) are not, so the output will be "Array element are not exists in Stack".

## Idea to Solve the Problem

To check if all the elements of the given array are present in the stack, we can use a HashSet to keep track of the elements present in the array. We will iterate through the array and add all its elements to the HashSet. Then, we will iterate through the stack, and for each element in the stack, we will check if it is present in the HashSet. If it is present, we will remove it from the HashSet. After iterating through the stack, if the HashSet becomes empty, it means all the elements of the array are present in the stack; otherwise, some elements are missing.

## Pseudocode

``````Function isContainsElement(s, arr, n):
Create an empty HashSet called record
Create an empty stack called temp
For i = 0 to n-1:
While s is not empty:
Get the top element of s and store it in auxiliary
If auxiliary is in record:
Remove auxiliary from record
Push auxiliary into temp
Pop the top element from s
While temp is not empty:
Get the top element of temp and store it in auxiliary
Push auxiliary into s
Pop the top element from temp
Display the elements of arr
If record is empty:
Display "Array element exists in Stack"
Else:
Display "Array element are not exists in Stack"
``````

## Algorithm

1. Create a class called `Finding`.
2. Define a function `display` to display the elements of an array.
3. Define a function `isContainsElement` which takes the stack `s`, the array `arr`, and the size of the array `n` as inputs.
4. Create a HashSet called `record` to store the elements of the array.
5. Create a stack called `temp` to temporarily store the elements of the stack `s`.
6. Add all the elements of the array `arr` to the HashSet `record`.
7. Iterate through the stack `s` using a while loop until it becomes empty: a. Get the top element of the stack and store it in a variable `auxiliary`. b. If `auxiliary` is present in the HashSet `record`, remove it from the HashSet. c. Push `auxiliary` into the stack `temp`. d. Pop the top element from the stack `s`.
8. Iterate through the stack `temp` using a while loop until it becomes empty: a. Get the top element of the stack `temp` and store it in a variable `auxiliary`. b. Push `auxiliary` into the stack `s`. c. Pop the top element from the stack `temp`.
9. Display the elements of the array `arr` using the `display` function.
10. Check if the HashSet `record` is empty: a. If it is empty, display "Array element exists in Stack". b. If it is not empty, display "Array element are not exists in Stack".

## Code Solution

``````/*
Java Program
Check if stack contains given array element present or not
*/
import java.util.HashSet;
import java.util.Stack;
public class Finding
{
// Function which is display array elements
public void display(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print("   " + arr[i]);
}
System.out.print("\n");
}
public void isContainsElement(Stack < Integer > s, int[] arr, int n)
{
int auxiliary = 0;
HashSet < Integer > record = new HashSet < Integer > ();
// Use to collect stack element
Stack < Integer > temp = new Stack < Integer > ();
// Get the unique element in array
for (int i = 0; i < n; ++i)
{
}
// Check whether stack contains given array elements or not
while (!s.isEmpty())
{
auxiliary = s.peek();

if (record.contains(auxiliary))
{
record.remove(auxiliary);
}

temp.push(auxiliary);

s.pop();
}
// Put the removed element into actual stack
while (!temp.isEmpty())
{
auxiliary = temp.peek();
s.push(auxiliary);
temp.pop();
}
// Display given array elements
display(arr, n);
if (record.size() == 0)
{
System.out.print(" Array element exists in Stack\n");
}
else
{
System.out.print(" Array element are not exists in Stack\n");
}
}
public static void main(String[] arg)
{
// Define array of integer elements
int[] arr1 = {
1 , 7 , 3
};
int[] arr2 = {
10 , 15 , 5 , 0
};
Stack < Integer > s = new Stack < Integer > ();
s.push(5);
s.push(3);
s.push(7);
s.push(10);
s.push(8);
s.push(1);
// Get the number of elements
int n = arr1.length;
// Test case
n = arr2.length;
}
}``````

#### Output

``````   1   7   3
Array element exists in Stack
10   15   5   0
Array element are not exists in Stack``````
``````// Include header file
#include <iostream>
#include <set>
#include <stack>

using namespace std;
/*
C++ Program
Check if stack contains given array element present or not
*/
class Finding
{
public:
// Function which is display array elements
void display(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << "   " << arr[i];
}
cout << "\n";
}
void isContainsElement(stack < int > s, int arr[], int n)
{
int auxiliary = 0;
set < int > record ;
// Use to collect stack element
stack < int > temp ;
// Get the unique element in array
for (int i = 0; i < n; ++i)
{
record.insert(arr[i]);
}
// Check whether stack contains given array elements or not
while (!s.empty())
{
auxiliary = s.top();
if (record.find(auxiliary) != record.end())
{
record.erase(auxiliary);
}
temp.push(auxiliary);
s.pop();
}
// Put the removed element into actual stack
while (!temp.empty())
{
auxiliary = temp.top();
s.push(auxiliary);
temp.pop();
}
// Display given array elements
this->display(arr, n);
if (record.size() == 0)
{
cout << " Array element exists in Stack\n";
}
else
{
cout << " Array element are not exists in Stack\n";
}
}
};
int main()
{
// Define array of integer elements
int arr1[] = {
1 , 7 , 3
};
int arr2[] = {
10 , 15 , 5 , 0
};
stack < int > s ;
s.push(5);
s.push(3);
s.push(7);
s.push(10);
s.push(8);
s.push(1);
// Get the number of elements
int n = sizeof(arr1) / sizeof(arr1);
// Test case
n = sizeof(arr2) / sizeof(arr2);
return 0;
}``````

#### Output

``````   1   7   3
Array element exists in Stack
10   15   5   0
Array element are not exists in Stack``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
C# Program
Check if stack contains given array element present or not
*/
public class Finding
{
// Function which is display array elements
public void display(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write("   " + arr[i]);
}
Console.Write("\n");
}
public void isContainsElement(Stack < int > s, int[] arr, int n)
{
int auxiliary = 0;
HashSet < int > record = new HashSet < int > ();
// Use to collect stack element
Stack < int > temp = new Stack < int > ();
// Get the unique element in array
for (int i = 0; i < n; ++i)
{
}
// Check whether stack contains given array elements or not
while (s.Count > 0)
{
auxiliary = s.Peek();
if (record.Contains(auxiliary))
{
record.Remove(auxiliary);
}
temp.Push(auxiliary);
s.Pop();
}
// Put the removed element into actual stack
while (temp.Count > 0)
{
auxiliary = temp.Peek();
s.Push(auxiliary);
temp.Pop();
}
// Display given array elements
display(arr, n);
if (record.Count == 0)
{
Console.Write(" Array element exists in Stack\n");
}
else
{
Console.Write(" Array element are not exists in Stack\n");
}
}
public static void Main(String[] arg)
{
// Define array of integer elements
int[] arr1 = {
1 , 7 , 3
};
int[] arr2 = {
10 , 15 , 5 , 0
};
Stack < int > s = new Stack < int > ();
s.Push(5);
s.Push(3);
s.Push(7);
s.Push(10);
s.Push(8);
s.Push(1);
// Get the number of elements
int n = arr1.Length;
// Test case
n = arr2.Length;
}
}``````

#### Output

``````   1   7   3
Array element exists in Stack
10   15   5   0
Array element are not exists in Stack``````
``````from queue import LifoQueue

#    Python 3 Program
#    Check if stack contains given array element present or not

class Finding :
#  Function which is display list elements
def display(self, arr, n) :
i = 0
while (i < n) :
print("   ", arr[i], end = "")
i += 1

print(end = "\n")

def isContainsElement(self, s, arr, n) :
auxiliary = 0
record = set()
#  Use to collect stack element
temp = LifoQueue(maxsize = s.qsize())
#  Get the unique element in list
i = 0
while (i < n) :
i += 1

#  Check whether stack contains given list elements or not
while (not s.empty()) :
auxiliary = s.get() # get and remove
if (auxiliary in record) :
record.remove(auxiliary)

temp.put(auxiliary)

#  Put the removed element into actual stack
while (not temp.empty()) :
auxiliary = temp.get()
s.put(auxiliary)

#  Display given list elements
self.display(arr, n)
if (len(record) == 0) :
print(" Array element exists in Stack")
else :
print(" Array element are not exists in Stack")

def main() :
#  Define list of integer elements
arr1 = [1, 7, 3]
arr2 = [10, 15, 5, 0]
s = LifoQueue(maxsize = 6)
s.put(5)
s.put(3)
s.put(7)
s.put(10)
s.put(8)
s.put(1)
#  Get the number of elements
n = len(arr1)
#  Test case
n = len(arr2)

if __name__ == "__main__": main()``````

#### Output

``````    1    7    3
Array element exists in Stack
10    15    5    0
Array element are not exists in Stack``````
``````import scala.collection.mutable._;
/*
Scala Program
Check if stack contains given array element present or not
*/
class Finding
{
// Function which is display array elements
def display(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print("   " + arr(i));
i += 1;
}
print("\n");
}
def isContainsElement(s: Stack[Int] , arr: Array[Int], n: Int): Unit = {
var auxiliary: Int = 0;
var record: Set[Int] = Set();
// Use to collect stack element

var temp = Stack[Int]();
// Get the unique element in array
var i: Int = 0;
while (i < n)
{
i += 1;
}
// Check whether stack contains given array elements or not
while (!s.isEmpty)
{
auxiliary = s.top;
if (record.contains(auxiliary))
{
record.remove(auxiliary);
}
temp.push(auxiliary);
s.pop;
}
// Put the removed element into actual stack
while (!temp.isEmpty)
{
auxiliary = temp.top;
s.push(auxiliary);
temp.pop;
}
// Display given array elements
this.display(arr, n);
if (record.size == 0)
{
print(" Array element exists in Stack\n");
}
else
{
print(" Array element are not exists in Stack\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Finding = new Finding();
// Define array of integer elements
var arr1: Array[Int] = Array(1, 7, 3);
var arr2: Array[Int] = Array(10, 15, 5, 0);
var s  = Stack[Int]();
s.push(5);
s.push(3);
s.push(7);
s.push(10);
s.push(8);
s.push(1);
// Get the number of elements
var n: Int = arr1.length;
// Test case
n = arr2.length;
}
}``````

#### Output

``````   1   7   3
Array element exists in Stack
10   15   5   0
Array element are not exists in Stack``````
``````import Foundation
/*
Swift 4 Program
Check if stack contains given array element present or not
*/

// implement stack
struct Stack
{
private
var items: [Int] = []
func peek()->Int
{
if (self.isEmpty()==false)
{
return items.first!
}
else
{
fatalError("This stack is empty.")
}
}
func isEmpty()->Bool
{
return items.count == 0
}
mutating func pop()->Int
{
return items.removeFirst()
}
mutating func push(_ data: Int)
{
items.insert(data, at: 0)
}
}
class Finding
{
// Function which is display array elements
func display(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print("   ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
func isContainsElement(_ s: inout Stack, _ arr: [Int], _ n: Int)
{
var auxiliary: Int = 0;
var record = Set < Int > ();
// Use to collect stack element
var temp: Stack = Stack();
// Get the unique element in array
var i: Int = 0;
while (i < n)
{
record.insert(arr[i]);
i += 1;
}
// Check whether stack contains given array elements or not
while (!s.isEmpty())
{
auxiliary = s.pop();
if (record.contains(auxiliary))
{
record.remove(auxiliary);
}
temp.push(auxiliary);

}
// Put the removed element into actual stack
while (!temp.isEmpty())
{
auxiliary = temp.pop();
s.push(auxiliary);

}
// Display given array elements
self.display(arr, n);
if (record.count == 0)
{
print(" Array element exists in Stack");
}
else
{
print(" Array element are not exists in Stack");
}
}
}
func main()
{
// Define array of integer elements
let arr1: [Int] = [1, 7, 3];
let arr2: [Int] = [10, 15, 5, 0];
var s = Stack();
s.push(5);
s.push(3);
s.push(7);
s.push(10);
s.push(8);
s.push(1);
// Get the number of elements
var n: Int = arr1.count;
// Test case
n = arr2.count;
}
main();``````

#### Output

``````    1    7    3
Array element exists in Stack
10    15    5    0
Array element are not exists in Stack``````

## Time Complexity

The time complexity of this algorithm is O(n + m), where n is the number of elements in the array and m is the number of elements in the stack. The HashSet operations like adding and checking for elements take O(1) time on average. The while loop for iterating through the stack runs in O(m) time. Therefore, the overall time complexity of the algorithm is O(n + m).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.