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

Since we are using an array, we will need to know its size in order to declare it. We will need to have some
information about the problem to determine a reasonable size for the array. We will use the symbolic constant MaxQ . In
our implementation, the queue will be declared full if there are MaxQ-1 elements in it and we attempt to add another.
We begin to define the class Queue as follows:

public class Queue {
final static int MaxQ = 100;
int head = 0, tail = 0;
int[] QA = new int[MaxQ];
...

Valid values for head and tail will range from 0 to MaxQ-1 . When we initialize a queue, we will set head and tail
to 0 ; later, we will see why this is a good value.
As usual, we can create an empty queue, Q , with this:

Queue Q = new Queue();

When this statement is executed, the situation in memory can be represented as shown in Figure 4-5 .

Q

head 0 0

tail

Q

0 1 2 3 4 5

Figure 4-5. Array representation of a queue

This represents the empty queue. In working with queues, we will need a function that tells us whether a queue is
empty. We can use the following:

public boolean empty() {
return head == tail;
}

Shortly, we will see that given the way we will implement the enqueue and dequeue operations, the queue will be
empty whenever head and tail have the same value. This value will not necessarily be 0 . In fact, it may be any of the
values from 0 to MaxQ-1 , the valid subscripts of QA .
Consider how we might add an item to the queue. In a real queue, a person joins at the tail. We will do the same
here by incrementing tail and storing the item at the location indicated by tail .
For example, to add 36 , say, to the queue, we increment tail to 1 and store 36 in QA[1] ; head remains at 0 .
If we then add 15 to the queue, it will be stored in QA[2] and tail will be 2 .
If we now add 52 to the queue, it will be stored in QA[3] and tail will be 3 .
Our picture in memory will look like Figure 4-6 .