使用抽象层次实现数据结构

Question

假设我要使用动态数组分配来实现 Stack。我有以下 classes 及其功能。

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

如果我实现类似上面的东西，效果会很好。但是最近，我被要求按原样实现上述两个，然后为核心 Stack 功能单独实现。

所以现在，如果我将 push、pop、isFull、isEmpty 移动到新的 Stack 定义，[=21 的目的究竟是什么？ =] 实施?.

我尝试过的两种解决方案如下：

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

然后，通过从 StackArray class 扩展这个 class，从而强制它实现所有纯虚函数。

第二种，但不是那么优雅（我认为）的方法是：

我在StackADT里面有完整的Stack的定义和实现，然后在StackArray的等价方法中调用对应的方法。像这样：

StackADT - push

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

然后在 StackArray - push 里面，我会做这样的事情：

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

不太确定将所有三种 class 数据、容器和堆栈组合在一起的方法是否是它们应该是的。

如何解决这个设计问题？或者至少将其与 "best practice" 对齐（如果有的话）。

Answer 1

我知道你练习它是为了让你思考什么是通用堆栈 ("core stack function") 以及什么是它的特定实现。

所以你的摘要的替代方案 class：

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

将导致 StackArray 作为具体实现：

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

这一切的目的是什么？好吧，您完全可以想象实现 StackLinkedList 或 StackReallocArray。优点是差异仅在创建时。创建堆栈后，使用它的代码是相同的，无论使用何种实现。

另一种方法可能是使用模板来概括堆栈的内容。还有一种方法是使用 <stack>，但我认为这（还）不是您练习的目标。

Answer 2

当我们谈论抽象时，我们应该尝试确定我们试图实现的核心方面。通常，这些方面可以表示为一个接口。

因为在C++中，不像其他语言Java，我们没有特定的接口声明语法，我们可以使用纯虚类.

一般来说，堆栈是一种遵循 LIFO 访问结构的数据结构，仅此而已。

尽管受到内存量的限制，但我看不出有任何理由让基本堆栈一开始就应该有大小限制。考虑大小限制的一种更抽象的方法是验证堆栈是否接受更多元素或可以通过 pop 调用提供和元素。

所以，我们可能会想到一个stack基本接口如下：

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

那么现在我们可以开始考虑实现了。一个简单的实现是使用数组：

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

更进一步，我们可以想到基于链表的堆栈：

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

c++

oop

inheritance

design-patterns