Implementing Data Structure using levels of abstraction

Question

Lets assume I'm to implement Stack using dynamic array allocation. I have the following classes and their functions.

Data.h

class Data
{
public:
   Data(std::string fname, int age) : name(fname) , age(age) {}

private:
   std::string name;
   int age;
}

StackArray.h

#include "Data.h"

class StackArray
{
public:
    StackArray(int sSize) : size(sSize), top(-1)
    {
       DataArray = new Data[size];
    };

    ~StackArray() { delete[] DataArray; };

    StackArray& operator=(StackArray& StackArrayObj) { //use copy&swap here };
    Stack(const StackArray& StackArrayObj);
    bool isFull();
    bool isEmpty();
    void push(Data& DataObj);
    void pop();

private:
    Data* DataArray;
    int top;
    int size;
}

If I implement something like the above, it works quite well. But of recent, I've been asked to implement the above two as it is, then have a separate implementation for core Stack functionalities.

So now, if I move push, pop, isFull, isEmpty to the new Stack definition, what exactly will be the purpose of class StackArray implemtation?.

The two solution I have tried are as follows:

New class implemtation

class StackADT
{
 public:
    StackADT();
    virtual ~StackADT() = 0;
    virtual bool isFull() = 0;
    virtual bool isEmpty() = 0;
    virtual void push(Data& DataObj) = 0;
    virtual void pop() = 0;
}

Then, by extending this class from StackArray class, thereby forcing it to implement all the pure virtual function.

The second, but not so elegant(my opinion) way I have done it is that:

I have a complete definition and implementation of the Stack in StackADT, and then calling the corresponding methods in equivalent methods in StackArray. Like this:

StackADT - push

bool StackADT::push(const Data& DataObj)
{
    if(!isFull)
       return false;
    else
    {
       top++;
       DataArray[top] = DataObj;
    }
    return true;
}

then inside StackArray - push, I'll do something like this:

bool StackArray::push(const Data& DataObj)
{
    StackADT doPush;
    doPush.push(DataObj);
}

Not too sure both methods of combining all three classes - Data, Container and Stack - are what they are suppose to be.

How can I solve this design problem? OR at least align it with "best practice" if there's any for such.

Answer 1

When we are talking about abstractions, we should try to identify the core aspects of what we are trying to implement. Normally, those aspects can be represented as an interface.

Since in C++, unlike other languages like Java, we do not have a specific interface declaration syntax, we can use pure virtual classes.

Generically speaking, a stack is a data structure following a LIFO access structure and nothing more.

Even though being limited by the amount of memory, I don't see any reason why a basic stack should have a size limit at first. A more abstracted way of thinking about size limit would be to verify whether the stack accepts more elements or can provide and element through a pop invocation.

So, we might think about a stack basic interface as follows:

class Stack {
public:
    virtual ~Stack()=0;
    virtual Data& pop() throw (std::out_of_range) = 0;
    virtual void push(Data&) throw (std::out_of_range) = 0;
    virtual bool isPoppable() = 0;
    virtual bool isPushable() = 0;
}

Then now we can start thinking about implementations. A simple implementation would be doing so with an array:

class StackArray : public Stack {
private:
    Data* mArray;
    int mSize;
    int mPointer;
    StackArray(int size) : mSize(size), mPointer(0) {
        mArray = new Data[mSize];
    }
    virtual ~StackArray() {
        delete [] mArray;
    }
public:
    void push(Data& el) throw (std::out_of_range) {
        if (!isPushable()) throw std::out_of_range("Cannot push to this stack");
        mArray[mPointer++] = el;
    }

    Data& pop() throw (std::out_of_range) {
        if (!isPopable()) throw std::out_of_range("Cannot pop from this stack");
        return mArray[mPointer--];
    }

    bool isPushable() {
        return mPointer < mSize;
    }

    bool isPoppable() {
        return mPointer > 0;
    }
}

Going further, we could think of a linked-list-based stack:

class DataNode {
private:
    DataNode* next;
    Data* data;
public: // trivial impl. ommited
    bool hasNext();
    DataNode* getNext();
    Data* getData();
    void setNext(DataNode* next);
    void setData(Data* data);
}

class StackLinkedList : public Stack {
private:
    DataNode* root;
public:
    StackLinkedList():pointer(0) {}
    virtual ~StackLinkedList() {}
    void push(Data& el) throw (std::out_of_range) {
        if (!isPushable()) throw std::out_of_range("Cannot push to this stack");
        DataNode* n = new DataNode();
        n->setData(&el);

        DataNode* pointer = root;
        if (root == NULL) {
            pointer = n;
        } else {
            while (pointer->hasNext()) {
                pointer = pointer->getNext();
            }

            pointer->setNext(n);
        }
    }

    Data& pop() throw (std::out_of_range) {
        if (!isPoppable()) throw std::out_of_range("Cannot pop from this stack");
        DataNode* pointer = root, previous = NULL;
        while (pointer->hasNext()) {
            previous = pointer;
            pointer = pointer->getNext();
        }

        Data* ret = pointer->getData();
        delete pointer;
        if (previous != NULL) {
            previous->setNext(NULL);
        }

        return *ret;
    }

    bool isPushable() {
        return true;
    }

    bool isPoppable() {
       return root != NULL;
    }
}

Answer 2

I understand that your exercise it to make you think about what's a general stack ("core stack function") and what's a perticular implementation of it.

So the alternative of having your abstract class:

class StackADT
{
 public:
     ...  // pure virtual core function 
};  // <= allways ;  at end of class ;-) 

would lead to having StackArray as a concrete implementation:

class StackArray : public Stack ADT {
    ... // you can leave the rest as it is:  the functions will override the virtual ones.  
};

What's the purpose of all this ? Well, you could perfectly imagine implementing a StackLinkedList or StackReallocArray. The advantage is that the difference is only at creation. Once a stack is created, the code using it is the same, whatever implementation is used.

Another approach could be to use templates to generalize on the content of the stack. And yet another would be to use <stack>, but I think that this is not (yet) the goal of your exercise.