Source code - download the attached zip file. It contains the Visual Studio proj
ID: 3903100 • Letter: S
Question
Source code
- download the attached zip file. It contains the Visual Studio project that you are required to modify.
To Do:
- implement the Stack ADT (50 points) using the array-based approach
- implement the Stack ADT (50 points) using the linked list approach
-----------------------------------------------------------------------------------------------
.header files
----------------------------------------------------------------------------------------------
//config.h
/**
* Stack class (Lab 6) configuration file.
* Activate test #N by defining the corresponding LAB6_TESTN to have the value 1.
*/
#define LAB6_TEST1 1 // 0 => use array implementation, 1 => use linked impl.
--------------------------------------------------------------------------
//stack.h
// Class declaration of the abstract class interface to be used as
// the basis for implementations of the Stack ADT.
// for the exception warnings
#pragma warning( disable : 4290 )
#ifndef STACK_H
#define STACK_H
#include
#include
using namespace std;
template
class Stack {
public:
static const int MAX_STACK_SIZE = 8;
virtual ~Stack();
virtual void push(const DataType& newDataItem) throw (logic_error) = 0;
virtual DataType pop() throw (logic_error) = 0;
virtual void clear() = 0;
virtual bool isEmpty() const = 0;
virtual bool isFull() const = 0;
virtual void showStructure() const = 0;
};
template
Stack::~Stack()
// Not worth having a separate class implementation file for the destuctor
{}
#endif // #ifndef STACK_H
-----------------------------------------------------------
// StackArray.h
// Class declaration for the array implementation of the Stack ADT
#ifndef STACKARRAY_H
#define STACKARRAY_H
#include
#include
using namespace std;
#include "Stack.h"
template
class StackLinked : public Stack {
public:
StackLinked(int maxNumber = Stack::MAX_STACK_SIZE);
StackLinked(const StackLinked& other);
StackLinked& operator=(const StackLinked& other);
~StackLinked();
void push(const DataType& newDataItem) throw (logic_error);
DataType pop() throw (logic_error);
void clear();
bool isEmpty() const;
bool isFull() const;
void showStructure() const;
private:
class StackNode {
public:
StackNode(const DataType& nodeData, StackNode* nextPtr)
{
dataItem = nodeData;
next = nextPtr;
}
DataType dataItem;
StackNode* next;
};
StackNode* top;
};
#endif //#ifndef STACKARRAY_H
-------------------------------------------------------
// StackLinked.h
// Class declaration for the linked implementation of the Stack ADT
#ifndef STACKARRAY_H
#define STACKARRAY_H
#include
#include
using namespace std;
#include "Stack.h"
template
class StackArray : public Stack {
public:
StackArray(int maxNumber = Stack::MAX_STACK_SIZE);
StackArray(const StackArray& other);
StackArray& operator=(const StackArray& other);
~StackArray();
void push(const DataType& newDataItem) throw (logic_error);
DataType pop() throw (logic_error);
void clear();
bool isEmpty() const;
bool isFull() const;
void showStructure() const;
private:
int maxSize;
int top;
DataType* dataItems;
};
#endif //#ifndef STACKARRAY_H
-----------------------------------------------------
.cpp files
---------------------------------------------------
//test.cpp
#include
using namespace std;
#include "config.h"
#if !LAB6_TEST1
# include "StackArray.cpp"
#else
# include "StackLinked.cpp"
#endif
void print_help()
{
cout << endl << "Commands:" << endl;
cout << " H : Help (displays this message)" << endl;
cout << " +x : Push x" << endl;
cout << " - : Pop" << endl;
cout << " C : Clear" << endl;
cout << " E : Empty stack?" << endl;
cout << " F : Full stack?" << endl;
cout << " Q : Quit the test program" << endl;
cout << endl;
}
template
void test_stack(Stack& testStack)
{
DataType testDataItem; // Stack data item
char cmd; // Input command
print_help();
do
{
testStack.showStructure(); // Output stack
cout << endl << "Command: "; // Read command
cin >> cmd;
if ( cmd == '+' )
cin >> testDataItem;
try {
switch ( cmd )
{
case 'H' : case 'h':
print_help();
break;
case '+' : // push
cout << "Push " << testDataItem << endl;
testStack.push(testDataItem);
break;
case '-' : // pop
cout << "Popped " << testStack.pop() << endl;
break;
case 'C' : case 'c' : // clear
cout << "Clear the stack" << endl;
testStack.clear();
break;
case 'E' : case 'e' : // isEmpty
if ( testStack.isEmpty() )
cout << "Stack is empty" << endl;
else
cout << "Stack is NOT empty" << endl;
break;
case 'F' : case 'f' : // isFull
if ( testStack.isFull() )
cout << "Stack is full" << endl;
else
cout << "Stack is NOT full" << endl;
break;
case 'Q' : case 'q' : // Quit test program
break;
default : // Invalid command
cout << "Inactive or invalid command" << endl;
}
}
catch (logic_error e) {
cout << "Error: " << e.what() << endl;
}
} while ( cin && cmd != 'Q' && cmd != 'q' );
}
int main() {
#if !LAB6_TEST1
cout << "Testing array implementation" << endl;
StackArray s1;
test_stack(s1);
#else
cout << "Testing linked implementation" << endl;
StackLinked s2;
test_stack(s2);
#endif
}
---------------------------------------------------------------------
//FILL OUT THIS FILE
//stackArray.cpp
#include "StackArray.h"
template
StackArray::StackArray(int maxNumber)
{
}
template
StackArray::StackArray(const StackArray& other)
{
}
template
StackArray& StackArray::operator=(const StackArray& other)
{
}
template
StackArray::~StackArray()
{
}
template
void StackArray::push(const DataType& newDataItem) throw (logic_error)
{
}
template
DataType StackArray::pop() throw (logic_error)
{
DataType t=0;
return t;
}
template
void StackArray::clear()
{
}
template
bool StackArray::isEmpty() const
{
return false;
}
template
bool StackArray::isFull() const
{
return false;
}
template
void StackArray::showStructure() const
// Array implementation. Outputs the data items in a stack. If the
// stack is empty, outputs "Empty stack". This operation is intended
// for testing and debugging purposes only.
{
if( isEmpty() ) {
cout << "Empty stack." << endl;
}
else {
int j;
cout << "Top = " << top << endl;
for ( j = 0 ; j < maxSize ; j++ )
cout << j << " ";
cout << endl;
for ( j = 0 ; j <= top ; j++ )
{
if( j == top )
{
cout << '[' << dataItems[j] << ']'<< " "; // Identify top
}
else
{
cout << dataItems[j] << " ";
}
}
cout << endl;
}
cout << endl;
}
--------------------------------------------------------------
//FILL OUT THIS FILE ALSO
//stackLinked.cpp
#include "StackLinked.h"
template
StackLinked::StackLinked (int maxNumber)
{
}
template
StackLinked::StackLinked(const StackLinked& other)
{
}
template
StackLinked& StackLinked::operator=(const StackLinked& other)
{
}
template
StackLinked::~StackLinked()
{
clear();
}
template
void StackLinked::push(const DataType& newDataItem) throw (logic_error)
{
}
template
DataType StackLinked::pop() throw (logic_error)
{
DataType t = 0;
return t;
}
template
void StackLinked::clear()
{
}
template
bool StackLinked::isEmpty() const
{
return false;
}
template
bool StackLinked::isFull() const
{
return false;
}
template
void StackLinked::showStructure() const
{
if( isEmpty() )
{
cout << "Empty stack" << endl;
}
else
{
cout << "Top ";
for (StackNode* temp = top; temp != 0; temp = temp->next) {
if( temp == top ) {
cout << "[" << temp->dataItem << "] ";
}
else {
cout << temp->dataItem << " ";
}
}
cout << "Bottom" << endl;
}
}
Explanation / Answer
Given below is the complemented implementations in .cpp files. Please change the config.h file to test array based / linked implementation
StackArray.cpp
--------
//stackArray.cpp
#include "StackArray.h"
template <typename DataType>
StackArray<DataType>::StackArray(int maxNumber)
{
maxSize = maxNumber;
dataItems = new DataType[maxSize];
clear();
top = 0;
}
template <typename DataType>
StackArray<DataType>::StackArray(const StackArray<DataType>& other)
{
maxSize = other.maxSize;
dataItems = new DataType[maxSize];
clear();
top = other.top;
for(int i = 0; i < top; i++)
dataItems[i] = other.dataItems[i];
}
template <typename DataType>
StackArray<DataType>& StackArray<DataType>::operator=(const StackArray<DataType>& other)
{
delete [] dataItems;
maxSize = other.maxSize;
dataItems = new DataType[maxSize];
clear();
top = other.top;
for(int i = 0; i < top; i++)
dataItems[i] = other.dataItems[i];
}
template <typename DataType>
StackArray<DataType>::~StackArray()
{
delete []dataItems;
}
template <typename DataType>
void StackArray<DataType>::push(const DataType& newDataItem) throw (logic_error)
{
if(isFull())
throw logic_error("stack full");
dataItems[top++] = newDataItem;
}
template <typename DataType>
DataType StackArray<DataType>::pop() throw (logic_error)
{
if(isEmpty())
throw logic_error("stack empty");
DataType t = dataItems[--top];
dataItems[top] = DataType();
return t;
}
template <typename DataType>
void StackArray<DataType>::clear()
{
for(int i = 0; i < maxSize; i++)
dataItems[i] = DataType();
top = 0;
}
template <typename DataType>
bool StackArray<DataType>::isEmpty() const
{
if(top == 0)
return true;
else
return false;
}
template <typename DataType>
bool StackArray<DataType>::isFull() const
{
if(top == maxSize)
return true;
else
return false;
}
template <typename DataType>
void StackArray<DataType>::showStructure() const
// Array implementation. Outputs the data items in a stack. If the
// stack is empty, outputs "Empty stack". This operation is intended
// for testing and debugging purposes only.
{
if( isEmpty() ) {
cout << "Empty stack." << endl;
}
else {
int j;
cout << "Top = " << top << endl;
for ( j = 0 ; j < maxSize ; j++ )
cout << j << " ";
cout << endl;
for ( j = 0 ; j <= top ; j++ )
{
if( j == top )
{
cout << '[' << dataItems[j] << ']'<< " "; // Identify top
}
else
{
cout << dataItems[j] << " ";
}
}
cout << endl;
}
cout << endl;
}
StackLinked.cpp
--------------
//stackLinked.cpp
#include "StackLinked.h"
template <typename DataType>
StackLinked<DataType>::StackLinked (int maxNumber)
{
top = nullptr;
}
template <typename DataType>
StackLinked<DataType>::StackLinked(const StackLinked<DataType>& other)
{
StackNode *n = other.top;
top = nullptr;
while(n != nullptr)
{
push(n->dataItem);
n = n->next;
}
}
template <typename DataType>
StackLinked<DataType>& StackLinked<DataType>::operator=(const StackLinked<DataType>& other)
{
clear();
StackNode *n = other.top;
while(n != nullptr)
{
push(n->dataItem);
n = n->next;
}
}
template <typename DataType>
StackLinked<DataType>::~StackLinked()
{
clear();
}
template <typename DataType>
void StackLinked<DataType>::push(const DataType& newDataItem) throw (logic_error)
{
StackNode *n = new StackNode(newDataItem, top);
top = n;
}
template <typename DataType>
DataType StackLinked<DataType>::pop() throw (logic_error)
{
if(isEmpty())
throw logic_error("stack empty");
DataType t = top->dataItem;
StackNode *tmp = top;
top = top->next;
delete tmp;
return t;
}
template <typename DataType>
void StackLinked<DataType>::clear()
{
StackNode *tmp;
while(top != nullptr)
{
tmp = top->next;
delete top;
top = tmp;
}
}
template <typename DataType>
bool StackLinked<DataType>::isEmpty() const
{
if(top == nullptr)
return true;
else
return false;
}
template <typename DataType>
bool StackLinked<DataType>::isFull() const
{
return false;
}
template <typename DataType>
void StackLinked<DataType>::showStructure() const
{
if( isEmpty() )
{
cout << "Empty stack" << endl;
}
else
{
cout << "Top ";
for (StackNode* temp = top; temp != 0; temp = temp->next) {
if( temp == top ) {
cout << "[" << temp->dataItem << "] ";
}
else {
cout << temp->dataItem << " ";
}
}
cout << "Bottom" << endl;
}
}
output
=====
Testing linked implementation
Commands:
H : Help (displays this message)
+x : Push x
- : Pop
C : Clear
E : Empty stack?
F : Full stack?
Q : Quit the test program
Empty stack
Command: +3
Push 3
Top [3] Bottom
Command: +4
Push 4
Top [4] 3 Bottom
Command: +5
Push 5
Top [5] 4 3 Bottom
Command: -
Popped 5
Top [4] 3 Bottom
Command: E
Stack is NOT empty
Top [4] 3 Bottom
Command: F
Stack is NOT full
Top [4] 3 Bottom
Command: Q
========
Testing array implementation
Commands:
H : Help (displays this message)
+x : Push x
- : Pop
C : Clear
E : Empty stack?
F : Full stack?
Q : Quit the test program
Empty stack.
Command: +2
Push 2
Top = 1
0 1 2 3 4 5 6 7
2 [0]
Command: +4
Push 4
Top = 2
0 1 2 3 4 5 6 7
2 4 [0]
Command: +6
Push 6
Top = 3
0 1 2 3 4 5 6 7
2 4 6 [0]
Command: E
Stack is NOT empty
Top = 3
0 1 2 3 4 5 6 7
2 4 6 [0]
Command: F
Stack is NOT full
Top = 3
0 1 2 3 4 5 6 7
2 4 6 [0]
Command: -
Popped 6
Top = 2
0 1 2 3 4 5 6 7
2 4 [0]
Command: Q
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.