Home > Mobile >  How can I check if 2 given stacks has the same values? (Not necessarily in the same order)
How can I check if 2 given stacks has the same values? (Not necessarily in the same order)

Time:01-02

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));
  • Related