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:

- First create a checker variable and set it to
**True**(initially assume both the stacks are equal). - Then compare the size of both the stacks and if they are not equal set checker variable to
**False**and return the control. - Else compare the top elements of both the stacks. If they are equal, pop them from both the stacks.
- If the top elements of the stacks are not equal, then set the checker variable to
**False**and return the control. - Repeat the
**step 3**and**4**till both the stacks become empty i.e. all the elements of the stacks are popped out. - 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:

- First create a checker variable and set it to
**True**(Initially assume both the stacks are equal). - 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. - Else run a
**for loop**over the range [1, P + 1] and do the following things:- First transfer the top (P-1) elements of stack 1 to stack 2.
- Store the current top element of the stack 1 to a separate variable say temp.
- Now transfer the top 2*(P-1) elements of stack 2 to stack 1.
- Compare the top element of stack 2 with the value inside the temp variable i.e. top element of the stack 1.
- 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.
- Else set the checker variable to
**False**and return the control.

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