Notes 8:
Addendum to Essentials of Data Structures, Cpt 8

Math 61 -- D. C. Smolarski, S.J.
Santa Clara University, Department of Mathematics and Computer Science

Contents

• Queues
• Queue Class Specification
• Presuppositions and Resolutions of Issues
• Code for Functions

Queues

Queue Class Specification

Ford & Topp (Cpt 5, pg 204ff) gives a specification of the Abstract Data Type queue in this way:

Data will be stored in an array of size determined by the parameter MaxQSize, and will be indexed by two pointers, front and rear. Ford & Topp also make use of an integer variable count which indicates the number of items stored in the queue.

The operations include the standard:

• QInsert (or "enqueue" or "insert") which inserts an item into the queue at the rear (a procedure);
• QDelete (or "dequeue" or "remove") which removes an item from the front of the queue (a function);
• QEmpty which tests to see whether the queue is empty (a function).

• Queue, which is the initializing constructor;
• ClearQueue which removes all items from the queue and resets it;
• QFront which copies the value of the item at the front of the queue and returns this value, but does not delete the item from the queue;
• QLength which determines how many items are in the queue;
• QFull which determines whether the queue is at its maximum capacity.

Presuppositons and Resolutions of Issues

Ford & Topp resolves the design issues as follows:

1. Once inserted, an item is not moved in the queue;
2. The array is thought of as circular (cf. F&T, p 210), i.e., after qlist[MaxQSize-1] comes qlist[0]. Therefore, front (and rear) can also be increased to the next legal number by using the formula front = (front+1)%MaxQSize (cf. F&T, pp 210, 212, 213).
3. front is the index of the array element that actually is the first element in the queue (different from Essentials of D.S.) (cf. F&T, pg 213). (This assumes that there actually still is an item in the queue.) rear is the index of the next location available to insert an item in the array (normally one higher than the location of the last item in the array) (cf. pg. 212).

   NOTE: This means that if front equals rear one can either have an empty queue waiting to have an element inserted, or a full queue.

4. Testing for emptiness (and overflow) is accomplished by checking the value of the class variable count. If count == 0 the queue is empty, but if count == MaxQSize the queue is full.

   NOTE: These implementation choices mean that we do not have to sacrifice an element of the underlying storage array and, thus, that every element of the array can be used to store a queue element.

Code for Functions

Function QEmpty

     int Queue::QEmpty(void) const
     {
         return count == 0;
     }

     void Queue::QInsert (const DataType & item)
     {
        // terminate if queue is full
	if (count == MaxQSize)
	{
	   cerr << "Queue overflow!" << endl;
	   exit(1);
	}
	// increment count, assign item to qlist
	// and update rear
	count++;
	qlist[rear] = item;
	rear = (rear+1) % MaxQSize;
     }

See F&T, p. 213 for array implementation version.

For a pointer version of the function, we can use the following:

     int remove(node * & q)
     {
        int temp;
        node * p;
        if ( q == NULL)
        {
	    cerr << "queue underflow" << endl;
	    exit(1);
        }
        else
        {
	   p = q;
	   q = q->next;
	   temp = p->data;
	   delete p;
	   return temp;
        }
     }

This page is maintained by Dennis C. Smolarski, S.J.
© Copyright 1998, 1999, 2000 Dennis C. Smolarski, SJ, All rights reserved.
Last changed: 27 January 2000.