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.

Henrique Barcelos · Accepted Answer

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;
    }
}

Implementing Data Structure using levels of abstraction

Answers (2)

Related Questions