DATA STRUCTURE

LANGUAGE JAVA

Q1. Suppose you want to design a class to store the contents of grocery bag that can contain duplicate and unordered items. The size of the bag can increase and shrink as necessary and you need to store it to know the current number of items in the bag. Below is the description of the operations that you need to include inside the grocery bag class. public int getSize o Task: Gets the size of the bag. o Return the integer number of items currently in the bag public boolean isEmpty o Task: Sees whether the bag is empty O Return true if the bag is empty, or false if not. public boolean add(String newItem) o Task: Adds a new item to the bag. Increases the number of items by one. o Param: newItem the object to be added as a new item o Return true if the addition is successful, or false if not public String remove(String anItem) o Task: Removes the first occurrence of an item. Decreases the number of items by one. o Param anltem: the object to be removed o Return either the entry removed if the removal was successful, or null public void clear o Task: Removes all entries from the bag. Reset the number of items. public void display o Task: Displays all items that are in the bag, one per line, in the order in which they occur in the bag. public boolean contains(String anItem); o Task: Tests whether the bag contains a given item. O Param anltem: the object that is the desired entry Return true if the bag contains anltem, or false if not o public int count(String anItem) o Task: Determines the number of times anItem appears in a bag, O Param anltem: the object that is the desired item o Return: the number of number of times anltem appears in the bag public GroceryBag union(GroceryBag another Bag); o Task: Creates a new bag that combines the contents of the bag and anotherBag. o Param anotherBag: the Bag that is to be added o Return a combined Bag public GroceryBag intersection (GroceryBag another Bag) Task: Creates a new bag that contains those items that occur in both the bag and anotherBag without duplication Param anotherBag: the Bag that is to be compared o Return an intersection Bag Your task is to: 1. Choose the best data structure to represent the grocery bag and the items that it contains (Array, Singly Linked List, Doubly Linked List). Justify your selection. 2. Implement the class GroceryBag and Item class using your chosen data structure in Java. 3. Implement the above methods in Java. 4. Provide a test class program. In main, create two GrocerryBag objects; bag1, bag2. Provide a list of actions for the user to choose from according to the shown sample output. Make sure to test all the cases. If one case did not work as described, note that in your sample output Sample output: Welcome to the Local Food Grocery Store: Please, choose one of the following: 1) Add item to a bag 2) Remove an item from a bag 3) Clear the contents of a bag 4) Find an item in a bag 5) Find the quantity of an item in a bag 6) Find the total number of items in a bag 7) Display the contents of a bag 8) Create the union bag 9) Create the intersection bag 10) Exit 1 Which bag you want to add to, 1 or 2? 1 Enter the items ($ to stop) milk egg carrot apple carrot cheese carrot $