Stacks and queues - Data Structures and Problem Solving Using Java - page 600

16.1.2 queues

The easiest way to implement the queue is to store the items in an array with the
front item in the front position (i.e., array index 0). If back represents the position
of the last item in the queue, then to enqueue we merely increment back and place
the item there. The problem is that the dequeue operation is very expensive. The
reason is that, by requiring that the items be placed at the start of the array, we
force the dequeue to shift all the items one position after we remove the front item.

Storing the queue
items beginning at
the start of any
array makes
dequeueing
expensive.

Figure 16.8 shows that we can overcome this problem when performing a
dequeue by incrementing front rather than shifting all the elements. When the
queue has one element, both front and back represent the array index of that
element. Thus, for an empty queue, back must be initialized to front-1 .
This implementation ensures that both enqueue and dequeue can be per-
formed in constant time. The fundamental problem with this approach is
shown in the first line of Figure 16.9. After three more enqueue operations, we
cannot add any more items, even though the queue is not really full. Array

A dequeue is
implemented by
incrementing the
front position.

figure 16.8
Basic array
implementation of
the queue

back

makeEmpty( )

size = 0

front

back

a

enqueue(a)

size = 1

front

back

a

b

enqueue(b)

size = 2

front

back

b

dequeue( )

size = 1

front

back

dequeue( )

size = 0

front