Stacks and Queues - Advanced Topics in Java: Core Concepts in Data Structures - page 132

We can now write enqueue , an instance method to add an item to the queue.

public void enqueue(int n) {
tail = (tail + 1) % MaxQ; //increment tail circularly
if (tail == head) {
System.out.printf("\nQueue is full\n");
System.exit(1);
}
QA[tail] = n;
} //end enqueue

We first increment tail . If, by doing so, it has the same value as head , we declare that the queue is full. If not, we
store the new item in position tail .
Consider Figure 4-7 . If we delete 15 and 52 , it changes to Figure 4-8 .

Q

head

3 tail 4

QA 36 15 52 23

0 1 2 3 4 5

Figure 4-8. Queue after removing 15, 52

Now, head has the value 3 , tail has the value 4 , and there is one item, 23 , in the queue at location 4 . If we delete
this last item, head and tail would both have the value 4 and the queue would be empty. This suggests that we have
an empty queue when head has the same value as tail .
But wait! Didn't we just say that the queue is full when head and tail have the same value? True, but there's a
difference. At any time, if head == tail , the queue is empty . However, if after incrementing tail to add an item it
becomes the same as head , then the queue is full.
We can now write dequeue , a method that removes an item from the queue.

public int dequeue() {
if (this.empty()) {
System.out.printf("\nAttempt to remove from an empty queue\n");
System.exit(2);
}
head = (head + 1) % MaxQ; //increment head circularly
return QA[head];
} //end dequeue

If the queue is empty, an error is reported, and the program is halted. If not, we increment head and return the
value in location head . Note, again, that if head has the value MaxQ -1 , incrementing it sets it to 0 .
To test our queue operations, we write Program P4.7, which reads an integer and prints its digits in reverse order.
For example, if 12345 is read, the program prints 54321 . The digits are extracted, from the right, and stored in a queue.
The items in the queue are taken off, one at a time, and printed.