In this task, you are asked to create a generic stack data structure that stores its objects using the Linked-list representation. In particular, you need to implement a generic class called "Stack" that maintains the necessary state variables (i.e. private attributes) to represent the data using a Linked list, and that implements the following methods: A Default Constructor: The constructor should initialize an empty stack using the Linked-list data representation. The default constructor should initialize an empty stack. The push method: The methods accepts as an input a generic type object and add it to the stack as its topmost element. The push method must handle all necessary bookkeeping to add a new object to the underlying Linked-list and enforce the Last-in First-out policy The pop method: The method accepts no input, and returns a reference to the topmost element in the stack as a generic type object, and removes that element from the stack. The pop method must handle all necessary bookkeeping to remove the appropriate element from the stack and enforce the Last-in First-out policy The size method: The method should return an integer indicating the number of elements currently stored in the stack. For this, you will need to maintain an appropriate attribute in the class to keep track of the elements in the Stack. The running time of this method should be in the order of O(1) (i.e. constant time). Task 2: Implement a Generic Queue Data Structures from scratch. In this task, you are asked to create a generic Queue data structure that stores its objects using the Linked-list representation. In particular, you need to implement a generic class called "Queue" that maintains all necessary state variables (i.e. private attributes) to represent the data using a Linked list, and that implements the following methods: The top method: The method accepts no input and returns a reference to the topmost element in the stack sa generic type object stored in the stack. The method must not remove the element from the stack. The isEmpty method: The method should return True in the Stack is empty, False otherwise. A Default Constructor: The constructor should initialize an empty Queue using the Linked-list data representation. The default constructor should initialize an empty Queue. The enqueue method: The methods accepts as an input a generic object type and add it to the queue at the tail of the queue. The enqueue method must handle all necessary bookkeeping to add a new object to the underlying Linked-list and enforce the First-in First-out policy (as discussed in the lectures). The dequeue method: The method accepts no input and returns a reference to the frontmost element in the queue (i.e. the head element) as a generic object, and it removes that element from the stack. The dequeue method must handle all necessary bookkeeping to remove the appropriate element from the queue and enforce the First-in First-out policy (as discussed in the lectures). The peek method: The method accepts no input and returns a reference to the frontmost element in the queue as generic object (i.e. the generic object type stored in the queue). The method must not remove the element from the stack. The isEmpty method: The method should return True in the Queueis empty, False otherwise. The size method: The method should return an integer indicating the number of elements currently stored in the Queue. For this, you will need to maintain an appropriate attribute in the class to keep track of the elements in the Queue. The running time of this method should be in the order of O(1) (i.e. constant time). Notice: Implement the genetic Node class: For the implementation of both Task 1 and Task 2, you need to also implement the generic Node class. This class should be used internally by the Stack and Queue classes to maintain a Linked-list representation of the data store. However, the consumer of the Stack and Queue data structures (i.e. the main method in the problem set example) should not need to know about or use the Node class. Refer the lecture notes on Stack, Queues and Linked list on how the Node class can be defined. You can use the same implementation from your previous problem sets implementing the generic Node class. Task 3: Demonstrate the correctness of your Linked-List implementation Create a Main.java class to demonstrate the correct implementation and use of the Stack and Queue classes. As part of the main method of the Main class implement the following use-case: Demonstrate the correctness of Stack class: Create a new instance of the Stack class in a variable called myStack. Test if the Stack is empty by invoking the isEmpty method; Display the message "Stack is empty" if the return value of the isEmpty method is True. Create four instances of User objects with their userid set to 100,200, 300, and 400 respectively, choose values for each user's name and age. Use the User object you created as part of the previous problem set. Add each of the four instances to the Stack in order, using the push method. Use the top method to get a reference to the top-most element in the stack, and print its content (i.e. its user id, and user name) in a single line. O O O 00 O O Invoke the size method and display its output on the console with the message "Total elements in the stack: %d"; replace "%d" with the returned value of the size method. Use the pop method to remove an element from the stack, and print the content of the removed element. Invoke the size method and display its output on the console with the message "Total elements in the stack: %d"; replace "%d" with the returned value of the size method. Use the pop method again to remove an element from the stack, and print the content of the removed element. O O O O O O O Invoke the size method and display its output on the console with the message "Total elements in the stack: %d"; replace "%d" with the returned value of the size method. Use the pop method again to remove an element from the stack, and print the content of the removed element. O O Invoke the size method and display its output on the console with the message "Total elements in the stack: %d"; replace "%d" with the returned value of the size method. Use the pop method a fourth time to remove an element from the stack (if any), and print the content of the removed element (if any). Demonstrate the correctness of Queue class: Create a new instance of the Queue class in a variable called myQueue. Test if the Queue is empty by invoking the isEmpty method; Display the message "Queue is empty" if the return value of the isEmpty method is True; display "Queue is not empty" otherwise. O O O O O O O O O O Create four instances of User objects with their userid set to 100,200, 300, and 400 respectively, choose values for each user's name and age. Use the User object you created as part of the previous problem set. Add each of the four instances to the Queue in order, using the enqueue method. Use the peek method to get a reference to the frontmost element in the Queue, and print its content (i.e. its user id, and user name) in a single line. Invoke the size method and display its output on the console with the message "Total elements in the queue: %d"; replace "%d" with the returned value of the size method. Use the dequeue method to remove an element from the queue, and print the content of the removed element. Invoke the size method and display its output on the console with the message "Total elements in the queue: %d"; replace "%d" with the returned value of the size method. Use the dequeue method again to remove an element from the queue, and print the content of the removed element. Invoke the size method and display its output on the console with the message "Total elements in the queue: %d"; replace "%d" with the returned value of the size method. Use the dequeue method again to remove an element from the queue, and print the content of the removed element. Invoke the size method and display its output on the console with the message "Total elements in the queue: %d"; replace "%d" with the returned value of the size method. Use the dequeue method a fourth time to remove an element from the queue (if any), and print the content of the removed element (if any). Program Requirement Your implementation for the above program should comply with the following requirements and specifications: Your program should implement all the specification outlined above. Your code implementation should be efficient; unnecessary computations or unnecessary use of memory will be penalized. Do not use any helper methods/functions other than those requested. Your code must be well organized, code must be indented. You must use the data file provided as input to your program (if any provided). Source code files must be submitted (not the compiled files) You must use the template code provided (if provided). Your program must compile and run without errors and generate the expected output. Deliverables: You must submit your implementation in the files: User.java (from previous problem set), Node.java, Stack.java, Queue.java, the Main.java, an output screen showing your code executing and complete the Submission Cover Page for this assignment as listed on the LMS.