Overview

In this assignment, you will be implementing your own Array-Based Stack (ABS) and Array-Based Queue. 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.) A queue is another linear data structure that follows the first in, first out (FIFO) property. FIFO means that the data added first is the first to be removed (like a line in a grocery store-- the first person in line is the first to checkout).

Stack Behavior

Push Add something to the top of the stack.

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

Queue Behavior

Enqueue Add something to end of the queue.

Dequeue Remove something from the front of the queue.

Description

Your ABS and ABQ will be template classes, 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 a dynamically allocated array (hence the array-based stack and queue). You may use any other variables/function in your class to make implementation easier.

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

1. Attempting to push() or enqueue() an item onto an ABS/ABQ that is full will resize the current capacity to current_capacity*scale_factor.

2. When calling pop() or dequeue(), if the percent full (e.g. current size / max capacity) becomes strictly less than 1/scale_factor, resized the storage array to current_capacity/scale_factor.

Stack Functions

Your ABS must support the following methods:

ABS() -Default constructor. Maximum capacity should be set to 1, and current size set to 0;

ABS(int capacity) -Constructor for an ABS with the specified starting maximum capacity.

ABS(const ABS &d) -Copy Constructor

ABS &operator=(const ABS &d) -Assignment operator.

~ABS() -Destructor

void push(T data) -Add a new item to the top of the stack and resize if necessary.

T pop() -Remove the item at the top of the stack, resizes if necessary, and return the value removed. 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.

Queue Functions

Your ABQ must support the following functions

ABQ() -Default constructor. Maximum capacity should be set to 1, and current size set to 0;

ABQ(int capacity) -Constructor for an ABQ with the specified starting maximum capacity.

ABQ(const ABS &d) -Copy Constructor

ABQ &operator=(const ABQ &d) -Assignment operator.

~ABQ() -Destructor

void enqueue(T data) -Add a new item to end of the queue and resizes if necessary.

T dequeue() -Remove the item at front of the queue, resizes if necessary, and return the value removed. Throws -1 if the queue is empty.

T peek() -Return the value of the item at the front of the queue, without removing it. Throws -1 if the queue is empty.

unsigned int getSize() -Returns the current number of items in the ABQ.

unsigned int getMaxCapacity() -Returns the current max capacity of the ABQ.

T* getData() -Returns the array representing the queue.

Main.cpp:

#include "ABS.h" #include "ABQ.h" #include using namespace std;

void ABSTest(); void ABQTest();

int main(){ int choice; cin >> choice;

if(choice==1) ABSTest(); else if(choice==2) ABQTest();

return 0; }

void ABSTest(){ cout << "Making integer ABS... "; ABS intABS; cout << "Size: " << intABS.getSize() << endl; cout << "Max Capacity: " << intABS.getMaxCapacity() << endl; cout << " Pushing items... "; for(int i = 1; i < 10; i++){ intABS.push(i); cout << " Pushed " << intABS.peek() << endl; cout << "New Size: " << intABS.getSize() << endl; cout << "New Max Capacity: " << intABS.getMaxCapacity() << endl; }

cout << " Popping items... "; for(int i = 1; i < 10; i++){ cout << " Popped " << intABS.pop() << endl; cout << "New Size: " << intABS.getSize() << endl; cout << "New Max Capacity: " << intABS.getMaxCapacity() << endl; }

cout << " Making float ABS... "; ABS floatABS(10); cout << "Size: " << floatABS.getSize() << endl; cout << "Max Capacity: " << floatABS.getMaxCapacity() << endl; cout << " Pushing items... "; for(float i = 1; i < 5; i+=0.5f){ floatABS.push(i); cout << " Pushed " << floatABS.peek() << endl; cout << "New Size: " << floatABS.getSize() << endl; cout << "New Max Capacity: " << floatABS.getMaxCapacity() << endl; }

cout << " Popping items... "; for(float i = 1; i < 5; i+=0.5f){ cout << " Popped " << floatABS.pop() << endl; cout << "New Size: " << floatABS.getSize() << endl; cout << "New Max Capacity: " << floatABS.getMaxCapacity() << endl; } }

void ABQTest(){ cout << "Making integer ABQ... "; ABQ intABQ; cout << "Size: " << intABQ.getSize() << endl; cout << "Max Capacity: " << intABQ.getMaxCapacity() << endl; cout << " Enqueueing items... "; for(int i = 1; i < 10; i++){ intABQ.enqueue(i); cout << " Enqueued " << i << endl; cout << "New Size: " << intABQ.getSize() << endl; cout << "New Max Capacity: " << intABQ.getMaxCapacity() << endl; }

cout << " Dequeueing items... "; for(int i = 1; i < 10; i++){ cout << " Dequeued " << intABQ.dequeue() << endl; cout << "New Size: " << intABQ.getSize() << endl; cout << "New Max Capacity: " << intABQ.getMaxCapacity() << endl; }

cout << " Making float ABQ... "; ABQ floatABQ(10); cout << "Size: " << floatABQ.getSize() << endl; cout << "Max Capacity: " << floatABQ.getMaxCapacity() << endl; cout << " Enqueueing items... "; for(float i = 1; i < 5; i+=0.5f){ floatABQ.enqueue(i); cout << " Enqueued " << i << endl; cout << "New Size: " << floatABQ.getSize() << endl; cout << "New Max Capacity: " << floatABQ.getMaxCapacity() << endl; }

cout << " Dequeueing items... "; for(float i = 1; i < 5; i+=0.5f){ cout << " Dequeued " << floatABQ.dequeue() << endl; cout << "New Size: " << floatABQ.getSize() << endl; cout << "New Max Capacity: " << floatABQ.getMaxCapacity() << endl; } }