Внедрение структуры данных с использованием уровней абстракции

Question

Предположим, что я должен реализовать 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; 
} 

Если я реализовать что-то вроде выше, она работает достаточно хорошо. Но в последнее время меня попросили реализовать вышеприведенные два, как есть, а затем иметь отдельную реализацию для основных функций Stack.

Так что теперь, если я перееду push, pop, isFull, isEmpty на новое определение стека, что именно будет цель class StackArray implemtation ?.

Два решения я попытался следующие:

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 класса, тем самым заставляя его реализовать все чисто виртуальную функцию.

Второй, но не настолько элегантна (мое мнение), как я делал это в том, что:

У меня есть полное определение и реализацию стека в StackADT, а затем вызвать соответствующие методы эквивалентных методов 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); 
} 

не слишком уверен, что оба способа объединения всех трех классов - Данные, контейнеров и стека - это то, что они должны быть.

Как я могу решить эту проблему? ИЛИ, по крайней мере, выровнять его с «лучшей практикой», если таковой имеется.

Answer 1

Когда мы говорим об абстракциях, мы должны попытаться определить основные аспекты того, что мы пытаемся реализовать. Обычно эти аспекты могут быть представлены как интерфейс.

Поскольку на C++, в отличие от других языков, таких как Java, у нас нет специального синтаксиса объявления интерфейса, мы можем использовать чистые виртуальные классы.

В общем случае стек представляет собой структуру данных, следующую за структурой доступа LIFO и не более того.

Несмотря на ограниченность объема памяти, я не вижу причин, по которым базовый стек должен иметь ограничение по размеру вначале. Более абстрактным способом мышления о пределе размера было бы проверить, принимает ли стек больше элементов или может предоставить и элемент через вызов pop.

Таким образом, мы могли бы думать о базовом интерфейсе стека следующим образом:

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

Answer 2

Я понимаю, что ваше упражнение это заставляет вас задуматься о том, что такое общий стек («функция основного стека») и что такое его реализация.

Так альтернатива иметь свой абстрактный класс:

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>, но я думаю, что это еще не цель вашего упражнения.