How to check if two stacks are equal in Python?

By /
Python Check If Two Stacks Are Equal Or Not

In this tutorial, we are going to discuss the different approaches to check if two stacks are equal or not using Python.

What is a stack?

A Python stack is a linear data structure that works on the LIFO principle. According to the LIFO principle, the element which is inserted at last in the stack will be removed/accessed at first. That’s why we call it Last In First Out. This means that we can perform the different operations on a stack only in a single direction. A stack can be implemented in any programming language including Python. In Python, a stack can be implemented using a list, deque, and LifoQueue. For simplicity purposes, here we will be using a Python list to implement the stack.

Properties of a Python stack

  • A stack is unidirectional i.e. element of a stack can be inserted or deleted only from its one end.
  • A stack maintains a top pointer that points to the last element of the stack.
  • To access the (i)th element of the stack we must remove the last (N-i)th elements.
  • A stack can be dynamic with no overflow condition or static with overflow condition.

Check Equality of Two Stacks in Python

We are given two stacks and have to check if the two stacks are the same. The two stacks are called equal only when they have the same number of elements with the same values and in the same order or sequence. For example:

stack1 = [1, 5, 7, 9]
stack2 = [1, 5, 7, 9]
(stack1 & stack2) are the same.
stack3 = [9, 5, 7, 1]
(stack1 & stack3) and (stack2 & stack3) are not the same.

Method 1: Compare and pop the top element of the two stacks

Let’s see the algorithm for method one to check the equality of two given stacks in Python:

  1. First create a checker variable and set it to True (initially assume both the stacks are equal).
  2. Then compare the size of both the stacks and if they are not equal set checker variable to False and return the control.
  3. Else compare the top elements of both the stacks. If they are equal, pop them from both the stacks.
  4. If the top elements of the stacks are not equal, then set the checker variable to False and return the control.
  5. Repeat the step 3 and 4 till both the stacks become empty i.e. all the elements of the stacks are popped out.
  6. Finally check the value of checker variable which we defined in the step 1 if it is True that means the two stacks are equal else, they are not equal (or unequal).

Let’s implement the above algorithm through Python code.

# Define a function in Python
# To check if the two stacks
# Equal or not
def equal_stacks(s1, s2):
    # Create a checker variable
    # And initialize it with True
    val = True

    # Check the size of both stacks
    # Passed as arguments
    if len(s1) != len(s2):
        val = False
        return val

    # Compare the top of each stack
    while(len(s1)):
        if s1[-1] == s2[-1]:
            s1.pop()
            s2.pop()
        else:
            val = False
            break
    # Return the final value
    # Of checker variable val
    return val

# Driver Code
# Define two stacks
stack1 = [8, 15, 7, 11]
stack2 = [8, 15, 9, 11]

# Pass the above two Stacks to equal_stacks() function
# And check their equality
if equal_stacks(stack1, stack2):
    print("Two stacks are equal!")
else:
    print("Two stacks are not equal!!")

# Print the contents of both the stacks
# After their comparison
print(f'\nStack-1 after comparison: {stack1}')
print(f'\nStack-2 after comparison: {stack2}')

Output:

Two stacks are not equal!

Stack-1 after comparison: [8, 15, 7]      

Stack-2 after comparison: [8, 15, 9]

In the above output, we can clearly see the content of both the stacks has been altered or changed after their comparison.

Method 2: Compare the top element of the two stacks without alteration

Let’s see the algorithm for method two to check the equality of two given stacks in Python:

  1. First create a checker variable and set it to True (Initially assume both the stacks are equal).
  2. Then save the size of both the stacks in two separate variables say (P and Q) and compare them. If they are not equal, set checker variable to False and return the control.
  3. Else run a for loop over the range [1, P + 1] and do the following things:
    1. First transfer the top (P-1) elements of stack 1 to stack 2.
    2. Store the current top element of the stack 1 to a separate variable say temp.
    3. Now transfer the top 2*(P-1) elements of stack 2 to stack 1.
    4. Compare the top element of stack 2 with the value inside the temp variable i.e. top element of the stack 1.
    5. If both the corresponding top elements of both the stacks are equal, then reconstruct both the stacks by transferring the top (P-1) elements of stack 1 to stack 2.
    6. Else set the checker variable to False and return the control.
  4. Finally check the value of checker variable which we defined in the step 1 if it is True that means the two stacks are equal else, they are not equal (or unequal).

Let’s implement the above algorithm through Python code.

# Define a function to push the elements of
# One stack into another stack
def push_stack(s1, s2, len):
	i = 1
	while (i <= len):
        # Append the top of s1 to s2
		s2.append(s1[-1])
        # Delete the top of s1
		s1.pop()
        # Increment the loop counter
		i = i + 1

# Define a function to check 
# If the two stacks equal or not
def equal_stacks(s1, s2):
    # Create a checker variable
    # And initialize it with True
    val = True
	# Find the size of S1 stack
    P = len(s1)
	# Find the size of S2 stack
    Q = len(s2)
	# Compare the size of s1 & s2 stacks
    if (P != Q):
        val = False
        return val
    # Compare the top elements of each stack
    for i in range(1, P + 1):
        # Push P-i elements of stack s1 to stack s2
        push_stack(s1, s2, P - i)
		# Save the value of S1 top
        val = s1[-1]
		# Push 2 * (P-i) elements of stack S2 to stack S1
        push_stack(s2, s1, 2 * (P - i))
		# Compare the top elements of both stacks s1 & s2
        if (val != s2[-1]):
            val = False
            return val
		# Reconstruct both the stacks s1 & s2
        push_stack(s1, s2, P - i)
	# Return the final value of val
    return val

# Driver Code
# Define two stacks
stack1 = [5, 7, 11, 8]
stack2 = [5, 7, 11, 8]

# Pass the above two Stacks to equal_stacks() function
# And check their equality
if equal_stacks(stack1, stack2):
    print("Two stacks are equal!")
else:
    print("Two stacks are not equal!!")

# Print the contents of both the stacks
# After their comparison
print(f'\nStack-1 after comparison: {stack1}')
print(f'\nStack-2 after comparison: {stack2}')

Output:

Two stacks are equal!

Stack-1 after comparison: [5, 7, 11, 8]   

Stack-2 after comparison: [5, 7, 11, 8]

In the above output, we can clearly see the contents of both the stacks have not been altered or changed after their comparison.

Conclusion

In this tutorial, we have learned the different methods to check the equality of the two given stacks in Python.

  • In the first method, we have checked the equality of the two stacks after altering them i.e. at the end we do not have the original stacks.
  • In the second method, we have checked the equality of the two stacks without altering them i.e. at the end we have the original stacks.