Question

Ellie needs a data structure that can handle the following operations: push, pop, contains, remove, where contains(Item x) answers whether a given item is in the data structure and remove(Item x) removes the given item from the data structure. How can this be implemented efficiently?

Answer 1

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

public class MyStack {
        
        static class Node {
                int value;
                Node next;
                Node prev;
                
                public Node(int x, Node next) {
                        this.value = x;
                        this.next = next;
                }
        }
        
        Node stack = null;
        
        // to keep count of each element
        // HashSet can not be used alone, Since, We need to push and pop
        private HashMap<Integer, ArrayList<Node>> hashSet = new HashMap<>();
        
        public void push(int x) {
                stack = new Node(x, stack);
                if(stack.next != null) {
                        stack.next.prev = null;
                }
                
                ArrayList<Node> nodeAddresses = hashSet.getOrDefault(x, new ArrayList<>());
                nodeAddresses.add(0, stack);
                hashSet.put(x, nodeAddresses);
        }
        
        public int pop() {
                if(stack == null) {
                        throw new IllegalArgumentException("pop on empty list");
                }
                Node x = stack;
                stack = stack.next;
                if(stack != null) {
                        stack.prev = null;
                }
                hashSet.get(x.value).remove(0);
                return x.value;
        }
        
        public boolean contains(int x) {
                return hashSet.containsKey(x) && !hashSet.get(x).isEmpty();
        }
        
        public boolean remove(int x) {
                ArrayList<Node> nodeAddresses = hashSet.get(x);
                if(nodeAddresses == null) {
                        return false;
                }
                
                Node node = nodeAddresses.remove(0);
                
                if(node.prev != null) {
                        node.prev.next = node.next;
                } else {
                        stack = node.next;
                        stack.prev = null;
                }
                
                return true;
        }
        
        public static void main(String[] args) {
                MyStack s = new MyStack();
                s.push(10);
                s.push(20);
                s.push(30);
                s.push(10);
                s.push(20);
                
                s.remove(20); // remove one occurrence.
                System.out.println(s.pop());
                System.out.println(s.pop());
                System.out.println(s.pop());
                System.out.println(s.pop());
                
        }

}

**************************************************
Created the stack with the node addresses stored in an hashmap, Hence we can easily remove the nodes in between the stack, which in general is not allowed from the stack. Remove is an O(1) operation thus, and so are push, pop and contains.

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.