अमूर्तता के स्तर का उपयोग कर डेटा संरचना कार्यान्वित करना

Question

मान लें कि मैं गतिशील सरणी आवंटन का उपयोग करके स्टैक को कार्यान्वित करना चाहता हूं। मेरे पास निम्नलिखित कक्षाएं और उनके कार्य हैं।

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 नई ढेर परिभाषा करने के लिए, वास्तव में क्या 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। इस तरह: - डेटा, कंटेनर और ढेर

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

भी सुनिश्चित नहीं हैं कि सभी तीन वर्गों के संयोजन के दोनों तरीकों:

StackADT - push

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

तो StackArray - push अंदर, मैं कुछ इस तरह कर दूँगा - वे क्या हैं मानते हैं।

मैं इस डिजाइन समस्या को कैसे हल कर सकता हूं? या कम से कम इसे "सर्वोत्तम अभ्यास" के साथ संरेखित करें यदि ऐसा कोई है।

Answer 1

जब हम कपोल-कल्पना के बारे में बात कर रहे हैं, हम क्या हम को लागू करने की कोशिश कर रहे हैं के मुख्य पहलुओं की पहचान करने की कोशिश करनी चाहिए। आम तौर पर, उन पहलुओं को एक इंटरफेस के रूप में प्रदर्शित किया जा सकता है।

के बाद से सी ++ में, जावा की तरह अन्य भाषाओं के विपरीत, हम एक विशिष्ट इंटरफ़ेस घोषणा वाक्य रचना की जरूरत नहीं है, हम शुद्ध आभासी कक्षाओं का उपयोग कर सकते हैं।

सामान्य रूप से बोल रहा है, एक ढेर एक 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> का उपयोग करना होगा, लेकिन मुझे लगता है कि यह आपके अभ्यास का लक्ष्य नहीं है (अभी तक)।