Requirements:

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

1. Queue: 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 Θ(1) time.

The objects in this queue are stored in a fixed-capacity array.

Runtime:

The 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:

Queue

Description

A class which implements a queue using an array. 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 front index int ifront,
• A tail index int itail,
• A counter int entry_count, and
• The capacity of the array, int array_capacity.

You may chose to use these or use whatever other member variables you want.

Member Functions

Constructors

Queue( int n = 10 )

The constructor takes as an argument the 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 is 10. Other member variables are assigned as appropriate.

Destructor

~Queue()

The destructor deletes the memory allocated for the array.

Copy Constructor

Queue( Queue const & )

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

Accessors

This class has four accessors:

Type front() const

Return the object at the front of the queue (the object that would be removed by Type pop()). It may throw an underflow exception. (Θ(1))

int size() const

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

bool empty() const

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

int capacity() const

Returns the capacity of the queue (the capacity of the array). (Θ(1))

Mutators

This class has three mutators:

void swap( Queue & );

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

Queue &operator=( Queue & );

The assignment operator makes a copy of the argument and then swaps the member variables of this node with those of the copy. (O(max{n_lhs, n_rhs}))

void push( Type const & )

Insert the argument at the tail of the queue. If the array is full before the argument is placed into the queue, an overflow exception is thrown. (Θ(1))

Type pop()

Removes the object at the front of the queue. This may throw an underflow exception. (Θ(1) on average)

void clear()

Empties the queue by resetting the member variables. (Θ(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.