Queue transformations

Reversing a stack's contents once turns LIFO into FIFO. Keep an in stack that receives every enqueue and an out stack that serves every dequeue. When out is empty, pop everything from in and push it onto out: the oldest value ends up on top. Values already in out are always older than any value in in, so the order is right.

A single dequeue can move many values, but each value moves across at most once, so over a run of operations the cost is O(1) amortised per operation. The animation shows the moves, and the final message counts them.

1class QueueFromStacks {
2    private final Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
3    void enqueue(int x) { in.push(x); }
4    int dequeue() {
5        if (out.isEmpty())
6            while (!in.isEmpty()) out.push(in.pop());     // reverses the order, once per batch
7        return out.pop();
8    }
9}

1class QueueFromStacks {
2    private final Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
3    void enqueue(int x) { in.push(x); }
4    int dequeue() {
5        if (out.isEmpty())
6            while (!in.isEmpty()) out.push(in.pop());     // reverses the order, once per batch
7        return out.pop();
8    }
9}

A stack needs the newest value to leave first, but a queue serves the oldest. The usual fix is to make push expensive: after adding the new value, rotate the queue by moving every older value behind it, so the new value is at the front. Then pop is a plain dequeue.

With one queue the rotation is size - 1 times offer(poll()); with two queues the values are shuffled between them. Either way push costs O(n) and pop costs O(1). The animation “Push, pop, push” uses the single-queue form.

1class StackFromQueue {
2    private final Queue<Integer> q = new ArrayDeque<>();
3    void push(int x) {
4        q.offer(x);
5        for (int i = 0; i < q.size() - 1; i++) q.offer(q.poll());    // move all older values behind x
6    }
7    int pop() { return q.remove(); }                                  // the newest value is at the front
8    int top() { return q.element(); }
9}

1class StackUsingQueue {
2    private final Queue<Integer> q = new ArrayDeque<>();           // the front of the queue is the top of the stack
3    void push(int x) {
4        q.offer(x);
5        for (int i = 0; i < q.size() - 1; i++) q.offer(q.poll());   // rotate: the new element moves to the front
6    }
7    int pop() { return q.poll(); }                                  // O(1)
8    int top() { return q.peek(); }
9}

Rotating a queue by k moves the front value to the rear k times: q.offer(q.poll()). Rotating by the queue size changes nothing, so only k % size rotations are needed. A rotation by k leaves the values in the same cyclic order, shifted k places.

The cost is k % size poll/offer pairs, at most size - 1. Try the “k > size” preset to see that 6 rotations of a 4-element queue equal 2.

1static void rotate(Queue<Integer> q, int k) {
2    int times = k % q.size();                     // a full turn changes nothing
3    for (int i = 0; i < times; i++)
4        q.offer(q.poll());                        // front goes to the rear
5}

1static void rotate(Queue<Integer> q, int k) {
2    int times = k % q.size();                     // a full turn changes nothing
3    for (int i = 0; i < times; i++)
4        q.offer(q.poll());                        // front goes to the rear
5}

A queue cannot be reversed in place using only enqueue and dequeue, but a stack can do it: move every value from the queue onto a stack (the front ends up deepest), then move them back (the old rear is now popped first and becomes the new front). It is O(n) time and O(n) extra space.

A recursive version does the same with the call stack: dequeue the front, reverse the rest, enqueue the saved value at the end.

1static void reverse(Queue<Integer> q) {
2    Deque<Integer> stack = new ArrayDeque<>();
3    while (!q.isEmpty()) stack.push(q.poll());       // front first in, so the front ends deepest
4    while (!stack.isEmpty()) q.offer(stack.pop());   // top first out: the old rear is now the front
5}

1static void reverse(Queue<Integer> q) {
2    Deque<Integer> stack = new ArrayDeque<>();
3    while (!q.isEmpty()) stack.push(q.poll());   // front first in, so front ends deepest
4    while (!stack.isEmpty()) q.offer(stack.pop());   // top first out: the old rear is now the front
5}

Given a stream of characters, report after each character the first one that has appeared exactly once so far. Keep a count per character and a queue of candidates in arrival order. A new character joins the queue; before answering, remove characters from the *front* while their count is above 1. The front is then the answer, or # if the queue is empty.

The removal is lazy: a repeated character stays in the queue until it reaches the front. Each character enters once and leaves at most once, so the whole stream is O(n). Try “Late survivor” (abbacd): the answer changes from a to # and later to c.

1static String firstNonRepeating(String s) {
2    int[] count = new int[26];
3    Deque<Character> q = new ArrayDeque<>();
4    StringBuilder out = new StringBuilder();
5    for (char c : s.toCharArray()) {
6        if (++count[c - 'a'] == 1) q.addLast(c);                                // first sighting: a candidate
7        while (!q.isEmpty() && count[q.peekFirst() - 'a'] > 1) q.pollFirst();   // drop repeats at the front
8        out.append(q.isEmpty() ? '#' : q.peekFirst());
9    }
10    return out.toString();
11}

1static String firstNonRepeating(String s) {
2    int[] count = new int[26];
3    Deque<Character> q = new ArrayDeque<>();
4    StringBuilder out = new StringBuilder();
5    for (char c : s.toCharArray()) {
6        if (++count[c - 'a'] == 1) q.addLast(c);                                // first sighting: a candidate
7        while (!q.isEmpty() && count[q.peekFirst() - 'a'] > 1) q.pollFirst();   // drop repeats at the front
8        out.append(q.isEmpty() ? '#' : q.peekFirst());
9    }
10    return out.toString();
11}