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

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
• C++
• C#
• Python
• Scala
• Swift 4

/*
   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);
    }
}

   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;
}

   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);
	}
}

   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()

    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);
	}
}

   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();

    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).