The definitions of stack, queue, and priority queue are not explicitly given and must be deduced with your knowledge of linked lists.

3 Linked Lists (20 points) Learning Objective 1) Consider the following linked list. For this question, you should assume that the operations as- sociated with a stack, queue, or priority queue are all implemented with best efficiency (in terms of run time and memory requirement), taking into account the properties of a linked list, as covered in the class or priority queue ae nt the properties of a (a) (4 points) The linked list at the beginning of this question is being used as a stack. We apply the following two operations on the stack consecutively. Show the resulting linked list after each operation Push(Stack, 5): Pop(Stack) (b) (4 points) The linked list at the beginning of this question is being used as a queue. We apply the following two operations on the queue consecutively. Show the resulting linked list after each operation Enqueue(Queue, 5): Dequeue(Queue) (c) (4 points) The linked list at the beginning of this question is being used as a priority queue (PQ). You have to deduce the definition of priority based on the given list. We apply the follow ing two operations on the PQ consecutively. Show the resulting linked list after each operation. PQ Enqueue(PQ. 5): PQ Dequeue(PQ: (d) (8 points) Consider an array-based implementation of singly linked list(s). The contents of the array implementing the linked list(s) are as follows: index infonext 109 5 1079 105 103 101 UnusedList index: 1 0 Among the linked lists in the array, one maintains a list of unused nodes. We refer to that list as Unused List, whose index at the moment is at position 1. The other list is the one we showed at the beginning of the question. Whenever a new node is required by some other functions (push, enqueue, or PQ.enqueue), the node is obtained from Unused List (and the index is updated). Whenever a node is deleted from a linked list and is no longer required (pop, dequeue, or PQ.dequeue), it is returned to Unused List (and the index is updated). Again, you should assume that the Unused.List is maintained with best efficiency. (d)() (2 points) Draw the UnusedList. ANS: (d)(i) (6 points) Update in the next page the contents of the array and the Unused List index after the consecutive executions of PQ-Enqueue(PQ, 5) and PQDequeue(P) in (c). All you have to do is to cross out entries that should be updated and replace them with correct values. PQ Enqueue(PQ.5) index info next 1095 0 7 107 9 Unused List index: 1 5 1054 104 103 102 3 PQ DequeuelPQ) index info next 109 5 0 7 1079 Unused,List index : 1 14 104 103 1 101