Oracle Interview Question
Financial Software DevelopersCountry: India
Interview Type: In-Person
public class StackUsingQueue {
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
public void pop() {
while (q1.size() > 1)
q2.add(q1.poll());
System.out.println("POPped:" + q1.poll());
while (!q2.isEmpty())
q1.add(q2.poll());
}
public void push(int val) {
System.out.println("PUSHed:" + val);
q1.add(val);
}
/**
* @param args
*/
public static void main(String[] args) {
StackUsingQueue suq = new StackUsingQueue();
suq.push(5);
suq.push(4);
suq.push(3);
suq.push(2);
suq.push(1);
suq.pop();
suq.push(6);
suq.pop();
suq.pop();
suq.pop();
}
}
I would say just use 2 queues. Assume you are inserting 1, 2, 3, 4, 5 (in this order). Assume one of the queues has 4, 3, 2, 1 already when you are trying to insert 5. First insert this 5 to the other queue, then keep removing each element from the other queue and insert it to this one. You will then end up with 5, 4, 3, 2, 1 in one queue and another empty queue.
- Sunny February 10, 2014This is inefficient because it requires O(n) for each insert.