Question

2. Consider a circular array based Queue as we have discussed in the lectures (class definition given below for reference) public class CircArrayQueue<E> implements Queue<E private EI Q private int front-0 indicates front of queue l indicates position after end of queue private int end-0: public CircArrayQueue( public int getSize (.. public boolean isEmpty ( public void enqueue (E e)... public E dequeue ) throws EmptyQueueException... Il constructor We are interested in implementing a Stack class based on the above CircArrayQueue definition as follows: public class Stack<E>{ private CircArrayQueue<E> data new CircArrayQueue<E>0 public boolean isEmpty ( public E top( public void push (E e... public E pop (.. Keep in mind that in the Stack class you can only manipulate the "data" through the public methods of the CircArrayQueue class. Assume there are no overflows possible in the CircArrayQueue. You are not permitted to add any members or methods to the Stack class. a) Provide the Java code for an implementation of push) with worst additional space complexity (1). Justify the run time and space complexity of your algorithm. Assume case run time complexity e(1) and n is the number of elements in the Stack. (2+1 marks) b) Provide the Java code for an implementation of pop) with worst case run time complexity e(n) and additional space complexity (1)? Justify the run time and space complexity of your algorithm. Assume n is the number of elements in the Stack. (2+1 marks)

Answer 1

Answer:

public void push(E e) {
data.enqueue(e); // O(1) operation, it just puts the data to the end of the queue..
}

public E pop() {
// assuming pop is only called for non-empty stack, else we need to raise an exception.

// First dequeue the start (n-1) entries and then enqueue them in the same queue back.
int size = data.getSize();
for(int i=0; i<size-1; i++) {
data.enqueue(data.dequeue());
}

// So now, starting (N-1) elements have come to the back of the queue in their
// orders preserved.

// Now dequeue the Nth element, which is at front end now.
return data.dequeue();
}