Queue Problems
Now let's apply queues to solve classic problems. These problems demonstrate the power of queue data structure.
1. Implement Stack using Queues
Implement a stack (LIFO) using two queues. Push: O(1), Pop: O(n).
public class StackUsingQueues {
private Queue q1 = new LinkedList<>();
private Queue q2 = new LinkedList<>();
public void push(int x) {
q2.add(x);
while (!q1.isEmpty()) {
q2.add(q1.poll());
}
Queue temp = q1;
q1 = q2;
q2 = temp;
}
public int pop() {
if (q1.isEmpty()) throw new RuntimeException();
return q1.poll();
}
}
2. Implement Queue using Stacks
Two stacks: one for enqueue, one for dequeue (amortized O(1) for both).
public class QueueUsingStacks {
private Stack s1 = new Stack<>();
private Stack s2 = new Stack<>();
public void enqueue(int x) {
s1.push(x);
}
public int dequeue() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
if (s2.isEmpty()) throw new RuntimeException();
return s2.pop();
}
}
3. Generate Binary Numbers from 1 to n
Use queue to generate binary numbers: start with "1", then for each, append "0" and "1".
public static List generateBinary(int n) {
List result = new ArrayList<>();
Queue queue = new LinkedList<>();
queue.offer("1");
for (int i = 0; i < n; i++) {
String binary = queue.poll();
result.add(binary);
queue.offer(binary + "0");
queue.offer(binary + "1");
}
return result;
}
Two Minute Drill
- Queue can simulate stack (push O(1), pop O(n)) and vice versa.
- Generate binary numbers using BFS with queue.
- These problems are common in interviews.
- Queues are also used in BFS and level-order tree traversal.
Need more clarification?
Drop us an email at career@quipoinfotech.com