2
\$\begingroup\$

Write a method equals that takes as parameters two stacks of integers and returns true if the two stacks are equal and that returns false otherwise. To be considered equal, the two stacks would have to store the same sequence of integer values in the same order. Your method is to examine the two stacks but must return them to their original state before terminating. You may use one stack as auxiliary storage.

I'm pretty new to stacks and queues, and data structures in general. I'd like to know if there are other ways I can do this that are easier or better for when I'm dealing with stacks in the future. Also, is my code readable? Does everything "make sense"? And can my code be easily optimized?

public boolean equals(Stack<Integer> s1, Stack<Integer> s2) {
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();
    boolean equal = true;

    while (!s1.isEmpty() && !s2.isEmpty()) {
        int firstNum = s1.pop();
        int secondNum = s2.pop();
        q1.offer(firstNum);
        q2.offer(secondNum);
        if (firstNum != secondNum) {
            equal = false;
        }
    }

    // used to preserve stack structure
    if (s1.isEmpty() && !s2.isEmpty()) {
        while(!s2.isEmpty()) {
            q2.offer(s2.pop());
        }
        equal = false;
    }

    if (s2.isEmpty() && !s1.isEmpty()) {
        while(!s1.isEmpty()) {
            q1.offer(s1.pop());
        }
        equal = false;
    }

    // add back to stack using s -> q -> s
    // for both stacks
    while (!q1.isEmpty()) {
        s1.push(q1.remove());
    }
    while (!s1.isEmpty()) {
        q1.offer(s1.pop());
    }
    while (!q1.isEmpty()) {
        s1.push(q1.remove());
    }

    while (!q2.isEmpty()) {
        s2.push(q2.remove());
    }
    while (!s2.isEmpty()) {
        q2.offer(s2.pop());
    }
    while (!q2.isEmpty()) {
        s2.push(q2.remove());
    }


    return equal;
}
\$\endgroup\$
5
\$\begingroup\$

Your code breaks the rules slightly by using two queues as auxiliary storage - I've done it with the allowed single stack. As you can see the first part of the code is very similar to yours, but the reconstruction and equals checking are simpler. By knowing that I always put the elements from s1 first, I need to reconstruct the other way around so s2 first later on from aux.

The code works nicely with empty inputs and puts them back in the correct order

    public boolean equals(Stack<Integer> s1, Stack<Integer> s2){
    Stack<Integer> aux = new Stack<>();
    boolean equal = true;
    while(!s1.isEmpty() && !s2.isEmpty()){
        int first = s1.pop();
        int second = s2.pop();
        aux.push(first);
        aux.push(second);
        if(first != second){
            equal = false;
            break;
        }
    }
    // Equal if both stacks are empty
     if(!(s1.isEmpty() || s2.isEmpty())){
        equal = false;
     }

    // Reconstruct
    while(!aux.isEmpty()){
        s2.push(aux.pop());
        s1.push(aux.pop());
    }
    return equal;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ If you test for equality before push, there's no need to push both values. You already know they are equal. \$\endgroup\$ – vnp Dec 1 '17 at 20:21
  • \$\begingroup\$ Isn't it necessary to check before you pop from the input stacks? If two stacks of same length are equal except for the last element, then you'd pop them and break the loop. Afterwards the stacks are empty so you'd consider them equal – a bug. \$\endgroup\$ – amon Dec 2 '17 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.