Requirements:

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

1. Dynamic Range Stack: Dynamic_range_stack.

A range stack maintains the range of values stored in a stack as well as the entries themselves. Thus, it is possible to call top() to return the top of the stack, but it is also possible to call maximum(), which returns the maximum element in the stack, and minimum(), which returns the minimum element in the stack. All operations must occur in time.

Runtime:

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

Class Specifications:

Dynamic_range_stack

Description

A class which implements a dynamic range stack (in fact, three stacks) which has the specified behaviours. For run-time requirements, the number of elements in the stacks is n. You may use the std::max and std::min functions.

Member Variables

The class has six members:

• An integer storing the initial size of the array: initial_size.
• An integer storing the current size of the array: array_size.
• An integer storing the number of elements in the stack: entry_count.
• Three arrays of size of size array_size: stack_array, maximum_array, and minimum_array.

Member Functions

Constructors

Dynamic_range_stack( int n = 10 )

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

Destructor

~Dynamic_range_stack()

The destructor deletes the memory allocated for the arrays.

Copy Constructor

Dynamic_range_stack( Dynamic_range_stack const & )

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

Accessors

This class has six accessors:

Type top() const

Return the object at the top of the stack (stack_array). It may throw a underflow exception. ()

Type maximum() const

Return the maximum object currently in the stack. It may throw a underflow exception. ()

Type minimum() const

Return the minimum object currently in the stack. It may throw a underflow exception. ()

int size() const

Returns the number of elements currently stored in the stack. ()

bool empty() const

Returns true if the stack is empty, false otherwise. ()

int capacity() const

Returns the current size of the arrays. ()

Mutators

This class has five mutators:

void swap( Dynamic_range_stack & );

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

Dynamic_range_stack &operator=( Dynamic_range_stack & );

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 & )

If the arrays are full, create three new arrays which are double in size, copy over all the entries, and delete the old arrays. Push the argument onto the top of the stack_array, push the larger of the current top of the maximum_array and the argument onto the maximum_array, and push the smaller of the current top of the minimum_array and the argument onto the minimum_array. (amortized )

Type pop()

Pop the top element off of the stack by removing the top element from all three arrays. If, after the element is removed, the arrays are 1/4 full and the array size is greater than the initial size, the size of the arrays are halved by creating three new arrays half the size and copying the entries over. This may throw a underflow exception. (amortized )

void clear()

Empties the stacks by resetting the member variables. If the current array size does not equal the initial size, delete the arrays and create three new arrays equal to the initial size. ()

Friends

The class has no friends.