Question

Josie 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? (Java)

Answer 1

After reading the question, what I understand is that you need a Stack class with extra functionalities to check if an element exists on it and to remove a specified element. Here is the completed code for this problem including test code. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

//Stack.java class

public class Stack<T> {

      private Node top;

      // constructor initializing empty stack

      public Stack() {

            top = null;

      }

      // method to add an element to the top of the stack

      // run time complexity: O(1)

      public void push(T item) {

            // creating a new node, adding before top, and updating top

            Node n = new Node(item);

            n.next = top;

            top = n;

      }

      // method to remove an element from the top of the stack

      // run time complexity: O(1)

      public T pop() {

            if (top == null) {

                  // empty

                  return null;

            }

            // storing top element

            T item = top.data;

            // removing top

            top = top.next;

            // returning top

            return item;

      }

      // method to check if an element exists on the stack

      // run time complexity (worst time): O(n)

      public boolean contains(T item) {

            // looping and comparing each element with item

            for (Node n = top; n != null; n = n.next) {

                  if (n.data.equals(item)) {

                        // found

                        return true;

                  }

            }

            // not found

            return false;

      }

      // removes an element from the stack, returns true if found, else not

      public boolean remove(T item) {

            if (top == null) {

                  // empty

                  return false;

            }

            if (top.data.equals(item)) {

                  // removing top

                  top = top.next;

                  return true;

            }

            // taking top node

            Node temp = top;

            // looping and checking each node

            while (temp.next != null) {

                  if (temp.next.data.equals(item)) {

                        // removing temp.next

                        temp.next = temp.next.next;

                        return true;

                  }

                  temp = temp.next;

            }

            return false; // not found

      }

      // returns true if stack is empty

      public boolean isEmpty() {

            return top == null;

      }

      // an inner class representing a node in the linked chain

      class Node {

            T data;

            Node next;

            public Node(T data) {

                  this.data = data;

                  next = null;

            }

      }

     

      //code for testing

      public static void main(String[] args) {

            // creating a Stack

            Stack<Integer> stk = new Stack<Integer>();

            // pushing some elements

            stk.push(1);

            stk.push(2);

            stk.push(3);

            stk.push(4);

            // testing contains()

            System.out.println(stk.contains(3)); // true

            // testing remove()

            stk.remove(3);

            System.out.println(stk.contains(3)); // false

            // looping and popping stack until it is empty

            while (!stk.isEmpty()) {

                  // will print 4, then 2, then 1

                  System.out.println(stk.pop());

            }

      }

}

/*OUTPUT*/

true

false

4

2

1