Recall the SLLNode class discussed in the week 1 lectures. Consider us- ing this to implement a SLLStack and SLLQueue data structures, where SLLStack represents a stack and SLLQueue represents a queue. Both were discussed brie y in lectures and you can look at more information athttps://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.

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.]