Instance Attributes

Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Instance Attributes

QueueAsArray objects comprise three instance attributes--_array, _head, and _tail. The first, _array, is an array 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 (a). The instance attributes _head and _tail denote the left and right ends, respectively, of this range.

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 (b).

As shown in Figure , the leftmost element is _array[_head], and the rightmost element is _array[_tail]. When the queue contains only one element, as shown in Figure (c).

Finally, Figure (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 and . Therefore, the difference between the _head and _tail satisfies . 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 instance attributes.

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 instance attribute, _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.