假设我要使用动态数组分配来实现Stack.
我有以下课程及其功能.
我有以下课程及其功能.
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;
}
如果我实现像上面这样的东西,它的效果很好.但是最近,我被要求实现上述两个,然后有一个单独的核心堆栈功能的实现.
所以现在,如果我将push,pop,isFull,isEmpty移动到新的Stack定义,StackArray类实现的目的究竟是什么？
我试过的两个解决方案如下：
新课程实施
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类扩展这个类,从而强制它实现所有的纯虚函数.
第二个但不是如此优雅(我的观点),我所做的就是：
我在StackADT中完成了Stack的定义和实现,然后在StackArray中以相同的方法调用相应的方法.喜欢这个：
StackADT – 推
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);
}
不太确定组合所有三个类(数据,容器和堆栈)的两种方法是他们认为的.
我如何解决这个设计问题？或者至少与“最佳实践”对齐,如果有的话.
解决方法
当我们谈论抽象时,我们应该尝试确定我们正在实施的核心方面.通常,这些方面可以表示为接口.
由于在C中,与其他语言(如Java)不同,我们没有特定的接口声明语法,我们可以使用纯虚拟类.
一般来说,堆栈是遵循LIFO访问结构的数据结构,没有其他的.
即使受到内存量的限制,我没有看到任何原因,一个基本的堆栈应该有一个大小限制.考虑大小限制的更抽象的方法将是验证堆栈是否接受更多元素,或者可以通过弹出式调用提供和元素.
所以,我们可以考虑堆栈的基本界面如下：
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;
}
}