Check if two Stacks are equal or not without alteration
Given two Stacks S1 and S2, the task is to check if both the stacks are equal or not in the same order without losing the original stacks. If both the stacks are equal, then print “Yes “. Otherwise, print “No”.
Examples:
Input: S1 = {3, 4, 2, 1}, S2 = {3, 4, 2, 1}
Output: YesInput: S1 = {3, 4, 6}, S2 = {7, 2, 1}
Output: No
Approach: The given problem can be solved by moving some amount of elements between the given two stacks for checking each corresponding element in the two stacks. Follow the steps below to solve the problem:
- Store the size of stack S1 and S2, in a variable N and M respectively.
- If N is not equal to M, then print “No” and return.
- Iterate over the range [1, N] and perform the following operations:
- Push the top (N – i) elements of the stack S1 to the stack S2.
- Now, store the top element of S1 stack in a variable, say val.
- Now, push the top 2 * (N – i) elements from the stack S2 to the stack S1.
- If the value of val is not equal to the top value of the stack S2, then print “No” and return.
- Otherwise, restore the stacks by pushing top (N – i) elements from the stack S1 to stack S2.
- After completing the above steps, if none of the above cases satisfy, then print “Yes“.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to push the elements from// one stack element into another stackvoid pushElements(stack<int> s1, stack<int> s2, int len){ int i = 1; while (i <= len) { // Update the stack if (s1.size() > 0) { s2.push(s1.top()); s1.pop(); } // Increment i i++; }}// Function to compare two given stacksstring compareStacks(stack<int> s1, stack<int> s2){ // Stores the size of S1 stack int N = s1.size(); // Stores the size of S2 stack int M = s2.size(); // If N is not equal to M if (N != M) { return "No"; } // Traverse the range [1, N] for (int i = 1; i <= N; i++) { // Push N-i elements to stack // S2 from stack S1 pushElements(s1, s2, N - i); // Stores the top value of S1 int val = s1.top(); // Pushes the 2 * (N-i) // elements from S2 to S1 pushElements(s2, s1, 2 * (N - i)); // If val is not equal // to the top of S2 if (val != s2.top()) return "No"; // Restores the stacks pushElements(s1, s2, N - i); } // Return return "Yes";}// Driver Codeint main(){ stack<int> S1, S2; S1.push(1); S1.push(2); S1.push(4); S1.push(3); S2.push(1); S2.push(2); S2.push(4); S2.push(3); cout << (compareStacks(S1, S2));}// This code is contributed by ukassp. |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to compare two given stacks static String compareStacks( Stack<Integer> s1, Stack<Integer> s2) { // Stores the size of S1 stack int N = s1.size(); // Stores the size of S2 stack int M = s2.size(); // If N is not equal to M if (N != M) { return "No"; } // Traverse the range [1, N] for (int i = 1; i <= N; i++) { // Push N-i elements to stack // S2 from stack S1 pushElements(s1, s2, N - i); // Stores the top value of S1 int val = s1.peek(); // Pushes the 2 * (N-i) // elements from S2 to S1 pushElements(s2, s1, 2 * (N - i)); // If val is not equal // to the top of S2 if (val != s2.peek()) return "No"; // Restores the stacks pushElements(s1, s2, N - i); } // Return return "Yes"; } // Function to push the elements from // one stack element into another stack static void pushElements( Stack<Integer> s1, Stack<Integer> s2, int len) { int i = 1; while (i <= len) { // Update the stack s2.push(s1.pop()); // Increment i i++; } } // Driver Code public static void main(String[] args) { Stack<Integer> S1 = new Stack<>(); Stack<Integer> S2 = new Stack<>(); S1.push(1); S1.push(2); S1.push(4); S1.push(3); S2.push(1); S2.push(2); S2.push(4); S2.push(3); System.out.println( compareStacks(S1, S2)); }} |
Python3
# Python3 program for the above approach# Function to compare two given stacksdef compareStacks(s1, s2): # Stores the size of S1 stack N = len(s1) # Stores the size of S2 stack M = len(s2) # If N is not equal to M if (N != M): return "No" # Traverse the range [1, N] for i in range(1, N + 1): # Push N-i elements to stack # S2 from stack S1 pushElements(s1, s2, N - i) # Stores the top value of S1 val = s1[-1] # Pushes the 2 * (N-i) # elements from S2 to S1 pushElements(s2, s1, 2 * (N - i)) # If val is not equal # to the top of S2 if (val != s2[-1]): return "No" # Restores the stacks pushElements(s1, s2, N - i) # Return return "Yes"# Function to push the elements from# one stack element into another stackdef pushElements(s1, s2, len): i = 1 while (i <= len): # Update the stack s2.append(s1[-1]) del s1[-1] # Increment i i += 1# Driver Codeif __name__ == '__main__': S1 = [] S2 = [] S1.append(1) S1.append(2) S1.append(4) S1.append(3) S2.append(1) S2.append(2) S2.append(4) S2.append(3) print(compareStacks(S1, S2))# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to compare two given stacks static String compareStacks( Stack<int> s1, Stack<int> s2) { // Stores the size of S1 stack int N = s1.Count; // Stores the size of S2 stack int M = s2.Count; // If N is not equal to M if (N != M) { return "No"; } // Traverse the range [1, N] for (int i = 1; i <= N; i++) { // Push N-i elements to stack // S2 from stack S1 pushElements(s1, s2, N - i); // Stores the top value of S1 int val = s1.Peek(); // Pushes the 2 * (N-i) // elements from S2 to S1 pushElements(s2, s1, 2 * (N - i)); // If val is not equal // to the top of S2 if (val != s2.Peek()) return "No"; // Restores the stacks pushElements(s1, s2, N - i); } // Return return "Yes"; } // Function to push the elements from // one stack element into another stack static void pushElements( Stack<int> s1, Stack<int> s2, int len) { int i = 1; while (i <= len) { // Update the stack s2.Push(s1.Pop()); // Increment i i++; } } // Driver Code public static void Main(String[] args) { Stack<int> S1 = new Stack<int>(); Stack<int> S2 = new Stack<int>(); S1.Push(1); S1.Push(2); S1.Push(4); S1.Push(3); S2.Push(1); S2.Push(2); S2.Push(4); S2.Push(3); Console.WriteLine( compareStacks(S1, S2)); }}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for the above approach// Function to push the elements from// one stack element into another stackfunction pushElements(s1, s2, len){ var i = 1; while (i <= len) { // Update the stack if (s1.length > 0) { s2.push(s1[s1.length-1]); s1.pop(); } // Increment i i++; }}// Function to compare two given stacksfunction compareStacks(s1, s2){ // Stores the size of S1 stack var N = s1.length; // Stores the size of S2 stack var M = s2.length; // If N is not equal to M if (N != M) { return "No"; } // Traverse the range [1, N] for (var i = 1; i <= N; i++) { // Push N-i elements to stack // S2 from stack S1 pushElements(s1, s2, N - i); // Stores the top value of S1 var val = s1[s1.length-1]; // Pushes the 2 * (N-i) // elements from S2 to S1 pushElements(s2, s1, 2 * (N - i)); // If val is not equal // to the top of S2 if (val != s2[s2.length-1]) return "No"; // Restores the stacks pushElements(s1, s2, N - i); } // Return return "Yes";}// Driver Codevar S1 = [], S2 = [];S1.push(1);S1.push(2);S1.push(4);S1.push(3);S2.push(1);S2.push(2);S2.push(4);S2.push(3);document.write(compareStacks(S1, S2));//This code is contributed by rutvik_56.</script> |
Output:
Yes
Time Complexity: O(N2)
Auxiliary Space: O(1), since no extra space has been taken.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
