everybody. How can I check if 2 stacks has the same values?
For example, in stack1 I have [1,3,4,5] and in stack2 I have [4,3,1,5], so the stacks has the same values and the methood needs to return true.
In addition, the stacks must be (in the end) as they were given (with the original values and the same order).
I have started to work on it but unfortuantely it's not working good:
import java.util.Stack;
public class StackMain {
public static void main(String[] args) {
Stack<Integer> st1 = new Stack<Integer>();
st1.push(2);
st1.push(643);
st1.push(254);
st1.push(13);
st1.push(74);
st1.push(6);
st1.push(5);
st1.push(99);
Stack<Integer> st2 = new Stack<Integer>();
st2.push(643);
st2.push(2);
st2.push(254);
st2.push(13);
st2.push(99);
st2.push(5);
st2.push(6);
st2.push(74);
System.out.println(isSameStacks(st1,st2));
}
public static boolean isSameStacks(Stack st1, Stack st2)
{
Stack st1Reverse = new Stack();
Stack st2Reverse = new Stack();
boolean isExist = false;
while(st1.isEmpty()==false)
{
isExist = false;
st1Reverse.push(st1.pop());
while(st2.isEmpty()==false)
{
st2Reverse.push(st2.pop());
if(st1Reverse.peek()== st2Reverse.peek())
isExist = true;
}
while(st2Reverse.isEmpty()==false)
st2.push(st2Reverse.pop());
if(isExist!=true)
{
while(st1Reverse.isEmpty()==false)
st1.push(st1Reverse.pop());
return false;
}
}
while(st1Reverse.isEmpty()==false)
st1.push(st1Reverse.pop());
return true;
}
Thanks in advance.
CodePudding user response:
One simple way is to use the Collection
functionality:
public static boolean isSameStacks(Stack st1, Stack st2) {
if(st1.size() != st1.size()) return false;
List list = new ArrayList<>(st1);//add all st1 elements
list.removeAll(st2);//remove all st2 elements
return list.size() == 0;
}
For completeness here is another solution using Collection
functionality. It is based on the partial solution posted by @user7:
public static boolean isSameStacks(Stack st1, Stack st2) {
return st1.size() == st1.size() &&
new HashSet<>(st1).equals(new HashSet<>(st2));
}
CodePudding user response:
We can use Hashmap to get track of the element count in each stack and use them to check if both the stack were same
import java.util.*;
public class HelloWorld {
public static void main(String[] args) {
Stack<Integer> st1 = new Stack<Integer>();
st1.push(2);
st1.push(643);
st1.push(254);
st1.push(13);
st1.push(74);
st1.push(6);
st1.push(5);
st1.push(99);
Stack<Integer> st2 = new Stack<Integer>();
st2.push(643);
st2.push(2);
st2.push(254);
st2.push(13);
st2.push(99);
st2.push(5);
st2.push(6);
st2.push(74);
System.out.println("Is Same STack: " isSameStacks(st1,st2));
}
public static boolean isSameStacks(Stack<Integer> st1, Stack<Integer> st2)
{
Stack<Integer> st1Reverse = new Stack<Integer>();
Stack<Integer> st2Reverse = new Stack<Integer>();
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
boolean isExist = false;
while(st1.isEmpty()==false)
{
isExist = false;
Integer val = st1.pop();
Integer val2 = st2.pop();
st1Reverse.push(val);
st2Reverse.push(val2);
if(map.get(val) == null) {
map.put(val, 0);
}
if(map.get(val2) == null) {
map.put(val2, 0);
}
map.put(val, map.get(val) 1);
map.put(val2, map.get(val2) 1);
}
boolean res = true;
Integer tmp;
while(st1Reverse.isEmpty()==false) {
tmp = st1Reverse.pop();
if(map.get(tmp)%2 != 0) {
res = false;
}
st1.push(tmp);
}
while(st2Reverse.isEmpty()==false) {
tmp = st2Reverse.pop();
if(map.get(tmp)%2 != 0) {
res = false;
}
st2.push(tmp);
}
return res;
}
}
CodePudding user response:
UPDATE:
As mentioned by @lzruo, if the stack has duplicate elements, this will not work. Say stack1 has [1, 1, 2]
and stack2 has [1, 2]
, this will return true.
Initial answer:
Since a Java Stack
is a Vector
which is a Collection
(specifically a List
), we can iterate or create a stream from the stack and collect it in a Set
(HashSet
). This will not affect the elements (will not be removed). in the stack or their ordering.
Or simply, since a HashSet
constructor accepts a Collection
as we do like:
Set<Integer> stack1AsSet = new HashSet<>(st1);
Set<Integer> stack2AsSet = new HashSet<>(st2);
System.out.println(stack1AsSet.equals(stack2AsSet)); //prints true
The stack order or elements would not be affected.
System.out.println(st1.pop()); //prints 99
The answer by @c0der is simpler. But if you use a HashSet, you can check the stack sizes are equal before checking the set contents.
return st1.size() == st1.size() && new HashSet<>(st1).equals(new HashSet<>(st2));