Consider providing an implementation for the Queue ADT abstr

Consider providing an implementation for the Queue ADT (abstract data type) that uses a stack as the underlying data structure. Provide an implementation for the enqueue and dequeue operations. One of these should use recursion. What is the time complexity for these operations?

Solution

Hi, Please find my implementtion.

A Queue class using only one Stack, would be as follows:

import java.util.Stack;
public class Queue<E> {

private Stack<E> stack = new Stack<E>();

public void enqueue(E elem) {
//The new element will be on the bottom of the stack,
//and the oldest element is on top (first to be popped)
if (!stack.empty()) {
E topElem = stack.pop();
insert(elem);
stack.push(topElem);
}
else
stack.push(elem);
}

public E dequeue() {
return stack.pop();
}
}

Time Complexity:

Dequeue: O(1)
Enqueue: O(n)