Question

Given the two stacks S1 and S2 each with a set of numbers, write an algorithm to check if the two stacks are identical (have the same information). Use only the Push and Pop operations. The original stacks should be kept. Briefly explain the time complexity of your algorithm.

Answer 1

Algorithm:

1. Take a flag variable and set it to true initially, flag = true. This variable will indicate whether the stacks are same or not.
2. First check if the size of given stack1 and stack2 are equal. If the size is not equal, set flag to false and return it.
3. If the size is same, then compare the top elements of both of the given stacks.
4. If the top of both stacks is NOT same, set flag to false and return it otherwise pop top elements of both stacks.
5. Repeat step 3 and 4 until all elements are popped out from both of the stacks.
6. If both stacks gets empty and the flag variable is still true, it means that the stacks are same.

Function implementing whether two stacks are equal or not:

static boolean isSameStack(Stack<String> stack1,

                            Stack<String> stack2)

{

    // Create a flag variable

    boolean flag = true;

  

    // Check if size of both stacks are same

    if (stack1.size() != stack2.size())

    {

        flag = false;

        return flag;

    }

  

    // Until the stacks are not empty

    // compare top of both stacks

    while (stack1.empty() == false)

    {

        // If the top elements of both stacks

        // are same

        if (stack1.peek() == stack2.peek())

        {

            // Pop top of both stacks

            stack1.pop();

            stack2.pop();

        }

        else

        {

            // Otherwise, set flag to false

            flag = false;

            break;

        }

    }

  

    // Return flag

    return flag;

}