Overview

In this assignment, you will be implementing your own Array-Based Stack (ABS). A stack is a linear data structure which follows the last in, first out (LIFO) property. LIFO means that the data most recently added is the first data to be removed. (Imagine a stack of books, or a stack of papers on a deskthe first one to be removed is the last one placed on top.)

The typical operations of a stack are:

Push Add something to the top of the stack

Pop Remove something from the top of the stack and return it

Example of a LIFO-the data most recently added is the first to be removed

Description

Your ABS will be a template class, and thus will be able to hold any data type. (Many data structures follow this conventionreuse code whenever you can!) As with previous classes that use dynamic memory, you must be sure to define The Big Three: The Copy Constructor, the Assignment Operator, and the Destructor.

Data will be stored using an array (hence the array-based stack). You may use any other variables/function in your class to make implementation easier.

By default, your ABS will have a scale factor 2.0f.

1. Attempting to push() an item onto an ABS that is full will scale its capacity by the scale factor.
2. When calling pop(), if the percent full (e.g. current size / max capacity) becomes less than

1/scale_factor, decrease the capacity of the ABS by 1-1/scale_factor

Why increase (or decrease) the size by any amount other than one?

Short answer: performance!

If you are increasing or decreasing the size of a container, its reasonable to assume that you will want to increase or decrease the size again at some point, requiring another round of allocate, copy, delete, etc.

Increasing the capacity by more than you might need (right now) or waiting to reduce the total capacity allows you to avoid costly dynamic allocations, which can improve performanceespecially in situations in which this resizing happens frequently. This tradeoff to this approach is that it will use more memory, but this speed-versus-memory conflict is something that programmers have been dealing with for a long time.

The images above assume a 2.0f scale factor

Your ABS will support the following methods:

• ABS(): Default constructor. Capacity should be initialized to 1, and size should be initialized to 0.
• ABS(int capacity): Constructor for an ABS with the specified starting capacity.
• ABS(const ABS &d): Copy constructor.
• ABS &operator=(const ABS &d): Assignment operator.
• ~ABS(): Destructor for an ABS.
• void push(T data): Add a new item to the top of the stack.
• T pop(): Remove the item at the top of the stack, and return its value. Throws -1 if the stack is empty.
• T peek(): Return the value of the item at the top of the stack, without removing it. Throws -1 if the stack is empty.
• unsigned int getSize(): Returns the current number of items in the ABS.
• unsigned int getMaxCapacity(): Returns the current max capacity of the ABS.
• T* getData(): Returns the array representing the stack. This should only be used in order to implement the copy constructor or assignment operator.