Dyanamic_stack

Description

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

Member Variables

The class at least four members:

• A pointer to an instance of Type, Type *array, to be used as an array,
• A counter int count,
• The initial size of the array, int initial_size, and
• The current size of the array, int array_size.

Member Functions

Constructors

Dyanamic_stack( int n = 10 )

The constructor takes as an argument the initial size of the array and allocates memory for that array. The default number of entries is 10. Other class members are assigned as appropriate.

Destructor

~Dyanamic_stack()

The destructor deletes the memory allocated for the array.

Accessors

This class has four accessors:

Type top() const

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

int size() const

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

bool empty() const

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

int capacity() const

Returns the current size of the array. (O(1))

Mutators

This class has three mutators:

void push( Type const & )

Insert the new element at the top of the stack. If the array is filled, the size of the array is doubled. (O(1) on average)

Type pop()

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

void clear()

Removes all the elements in the stack. The array is resized to the initial size. (O(1))

Friends

The class has no friends.