Requirements:

In this sub-project, you will implement one class:

1. Dynamic Queue: Dynamic_queue.

A queue stores objects in an ordered list and allows insertions at one end and deletions from the other end of the list in O(1) time.

The objects in this queue are stored in an array. The capacity of the array may be changed depending on the number of objects currently stored in the array, according to the following two rules:

• If an object is being inserted into a queue where the array is already full, the capacity of the array is doubled.
• If, after removing an object from a queue where the number of objects is one-quarter (1/4) the capacity of the array, then the capacity of the array is halved. The capacity of the array may not be reduced below the initially specified capacity.

Runtime:

The amortized run time of each member function is specified in parentheses at the end of the description. Projects which do not satisfy the run time requirements will be required to resubmit.

Class Specifications:

---

Dynamic_queue

Description

A class which implements a queue using an array. The capacity of the array may be changed dynamically after insertions or deletions. For run-time requirements, the number of objects in the queue is n.

Member Variables

The class at least six suggested member variables:

• A pointer to an instance of Type, Type *array, to be used as an array,
• A head index int ihead,
• A tail index int itail,
• A counter int entry_count,
• The initial capacity of the array, int initial_capacity, and
• The current capacity of the array, int array_capacity.

You may chose to use these or use whatever other member variables you want. You do not have to use all of these member variables—it is possible to implement this class using two of the three integer member variables; however, this requires more computation for the individual member functions.

Member Functions

Constructors

Dynamic_queue( int n = 10 )

The constructor takes as an argument the initial capacity of the array and allocates memory for that array. If the argument is either 0 or a negative integer, set the initial capacity of the array to 1. The default initial capacity of the array is 10. Other member variables are assigned as appropriate.

Destructor

~Dynamic_queue()

The destructor deletes the memory allocated for the array.

Copy Constructor

Dynamic_queue( Dynamic_queue const & )

The copy constructor creates a new instance of the queue. (O(n))

Accessors

This class has four accessors:

Type head() const

Return the object at the head of the queue (the object that would be removed by Type dequeue()). It may throw a underflow exception). (O(1))

int size() const

Returns the number of objects currently stored in the queue. (O(1))

bool empty() const

Returns true if the queue is empty, false otherwise. (O(1))

int capacity() const

Returns the current capacity of the queue. (O(1))

Mutators

This class has five mutators:

void swap( Dynamic_queue & );

The swap function swaps all the member variables of this queue with those of the argument. (O(1))

Dynamic_queue &operator=( Dynamic_queue & );

The argument is a copy of the right-hand side of the operator. Swap the member variables of this with that copy.

void enqueue( Type const & )

Insert the argument at the tail of the queue. If the array is full before the argument is placed into the queue, the capacity of the array is first doubled. (O(1) on average)

Type dequeue()

Removes the object at the head of the queue. If, after the object is removed, the array is one-quarter (1/4) full and the array capacity is greater than the initial capacity, the capacity of the array is halved. This will throw the underflow exception if the queue is empty. (O(1) on average)

void clear()

Empties the queue by resetting the member variables. The array is resized to the initial capacity. (O(1))

Friends

The class has one friend: the operation cout << queue. Because the structure of the internal queue is unknown, nothing is implemented here; however, you could add an implementation which allows you to print the entries of your queue.