# Check two stacks for equality

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) {
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;
}


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;
}

• If you test for equality before push, there's no need to push both values. You already know they are equal.
– vnp
Dec 1 '17 at 20:21
• 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.
– amon
Dec 2 '17 at 8:11