A Function that Compares Two Stacks for Equality C++

Comparing two stacks for equality in C++ involves verifying that they contain the same elements in the same order. Before C++20, this required a manual approach. This article outlines a clear, step-by-step method to implement a function that accomplishes this task.

Understanding Stack Comparison

Stacks operate on the Last-In, First-Out (LIFO) principle. Therefore, two stacks are equal only if:

• They have the same size.
• Elements at each corresponding position are identical.

Direct comparison using operators wasn’t possible before C++20. Hence, a custom function is necessary.

Implementing the Comparison Function

The function compareStacks takes two stacks (s1 and s2) as input and returns true if they are equal, and false otherwise.

#include <iostream>
#include <stack>

using namespace std;

bool compareStacks(stack<int>& s1, stack<int>& s2) {
  // Check if sizes are different
  if (s1.size() != s2.size()) {
    return false;
  }

  // Compare elements one by one from the top
  while (!s1.empty()) {
    if (s1.top() != s2.top()) {
      return false;
    }
    s1.pop();
    s2.pop();
  }

  return true; // Stacks are equal
}

int main() {
  stack<int> stack1, stack2;

  stack1.push(1);
  stack1.push(2);
  stack1.push(3);

  stack2.push(1);
  stack2.push(2);
  stack2.push(3);


  if (compareStacks(stack1, stack2)) {
    cout << "Stacks are equal." << endl;
  } else {
    cout << "Stacks are not equal." << endl;
  }

  return 0;
}

Output:

Stacks are equal.

Explanation:

1. Size Check: The function first checks if the stacks have the same size. If not, they cannot be equal, so it immediately returns false.

2. Element Comparison: If the sizes are equal, the function enters a while loop that continues as long as s1 is not empty. Inside the loop:

   • It compares the top elements of both stacks using s1.top() and s2.top().
   • If the top elements are different, it returns false.
   • If the top elements are the same, it removes them from both stacks using s1.pop() and s2.pop(). This allows comparison of the next pair of elements.

3. Equality Confirmation: If the loop completes without finding any unequal elements, it signifies that all corresponding elements were identical, and both stacks are now empty. Thus, the function returns true.

Time and Space Complexity

• Time Complexity: O(N), where N is the size of the smaller stack. In the worst case, all elements are compared.
• Auxiliary Space: O(1), as the function uses only a few extra variables for comparison and does not require any additional data structures that scale with the input size. Note that popping elements modifies the original stacks. If preserving the original stacks is required, copies should be made before calling the function, increasing auxiliary space complexity to O(N). However, the core comparison logic itself remains constant in space usage.