Problem
Given two queues with their standard operations (enqueue
, dequeue
, isempty
, size
), implement a stack with its standard operations (pop
, push
, isempty
, size
). The stack should be efficient when pushing an item.
Given we have queue1
and queue2
:
push – O(1)
:
- enqueue in
queue1
pop – O(n)
:
- while size of
queue1
is bigger than 1, pipe (dequeue + enqueue) dequeued items fromqueue1
intoqueue2
- dequeue and return the last item of
queue1
, then switch the names ofqueue1
andqueue2
Complexity Analysis
If queue is implemented as linked list the enqueue
operation has O(1)
time complexity.
Implementation
public Stack<E> {
private Queue<E> q1 = new Queue<E>();
private Queue<E> q2 = new Queue<E>();
public void push(E x) {
q1.enqueue(x);
}
public E pop() {
while (q1.size() > 1) {
q2.enqueue(q1.dequeue());
}
E pop = q1.dequeue();
Queue<E> temp = q1;
q1 = q2;
q2 = temp;
return pop;
}
}