Question

- implement the Stack ADT using array – based approach. Use C++ program language

#include "StackArray.h"

template <typename DataType>
StackArray<DataType>::StackArray(int maxNumber)
{
}

template <typename DataType>
StackArray<DataType>::StackArray(const StackArray& other)
{
}

template <typename DataType>
StackArray<DataType>& StackArray<DataType>::operator=(const StackArray& other)
{
}

template <typename DataType>
StackArray<DataType>::~StackArray()
{
}

template <typename DataType>
void StackArray<DataType>::push(const DataType& newDataItem) throw (logic_error)
{
}

template <typename DataType>
DataType StackArray<DataType>::pop() throw (logic_error)
{

}

template <typename DataType>
void StackArray<DataType>::clear()
{
}

template <typename DataType>
bool StackArray<DataType>::isEmpty() const
{
   return false;
}

template <typename DataType>
bool StackArray<DataType>::isFull() const
{
   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 << "\t";
   cout << endl;
   for ( j = 0 ; j <= top ; j++ )
   {
   if( j == top )
   {
   cout << '[' << dataItems[j] << ']'<< "\t"; // Identify top
   }
   else
   {
       cout << dataItems[j] << "\t";
   }
   }
   cout << endl;
}
cout << endl;
}

// Class declaration for the linked implementation of the Stack ADT
//
//--------------------------------------------------------------------

#ifndef STACKARRAY_H
#define STACKARRAY_H

#include <stdexcept>
#include <iostream>

using namespace std;

#include "Stack.h"

template <typename DataType>
class StackArray : public Stack<DataType> {
public:
StackArray(int maxNumber = Stack<DataType>::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

Answer 1

StackArray.cpp

#ifndef STACKARRAY_CPP
#define STACKARRAY_CPP

#include <iostream>

#include "StackArray.h"

//--------------------------------------------------------------------

template <typename DataType>
StackArray<DataType>::StackArray(int maxNumber)

// Creates an empty stack.

    : maxSize(maxNumber), top(-1)
{
    dataItems = new DataType[maxNumber];
}

//--------------------------------------------------------------------

template <typename DataType>
StackArray<DataType>::StackArray(const StackArray& other)

// Copy constructor for linked stack

: maxSize( other.maxSize ), top( other.top )
{
    dataItems = new DataType [ maxSize ];

    // Note: "i<= top" because top is the top item, not the zero-based size.
    for( int i=0; i<=top; i++ )
    {
   dataItems[i] = other.dataItems[i];
    }
}

//--------------------------------------------------------------------

template <typename DataType>
StackArray<DataType>& StackArray<DataType>::operator=(const StackArray& other)

// Overloaded assignment operator for the StackArray class.
// Because this function returns a StackArray object reference,
// it allows chained assignment (e.g., stack1 = stack2 = stack3).

{
    // Self-assignment protection
    if( this != &other ) return *this;

    if( maxSize < other.maxSize ) {
   // This object's array is smaller than the other object's array.
   // Make an equally big array.

   delete[] dataItems;
   dataItems = new DataType [other.maxSize];
    }

    // Now proceed to copy state data over from other object.
    maxSize = other.maxSize;
    top = other.top;
    for( int i=0; i<=top; i++ )
    {

   dataItems[i] = other.dataItems[i];
    }

    return *this;
}

//--------------------------------------------------------------------

template <typename DataType>
StackArray<DataType>::~StackArray()

// Frees the memory used by a stack.

{
    delete[] dataItems;
}

//--------------------------------------------------------------------

template <typename DataType>
void StackArray<DataType>::push(const DataType& newDataItem) throw (logic_error)

// Inserts newDataItem onto the top of a stack.

{
    if (isFull()) {
   throw logic_error("push() while stack full");
    }else
    {
            top++;
            dataItems[top] = newDataItem;
        }
    }

//--------------------------------------------------------------------

template <typename DataType>
DataType StackArray<DataType>::pop() throw (logic_error)

// Removes the topmost data item from a stack and returns it.

{
    if (isEmpty()) {
   throw logic_error("pop() while stack empty");
    }else{
         //ADD YOUR CODE HERE (should require only one line of code)
        top--;
        return dataItems[top +1];
    }
}

//--------------------------------------------------------------------

template <typename DataType>
void StackArray<DataType>::clear()

// Removes all the data items from a stack.

{
    top = -1;
}

//--------------------------------------------------------------------

template <typename DataType>
bool StackArray<DataType>::isEmpty() const

// Returns true if a stack is empty. Otherwise, returns false.

{
    return top == -1;
}

//--------------------------------------------------------------------

template <typename DataType>
bool StackArray<DataType>::isFull() const

// Returns true if a stack is full. Otherwise, returns false.

{
    return top == maxSize - 1;
}

//--------------------------------------------------------------------

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 << "\t";
   cout << endl;
   for ( j = 0 ; j <= top ; j++ )
   {
        if( j == top )
        {
            cout << '[' << dataItems[j] << ']'<< "\t"; // Identify top
        }
        else
        {
       cout << dataItems[j] << "\t";
        }
   }
   cout << endl;
    }
    cout << endl;
}

#endif       // #ifndef STACKARRAY_CPP

StackArray.h

#ifndef STACKARRAY_H
#define STACKARRAY_H

#include <stdexcept>
#include <iostream>

using namespace std;

#include "Stack.h"

template <typename DataType>
class StackArray : public Stack<DataType> {
public:
    StackArray(int maxNumber = Stack<DataType>::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

Stack.h

// for the exception warnings
#pragma warning( disable : 4290 )

#ifndef STACK_H
#define STACK_H

#include <stdexcept>
#include <iostream>

using namespace std;

template <typename DataType>
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 <typename DataType>
Stack<DataType>::~Stack()
// Not worth having a separate class implementation file for the destuctor
{}

#endif       // #ifndef STACK_H

main.cpp

#include <iostream>

using namespace std;

# include "StackArray.cpp"

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 <typename DataType>
void test_stack(Stack<DataType>& 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() {

   cout << "Testing array implementation" << endl;
   StackArray<char> s1;
   test_stack(s1);

}