Submission: Please submit the solution to this exercise in iLearn by the due date. Recall the SLLNode class discussed in the week 1 lectures. Consider using this to implement a SLLStack and SLLQueue data structures, where SLLStack represents a stack and SLLQueue represents a queue. Both were discussed briefly in lectures and you can look at more information at https://en.wikipedia.org/wiki/Stack_(abstract_data_type) and https: //en.wikipedia.org/wiki/Queue_(abstract_data_type). A basic set up for each is as follows: class SLLStack { SLLNode top= null; // Records the top element of the stack SLLStack () { // Default constructor } void sPush(Object x) { ... } // Creates a SLLNode containing // x and adds it to the top of the stack Object sPop() {...} // Removes the top node (if it exists) of the stack // and returns the value (of the removed node) } class SLLQueue { SLLNode tail= null; // Records the last element (tail) of the queue SLLQueue () { // Default constructor } void qPush(Object x) { ... } // Creates a SLLNode containing // x and joins it to the tail of the queue Object qPop() {...} // Removes the head node (if it exists) of the // queue and returns the value (of the removed node) } (a) Draw (successive) diagrams of a stack after each call of sPop, sPush. Indicate where the pointer top is after each method call. 10 SLLStack myStack= SLLStack(); myStack.sPush(1); myStack.sPush(2); myStack.sPush(3); int x= myStack.sPop();

(b) Draw (successive) diagrams of a stack after each call of qPop, qPush. Indicate where the pointer tail is after each method call. SLLStack myQueue= SLLQueue(); myQueue.qPush(1); myQueue.qPush(2); myQueue.qPush(3); int x= myQueue.qPop();

(c) Consider implementing the qPop method using the given specification of the SLLQueue class given. Write down a problem with the given specification that could cause performance issues in large queues. Suggest a simple improvement to the given design which would mitigate the problem you have identified. [Note: You do not need to provide an implementation.]