Not sure whether to use inheritance when trying to extend my stack function

Question

I wrote a stack before. Basically, I had two classes, Node and Stack. This stack can just push, pop and check the head of the stack. The code is shown below:

#include <iostream>

using namespace std;

template<class Datatype>
class Node
{
    public:
        Node()
        {
            next = NULL;
            prev = NULL;
        }
        Node* getNext()
        {
            return next;
        }
        Node* getPrev()
        {
            return prev;
        }
        Datatype* getData()
        {
            return &data;
        }
        void changeNext()
        {
            next = NULL;
        }
        void changeNext(Node& nextNode)
        {
            next = &nextNode;
        }
        void changePrev()
        {
            prev = NULL;
        }
        void changePrev(Node& prevNode)
        {
            prev = &prevNode;
        }
        Node* addNext(Node &);
        Node* addPrev(Node &);
        void nodeDel();
        void addData(Datatype &);
    private:
        Node* next;
        Node* prev;
        Datatype data;
};

template<class Datatype>
class Stack
{
    public:
        Stack() : head( NULL )
        {

        }
        int push(Datatype &);
        int pop(Datatype &);
        Datatype* peek();
    private:
        Node<Datatype> *head;
};

template <class Datatype>
Node<Datatype>* Node<Datatype>::addNext(Node<Datatype>& exi_node)
{
    if (exi_node.getNext() == NULL)
    {
        changePrev(exi_node);
        exi_node.changeNext(*this);
    }
    else
    {
        Node* next = exi_node.getNext();
        changePrev(exi_node);
        changeNext(*next);
        exi_node.changeNext(*this);
        next -> changePrev(*this);
    }
    return &exi_node;
}

template <class Datatype>
Node<Datatype>* Node<Datatype>::addPrev(Node<Datatype>& exi_node)
{
    if (exi_node.getPrev() == NULL)
    {
        changeNext(exi_node);
        exi_node.changePrev(*this);
    }
    else
    {
        Node* prev = exi_node.getPrev();
        changePrev(*prev);
        changeNext(exi_node);
        exi_node.changePrev(*this);
        prev -> changeNext(*this);
    }
    return &exi_node;
}

template<class Datatype>
void Node<Datatype>::nodeDel()
{
    if (prev == NULL && next == NULL)
        ;
    else if (prev == NULL)
    {
        Node* next = getNext();
        next -> changePrev();
    }
    else if (next == NULL)
    {
        Node* prev = getPrev();
        prev -> changeNext();
    }
    else
    {
        Node* next = getNext();
        Node* prev = getPrev();
        next -> changePrev(*prev);
        prev -> changeNext(*next);  
    }
    delete this;
    return;
}

template <class Datatype>
void Node<Datatype>::addData(Datatype &new_data)
{
    data = new_data;
}

template <class Datatype>
int Stack<Datatype>::push(Datatype &new_data)
{
    Node<Datatype> *pt_node = new Node<Datatype>;
    if (pt_node == NULL)
        return -1;

    pt_node -> addData(new_data);

    if (head == NULL)
        head = pt_node;
    else
    {
        pt_node -> addPrev(*head);
        head = pt_node;
    }

    cout << *(head -> getData()) << endl;

    return 0;
}

template <class Datatype>
int Stack<Datatype>::pop(Datatype &pop_data)
{
    if (head == NULL)
        return 0;

    pop_data = *(head -> getData());

    if (head -> getNext() == NULL)
    {
        delete head;
        head = NULL;
    }
    else
    {
        Node<Datatype>* temp = head;
        head = head -> getNext();
        delete temp;
    }

    return 1;
}

template <class Datatype>
Datatype* Stack<Datatype>::peek()
{
    return (this->head)->getData();
}

It's a pretty simple stack. The Stack class has some interface for users and also a pointer points to the first Node. Node class has two pointers pointing to both direction and also a data field. Now, I want to add a function to my Stack, which is to find the min value in the stack within O(1). One method is to add a field "local_min" in Node class, which records the minimum value beneath itself. In this way, pop(), push(), find_min() can all be done in O(1). My intuition is to have inheritance of both Node and Stack, because I only need to add a new function. However, I feel this very inconvenient. I have to rewrite almost all the functions. The pointer in both Node and Stack pointed to class Node. If I use a new class, like New_Node, all the thing has to be changed. Are there any good ways for me to do this extension? I really feel like inheritance should be working well here. However, I cannot figure it out.

Answer 1

Your Stack is not written in a way that facilitates clean OO re-use: you haven't got a virtual destructor, and the member functions that derived types may wish to override aren't virtual either (specifically push and pop). So, it is cleaner to write a new class that uses Composition - storing a Stack object as a data member. Then there's no need to change Node - you can just add a Stack<Node*> to your StackWithMin class, and push/pop an extra Node* only when the data Stack pushes/pops a Node that changes the min. For example, after pushing 3, 7, 5, 2, 3, your StackWithMin data members would be:

Stack<Data>   Stack<Node*>
[0] 3         &[0]
[1] 7         &[3]
[2] 5
[3] 2
[4] 3

This encodes that the current min is at &[3], and if a pop removes that element then it should be popped from the Stack<Node*> too.

Separately, Node is a supporting type for Stack, and the definition need not be offered as part of the client-facing interface. To hide it, consider putting it in a namespace called something like Stack_Private, Stack_Support or Stack_Implementation so that clients know not to use, then you can reasonably make it a struct and get/set the data members directly instead of using accessor functions - that will make your code less verbose.

Answer 2

Sometimes in these situations you should use non-template base class. This base class can implement all functions which aren't depend of a given data type.

class Node
{
public:
    Node() : _next(nullptr), _prev(nullptr) {
    }
public:
    Node* getNext() {
        return _next;
    }
    Node* getPrev() {
        return _prev;
    }
    void setNext(Node *node) {
        _next = node;
    }
    void setPrev(Node *node) {
        _prev = node;
    }
private:
    Node* _next;
    Node* _prev;
};

template <typename Value>
class NodeWithType : public Node
{
public:
    NodeWithType() : Node() {
    }
public:
    const Value& getValue() const {
        return _value;
    }
    void setValue(const Value &value) {
        _value = value;
    }

public:
    Value _value;
};

Now, the stack class can use the value independent interface. This simplifies everything.