Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Fields

QueueAsArray objects comprise three fields--array, head, and tail. The first, array, is an array of objects that is used to hold the contents of the queue. The objects contained in the queue will be held in a contiguous range of array elements as shown in Figure gif (a). The fields head and tail denote the left and right ends, respectively, of this range.

   figure6406
Figure: Array implementation of a queue.

In general, the region of contiguous elements will not necessarily occupy the leftmost array positions. As elements are deleted at the head, the position of the left end will change. Similarly, as elements are added at the tail, the position of the right end will change. In some circumstances, the contiguous region of elements will wrap around the ends of the array as shown in Figure gif (b).

As shown in Figure gif, the leftmost element is array[head], and the rightmost element is array[tail]. When the queue contains only one element, tex2html_wrap_inline60573 as shown in Figure gif (c).

Finally, Figure gif (b) shows that if the queue is empty, the head position will actually be to the right of the tail position. However, this is also the situation which arises when the queue is completely full! The problem is essentially this: Given an array of length n, then tex2html_wrap_inline60577 and tex2html_wrap_inline60579. Therefore, the difference between the head and tail satisfies tex2html_wrap_inline60581. Since there are only n distinct differences, there can be only n distinct queue lengths, 0, 1, ..., n-1. It is not possible to distinguish the queue which is empty from the queue which has n elements solely on the basis of the head and tail fields.

There are two options for dealing with this problem: The first is to limit the number of elements in the queue to be at most n-1. The second is to use another field, count, to keep track explicitly of the actual number of elements in the queue rather than to infer the number from the head and tail variables. The second approach has been adopted in the implementation given below.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.