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:
Add arr[i] to record
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
- Create a class called
Finding
. - Define a function
display
to display the elements of an array. - Define a function
isContainsElement
which takes the stacks
, the arrayarr
, and the size of the arrayn
as inputs. - Create a HashSet called
record
to store the elements of the array. - Create a stack called
temp
to temporarily store the elements of the stacks
. - Add all the elements of the array
arr
to the HashSetrecord
. - 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 variableauxiliary
. b. Ifauxiliary
is present in the HashSetrecord
, remove it from the HashSet. c. Pushauxiliary
into the stacktemp
. d. Pop the top element from the stacks
. - Iterate through the stack
temp
using a while loop until it becomes empty: a. Get the top element of the stacktemp
and store it in a variableauxiliary
. b. Pushauxiliary
into the stacks
. c. Pop the top element from the stacktemp
. - Display the elements of the array
arr
using thedisplay
function. - 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)
{
record.add(arr[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)
{
Finding task = new Finding();
// Define array of integer elements
int[] arr1 = {
1 , 7 , 3
};
int[] arr2 = {
10 , 15 , 5 , 0
};
Stack < Integer > s = new Stack < Integer > ();
// Add element
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
task.isContainsElement(s, arr1, n);
n = arr2.length;
task.isContainsElement(s, arr2, n);
}
}
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()
{
Finding task = Finding();
// Define array of integer elements
int arr1[] = {
1 , 7 , 3
};
int arr2[] = {
10 , 15 , 5 , 0
};
stack < int > s ;
// Add element
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[0]);
// Test case
task.isContainsElement(s, arr1, n);
n = sizeof(arr2) / sizeof(arr2[0]);
task.isContainsElement(s, arr2, n);
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)
{
record.Add(arr[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)
{
Finding task = new Finding();
// Define array of integer elements
int[] arr1 = {
1 , 7 , 3
};
int[] arr2 = {
10 , 15 , 5 , 0
};
Stack < int > s = new Stack < int > ();
// Add element
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
task.isContainsElement(s, arr1, n);
n = arr2.Length;
task.isContainsElement(s, arr2, n);
}
}
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) :
record.add(arr[i])
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() :
task = Finding()
# Define list of integer elements
arr1 = [1, 7, 3]
arr2 = [10, 15, 5, 0]
s = LifoQueue(maxsize = 6)
# Add element
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
task.isContainsElement(s, arr1, n)
n = len(arr2)
task.isContainsElement(s, arr2, n)
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)
{
record.add(arr(i));
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]();
// Add element
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
task.isContainsElement(s, arr1, n);
n = arr2.length;
task.isContainsElement(s, arr2, n);
}
}
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()
{
let task: Finding = Finding();
// Define array of integer elements
let arr1: [Int] = [1, 7, 3];
let arr2: [Int] = [10, 15, 5, 0];
var s = Stack();
// Add element
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
task.isContainsElement(&s, arr1, n);
n = arr2.count;
task.isContainsElement(&s, arr2, n);
}
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).
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.
New Comment