Queues

Set A: from the module

1. Write exactly what this prints.

   LinkedQueue q = new LinkedQueue();
   q.enqueue(3);
   q.enqueue(5);
   q.enqueue(8);
   System.out.println(q.dequeue());
   System.out.println(q.peek());
   q.enqueue(1);
   System.out.println(q.size());

2. A LinkedQueue holds one node. After dequeue(), what are front and rear, and why must both change?

Set B: new problems

1. The statements run in order, starting with an empty queue. Copy the table and fill it in. The first row is done for you.

   LinkedQueue q = new LinkedQueue();
   q.enqueue(6);
   q.enqueue(14);
   q.dequeue();
   q.enqueue(9);
   q.enqueue(2);
   q.peek();
   q.dequeue();
   q.dequeue();

   Statement	Queue after (front → rear)	Value returned
   q.enqueue(6);	6	—
   q.enqueue(14);
   q.dequeue();
   q.enqueue(9);
   q.enqueue(2);
   q.peek();
   q.dequeue();
   q.dequeue();

2. A LinkedQueue holds 4, 10, 15 (front to rear). (a) After enqueue(20), which node does rear refer to, and which node's next changed? (b) Then dequeue() runs three times. Which node do front and rear refer to now?
3. Choose a stack or a queue, and give a reason: (a) a printer that prints jobs in the order they were sent; (b) a text box that removes the most recently typed letter when you press Backspace.

Readiness check (all prelim topics, from the module)

1. The list is head → 4 → 9 → 2 → 7 → null. What does this print?

   Node current = head;
   int count = 0;
   while (current != null) {
     if (current.data > 3) {
       count++;
     }
     current = current.next;
   }
   System.out.println(count);

2. Starting empty: add 1, add 2, remove, add 3, add 4, remove, remove. Which values are removed, in order, (a) if it is a stack, (b) if it is a queue? (Check it with the lab's "Same inputs" button above.)
3. Choose a stack, queue, array, or linked list, and give a reason: (a) passengers riding in the order they arrived; (b) undoing the most recent drawing stroke first; (c) looking up the score in seat 25 many times a day, in a class that never changes size.
4. True or false, with a reason: "Linked lists always insert and delete faster than arrays."

Your coding task: a queue in an array

Part 4's box "A queue in an array" kept a queue in a circular array (see the picture ). Here it is in Java, as our own class ArrayQueue. dequeue is done: it takes the value at front, then moves front to the next cell, wrapping around with %. Finish enqueue in about 6 lines where it says YOUR CODE. It does the same thing at the rear. Run it: the printed lines must match the comments.

 1public class Main {
 2  public static void main(String[] args) {
 3    ArrayQueue q = new ArrayQueue(4);
 4    q.enqueue(1);
 5    q.enqueue(2);
 6    q.enqueue(3);
 7    System.out.println(q.dequeue());  // expected: 1
 8    System.out.println(q.dequeue());  // expected: 2
 9    q.enqueue(4);
10    q.enqueue(5);                     // wraps around to cell 0
11    q.enqueue(6);                     // goes into cell 1
12    System.out.println(q.isFull());   // expected: true
13    while (!q.isEmpty()) {
14      System.out.print(q.dequeue() + " ");
15    }
16    System.out.println();             // expected: 3 4 5 6
17  }
18}
19
20class ArrayQueue {
21  int[] data;
22  int front;   // index of the front item
23  int rear;    // index of the rear item; -1 before the first enqueue
24  int count;   // number of items
25
26  ArrayQueue(int capacity) {
27    data = new int[capacity];
28    front = 0;
29    rear = -1;
30    count = 0;
31  }
32  boolean isEmpty() {
33    return count == 0;
34  }
35  boolean isFull() {
36    return count == data.length;
37  }
38  void enqueue(int value) {
39    // YOUR CODE:
40    // 1. If the queue is full, throw an IllegalStateException.
41    // 2. Move rear to the next cell, wrapping around with %.
42    // 3. Store the value there, and add 1 to count.
43
44  }
45  int dequeue() {
46    if (isEmpty()) {
47      throw new IllegalStateException("Queue underflow: empty.");
48    }
49    int value = data[front];
50    front = (front + 1) % data.length;   // move front, wrapping around
51    count--;
52    return value;
53  }
54}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

Before you write enqueue, the starter stops at the first dequeue with "Queue underflow: empty.", because nothing was added. That is expected.

 1void enqueue(int value) {
 2  if (isFull()) {
 3    throw new IllegalStateException("Queue overflow: full.");
 4  }
 5  rear = (rear + 1) % data.length;
 6  data[rear] = value;
 7  count++;
 8}