In this problem you will use C++ built in arrays to create a class List , which
ID: 3687993 • Letter: I
Question
In this problem you will use C++ builtin arrays to create a class List, which should work something like a vector<int>
In a file List.cpp, implement the following interface:
class List {
public:
List();
void push_back( int val);
void pop_back();
int get_size()
const;
void print() const;
private:
int capacity;
int size;
int* data;
void double_capacity();
};
Member functions push_back and pop_back
will behave similarly to the corresponding functions
for vectors.
Excessive pop_backs (calls made when the list is already empty) should not cause issues.
get_size should simply return the
size
of the
List, just like the
size()
function does for
a vector. Wouldn’t it be nice if vectors had a
function for printing all their elements to the
console?
data
is a pointer to the array used to store the data for your list.
size
is for the number of elements
actually stored in the data array
, whereas
capacity
is
the
available
size of the data array. When a List is constructed using the default constructor, the capacity should be 2. Whenever a call to push_backwouldcause the size of theList to exceed its capacity, the functiondouble_capacity should be invoked to:
-allocate a new data array with twice the old data array’s capacity
-copy the elements of the old data array to the new data array, and deallocate the old data array, all while updating the values of the capacity, size, and data instance variables appropriately.
-The capacity of theListnever needs to be decreased, and you do not need to provide a function todeallocate all memorycurrentlyused by the List.
You do not need to provide functions for getting and setting elements from the List, but you might want to think about how those would work.
NO VECTORS and MALLOC. MUST USE BUILT IN ARRAYS
Explanation / Answer
template <class Type>
class stackADT
{
public:
virtual void initializeStack() = 0;
//Method to initialize the stack to an empty state.
//Postcondition: Stack is empty
virtual bool isEmptyStack() const = 0;
//Function to determine whether the stack is empty.
//Postcondition: Returns true if the stack is empty,
//otherwise returns false.
virtual bool isFullStack() const = 0;
//Function to determine whether the stack is full.
//Postcondition: Returns true if the stack is full,
//otherwise returns false.
virtual void push(const Type& newItem) = 0;
//Function to add newItem to the stack.
//Precondition: The stack exists and is not full.
//Postcondition: The stack is changed and newItem
// is added to the top of the stack.
virtual Type top() const = 0;
//Function to return the top element of the stack.
//Precondition: The stack exists and is not empty.
//Postcondition: If the stack is empty, the program
//terminates; otherwise, the top element
//of the stack is returned.
virtual void pop() = 0;
//Function to remove the top element of the stack.
//Precondition: The stack exists and is not empty.
//Postcondition: The stack is changed and the top
// element is removed from the stack.
};
//Header file: myStack.h
#include <iostream>
#include <cassert>
using namespace std;
template <class Type>class stackType: public stackADT<Type>
{
public:
const stackType<Type>& operator=(const stackType<Type>&);
//Overload the assignment operator.
void initializeStack();
//Function to initialize the stack to an empty state.
//Postcondition: stackTop = 0
bool isEmptyStack() const;
//Function to determine whether the stack is empty.
//Postcondition: Returns true if the stack is empty,
//otherwise returns false.
bool isFullStack() const;
//Function to determine whether the stack is full.
//Postcondition: Returns true if the stack is full,
//otherwise returns false.
void push(const Type& newItem);
//Function to add newItem to the stack.
//Precondition: The stack exists and is not full.
//Postcondition: The stack is changed and newItem
//is added to the top of the stack.
Type top() const;
//Function to return the top element of the stack.
//Precondition: The stack exists and is not empty.
//Postcondition: If the stack is empty, the program
//terminates; otherwise, the top element
//of the stack is returned.
void pop();
//Function to remove the top element of the stack.
//Precondition: The stack exists and is not empty.
//Postcondition: The stack is changed and the top
//element is removed from the stack.
stackType(int stackSize = 100);
//constructor
//Create an array of the size stackSize to hold
//the stack elements. The default stack size is 100.
//Postcondition: The variable list contains the base
//address of the array, stackTop = 0, and
//maxStackSize = stackSize.
stackType(const stackType<Type>& otherStack);
//copy constructor
~stackType();
//destructor
//Remove all the elements from the stack.
//Postcondition: The array (list) holding the stack
//elements is deleted.
private:
int maxStackSize;
//variable to store the maximum stack size
int stackTop;
//variable to point to the top of the stack
Type *list;
//pointer to the array that holds the
//stack elements
void copyStack(const stackType<Type>& otherStack);
//Function to make a copy of otherStack.
//Postcondition: A copy of otherStack is created and
//assigned to this stack.
};
template <class Type>
void stackType<Type>::initializeStack()
{
stackTop = 0;
}
//end initializeStack
template
<class Type>
bool stackType<Type>::isEmptyStack() const
{
return(stackTop == 0);
}
//end isEmptyStack
template
<class Type>
bool stackType<Type>::isFullStack() const
{
return(stackTop == maxStackSize);
}
//end isFullStack
template
<class Type>
void stackType<Type>::push(const Type& newItem)
{
if (!isFullStack())
{
list[stackTop] = newItem;
//add newItem to the
//top of the stack
stackTop++;
//increment stackTop
}
else
cout << "Cannot add to a full stack." << endl;
}
//end push
template
<class Type>
Type stackType<Type>::top() const
{
assert(stackTop != 0);
//if stack is empty,
//terminate the program
return list[stackTop - 1];
//return the element of the
//stack indicated by
//stackTop - 1
}//end top
template
<class Type>
void stackType<Type>::pop()
{
if (!isEmptyStack())
stackTop--;
//decrement stackTop
else
cout << "Cannot remove from an empty stack." << endl;
}
//end pop
template
<class Type>
stackType<Type>::stackType(int stackSize)
{
if (stackSize <= 0)
{
cout << "Size of the array to hold the stack must "
<< "be positive." << endl;
cout << "Creating an array of size 100." << endl;
maxStackSize = 100;
}
else
maxStackSize = stackSize;
//set the stack size to
//the value specified by
//the parameter stackSize
stackTop = 0;
//set stackTop to 0
list = new Type[maxStackSize];
//create the array to
//hold the stack elements
}
//end constructor
template
<class Type>
stackType<Type>::~stackType()
{
delete [] list;
//deallocate the memory occupied
//by the array
}
//end destructor
template
<class Type>
void stackType<Type>::copyStack(const stackType<Type>& otherStack)
{
delete [] list;
maxStackSize = otherStack.maxStackSize;
stackTop = otherStack.stackTop;
list = new Type[maxStackSize];
//copy otherStack into this stack
for (int j = 0; j < stackTop; j++)
list[j] = otherStack.list[j];
} //end copyStack
template
<class Type>
stackType<Type>::stackType(const stackType<Type>& otherStack)
{
list = NULL;
copyStack(otherStack);
}
//end copy constructor
template
<class Type>
const stackType<Type>& stackType<Type>::operator=(const stackType<Type>& otherStack)
{
if (this != &otherStack)
//avoid self-copy
copyStack(otherStack);
return *this;
}
//end operator=
//Program to test the various operations of a stack
#include <iostream>
using namespace std;
void testCopyConstructor(stackType<int> otherStack);
int main()
{
stackType<int> stack(50);
stackType<int> copyStack(50);
stackType<int> dummyStack(100);
stack.initializeStack();
stack.push(23);
stack.push(45);
stack.push(38);
copyStack = stack;
//copy stack into copyStack
cout << "The elements of copyStack: ";
while (!copyStack.isEmptyStack()) {
cout << copyStack.top() << " ";
copyStack.pop();
}
cout << endl;
copyStack = stack;
testCopyConstructor(stack);
//test the copy constructor
if (!stack.isEmptyStack())
cout << "The original stack is not empty." << endl
<< "The top element of the original stack: "
<< copyStack.top() << endl;
dummyStack = stack;
//copy stack into dummyStack
cout << "The elements of dummyStack: ";
while (!dummyStack.isEmptyStack()) {
cout << dummyStack.top() << " ";
dummyStack.pop();
}
cout << endl;
return 0;
}
void testCopyConstructor(stackType<int> otherStack)
{
if (!otherStack.isEmptyStack())
cout << "otherStack is not empty." << endl
<< "The top element of otherStack: "
<< otherStack.top() << endl;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.