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

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

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

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

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

У меня есть полное определение и реализация Stack in 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);
}

Не слишком уверен, что оба метода объединения всех трех классов - Data, Container и Stack - это то, что они должны быть.

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

Ответы

Ответ 1

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

Так как в С++, в отличие от других языков, таких как 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;
    }
}

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