Requirements:

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

1. Drop-off Stack: Drop_off_stack.

A stack stores elements in an ordered list and allows insertions and deletions at one end in O(1) time.

The elements in this stack are stored in an array. If the array is full, the bottom item is dropped from the stack. In practice, this would be equivalent to overwriting that entry in the 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:

---

Drop_off_stack

Description

A class which implements a stack using an array. The capacity of the array is fixed at initialization time. For run-time requirements, the number of elements in the stack is n. The array is considered to be full if all entries in the array are assigned. If an insertion is made into a full stack, the element at the bottom is removed before the new element is inserted.

Member Variables

The class will have up to five members:

• A pointer to an instance of Type, Type *array, to be used as an array,
• A top index int itop,
• A bottom index int ibottom,
• 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. 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

Drop_off_stack( int n = 10 )

The constructor takes as an argument the capacity of the array and allocates memory for that array. The default initial capacity of the array is 10. Other class members are assigned as appropriate. (O(1))

Destructor

~Drop_off_stack()

The destructor deletes the memory allocated for the array. (O(1))

Copy Constructor

Drop_off_stack( Drop_off_stack const & )

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

Accessors

This class has three accessors:

Type top() const

Return the object at the top of the stack. This 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))

Mutators

This class has five mutators:

void swap( Drop_off_stack & );

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

Drop_off_stack &operator=( Drop_off_stack & );

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

void push( Type const & )

Insert the new element at the top of the stack. If the stack is full, the element at the bottom of the stack is removed. (O(1))

Type pop()

Removes the element at the top of the stack. This may throw a underflow exception. (O(1))

void clear()

Removes all the elements in the stack. (O(1))

Friends

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