不确定在尝试扩展堆栈函数时是否使用继承

Question

我以前写过一堆。基本上，我有两个班，Node和Stack。这个堆栈只需推、弹和检查堆栈的头。守则如下：

#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();
}

这是一个相当简单的堆栈。Stack类为用户提供了一些界面，也有指向第一个节点的指针。Node类有两个指向两个方向的指针，也有一个数据字段。现在，我想向我的Stack中添加一个函数，即在O(1)中找到堆栈中的min值。一种方法是在Node类中添加一个字段"local_min“，它记录其下的最小值。这样，pop()、push()、find_min()都可以在O(1)中完成。我的直觉是继承Node和Stack，因为我只需要添加一个新函数。不过，我觉得这很不方便。我必须重写几乎所有的功能。Node和Stack中的指针指向Node类。如果我使用一个新的类，比如New_Node，那么所有的东西都必须改变。有什么好办法让我做这个分机吗？我真的觉得遗产继承在这里应该很管用。不过，我想不出来。

Answer 1

有时，在这些情况下，您应该使用非模板基类。这个基类可以实现不依赖于给定数据类型的所有函数。

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

现在，堆栈类可以使用与值无关的接口。这简化了一切。