Queue II: circular index calculation, deque, priority queue

Last week we wrote the two basic implementations of a queue. This week there are three extensions. First we work on the count-free version of the circular array and its index formulas, because the exam has pure formula questions like “front = 4, rear = 1, how many elements are there?”. Then we see the deque, which can operate at both ends, followed by the priority queue, which removes elements in priority order. Finally we follow simulations, the real use of queues.

Golden rules:

1. In a circular index everything is % cap. When going backward, add + cap first.
2. If there is no count, one cell stays empty. Empty: front == rear. Full: (rear + 1) % cap == front.
3. A deque is a double-ended queue. It can be used both like a stack and like a queue.
4. A priority queue is not FIFO. In Java the smallest comes out first.

The circular queue: without count

Last week we saw that the case front == rear can mean both empty and full, and we added a count field. The other common solution: never let the queue become completely full. One cell always stays empty, so that:

rear is again the next free slot. With capacity 5:

SlotQueue s = new SlotQueue(5);
for (int i = 1; i <= 4; i++) s.enqueue(i * 10);
System.out.println(s.raw() + " full=" + s.isFull());
s.dequeue(); s.dequeue(); s.enqueue(50); s.enqueue(60);
System.out.println(s.raw() + " full=" + s.isFull());

[10, 20, 30, 40, 0] front=0 rear=4 size=4 full=true
[60, 20, 30, 40, 50] front=2 rear=1 size=4 full=true

In the first line there is still one free cell in the array but the queue is full: (4 + 1) % 5 = 0 = front. In the second line 50 was written to index 4 and 60 to index 0; rear 1, front 2. The size is (1 − 2 + 5) % 5 = 4.

PITFALL · Why + cap? When rear wraps and falls behind front, rear - front is negative. In Java % leaves a negative result negative: (1 − 4) % 6 = −3. If you add cap first, (1 − 4 + 6) % 6 = 3, the correct size.

A solution pattern for formula questions

cap = 6, front = 4, rear = 1
size     = (1 - 4 + 6) % 6 = 3
elements: indices 4, 5, 0
full?    (1 + 1) % 6 = 2 ≠ 4 → no
the next enqueue writes to index 1, and rear becomes 2

Deque (double-ended queue)

A queue from which you can insert and remove at both ends. Read as “deck”.

If you use only addLast + pollFirst it is a queue, and if you use only addFirst + pollFirst it is a stack. Java’s ArrayDeque class is exactly this: a deque on a circular array.

Deque<Integer> d = new ArrayDeque<>();
d.addFirst(1); d.addLast(2); d.addFirst(3); d.addLast(4);
System.out.println(d);
System.out.println(d.pollLast() + " " + d.pollFirst());
d.offerFirst(9);
System.out.println(d + " peekLast=" + d.peekLast());

[3, 1, 2, 4]
4 3
[9, 1, 2] peekLast=2

Writing a deque with a circular array

front and count are kept. Adding at the end writes to cell (front + count) % cap. Adding at the front moves front back by one:

void addFirst(int x) {
    front = (front - 1 + data.length) % data.length;
    data[front] = x;
    count++;
}

void addLast(int x) {
    data[(front + count) % data.length] = x;
    count++;
}

int removeLast() {
    int idx = (front + count - 1) % data.length;
    count--;
    return data[idx];
}

With capacity 6: addLast(1), addLast(2), addFirst(3), addFirst(4):

[1, 2, 0, 0, 4, 3] front=4 count=4

When front wraps back from 0 it goes to 5 (3 was written), then to 4 (4 was written). The logical order from front: 4 3 1 2.

The priority queue

Like a hospital emergency room: you are called not by order of arrival but by urgency. Every element has a priority; remove always gives the highest-priority element. In Java, “highest priority” by default means the smallest value.

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 8, 3, 9, 2}) pq.add(x);
System.out.println("toString: " + pq);
System.out.println(pq.poll() + " " + pq.poll() + " " + pq.poll() + " size=" + pq.size());

toString: [1, 3, 2, 5, 9, 8]
1 2 3 size=3

The toString output is not sorted. A PriorityQueue keeps a heap inside; the only guarantee is that the one at the front is the smallest. If you want the largest to come out first, give a Comparator:

PriorityQueue<Integer> mx = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<String> byLen = new PriorityQueue<>((a, b) -> a.length() - b.length());

Implementation options

In this course it is enough for you to be able to write the first two. The sorted list version consists of insertSorted + removeFirst from week 3. The heap is the subject of the next course (SEN2212).

Simulation with queues

The real strength of a queue is in scenarios like “the one whose turn it is gets processed, and the one whose job isn’t finished goes to the back”.

Round-robin scheduling

The operating system distributes the processor among jobs in turn, giving each a fixed time slice (quantum). With time slice 2, jobs A (5 units), B (2), C (4):

while (!names.isEmpty()) {
    String p = names.remove();
    int run = Math.min(2, left.get(p));
    time += run;
    left.put(p, left.get(p) - run);
    if (left.get(p) > 0) names.add(p);   // if unfinished, to the back
}

A[0-2] B[2-4] (B done at 4) C[4-6] A[6-8] C[8-10] (C done at 10) A[10-11] (A done at 11)

Hot potato

Everyone is in a circle. The potato changes hands k times, and whoever is holding it is out of the game. With a queue: k times add(remove()), then one remove(). The queue version of the Josephus problem from week 3.

out: Deniz Cem Ece Bora | winner: Ali

Traversing a queue without damaging it

There is no access by index in a queue. To get the sum without changing the contents, rotate size times:

static int sumQueue(Queue<Integer> q) {
    int sum = 0, n = q.size();
    for (int i = 0; i < n; i++) { int x = q.remove(); sum += x; q.add(x); }
    return sum;
}

For [3, 6, 9, 12] it returns 30 and the queue stays in the same order. It is important to take the loop bound into a variable n beforehand; i < q.size() also works in this example because the size doesn’t change, but it misleads in variations that remove elements.

Common mistakes

Deque<Integer> d = new ArrayDeque<>();
d.addFirst(1); d.addLast(2); d.addFirst(3); d.addLast(4);
System.out.println(d);
System.out.println(d.pollLast() + " " + d.pollFirst());
d.offerFirst(9);
System.out.println(d + " peekLast=" + d.peekLast());

static boolean isPalindrome(String s) {
    Deque<Character> d = new ArrayDeque<>();
    for (char c : s.toCharArray()) d.addLast(c);
    while (d.size() > 1) {
        if (d.pollFirst() != d.pollLast()) return false;
    }
    return true;
}

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 8, 3, 9, 2}) pq.add(x);
System.out.println(pq.poll() + " " + pq.poll() + " " + pq.poll() + " size=" + pq.size());

PriorityQueue<Integer> mx = new PriorityQueue<>(Comparator.reverseOrder());
mx.add(4); mx.add(10); mx.add(7);
System.out.println(mx.peek());
mx.poll(); mx.add(6);
while (!mx.isEmpty()) System.out.print(mx.poll() + " ");

time    running   after run         queue
0-2     A         A:3               B C A
2-4     B         B:0 done (4)      C A
4-6     C         C:2               A C
6-8     A         A:1               C A
8-10    C         C:0 done (10)     A
10-11   A         A:0 done (11)