CSCI373 Dynamic Queue

Problem Description

Queue ADT is sequence containers with dynamic sizes that can be expanded or contracted following the first-in first-out (FIFO) scheme. A queue stores elements in a linear list and allows insertions at the back and deletions at the front end of the list in O(1) time.

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

1.If an element is being inserted into a queue where the array is already full, the capacity of the array is doubled.

2.If, after removing an element from a queue where the number of elements is 1/4 the capacity of the array or less, then the capacity of the array is halved. The capacity of the array may not be reduced below the initially specified capacity.

Task

Implement and override necessary methods to achieve the dynamic queue growth/shrink as described above.

• Bonus: Implement copy and move constructors

Runtime

The amortized run time of each member function is specified in parentheses at the end of the description.

Class Specifications

UML Class Diagram see image.

A skeleton for this class is provided in the source directory in the file DynamicQueue.h.

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 elements in the queue is n.

Member Variables

The DynamicQueue class has at least one member variable:

• The initial capacity of the storage array, int initial_array_capacity

And it also inherits five member variables:

• A pointer to an instance of Type, Type *elements, to be used as a storage array,
• A front index, int ifront,
• A back index, int iback,
• A size variable, int queue_size,
• The current capacity of the storage array, int array_capacity.

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

Member Functions

Constructor

DynamicQueue( int n = 4 )

The constructor takes as an argument the initial capacity of the array and allocates memory for that array. The initial array capacity must be 4 or more, with a default capacity of 4. If the user passes a value less than 4, use 4. Other member variables are assigned as appropriate.

Destructor

~DynamicQueue()

The destructor deletes the memory allocated for the storage array.

Copy Constructor

DynamicQueue( cont DynamicQueue & )

The copy constructor creates a new instance of the queue. The initial capacity of the copy is still the initial capacity of the queue being copied. (O(n))

Move Constructor

DynamicQueue( DynamicQueue && )

The move constructor creates an empty queue (one that can be deleted) and calls swap. (O(1))

Accessors

This class has five inherited accessors:

Type front() const

Return the object at the front of the queue. Throw an underflow exception if the queue is empty. (O(1))

Type back() const

Return the object at the back of the queue. Throw an underflow exception if the queue is empty. (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 storage array. (O(1))

Mutators

This class has at least two mutators:

void push( const Type& obj )

Insert the new element at the back of the queue. If before the element is placed into the queue, the array is filled, the capacity of the array is doubled. (O(1) on average)

Type pop()

Removes the element at the front of the queue. If, after the element is removed, the array is 1/4 full or less and the array capacity is greater than the initial capacity, the capacity of the array is halved. This may throw a underflow exception. (O(1) on average)

void clear()

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

void swap( DynamicQueue & )

The swap function swaps all the member variables of this queue with those of the argument. (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.

Test Driver Program

Test your solution by running series of provided tests, see file testfile.txt. Look for additional test files in the text format in the source code directory.

Test Driver Commands

See QueueTester.h file for more detailed description.