c++ - 将双向链表与 C++ 中的 Stack 和 Queue 类链接起来

Question

所以我有一个任务，我需要创建一个双向链表，然后创建一个堆栈和队列类，并从 linkedlist 类继承，以便创建一个 RPN 计算器。到目前为止，我已经创建了我的双向链表类和另一个类。但是，我无法理解如何继承链表类并将其与堆栈和队列一起使用。我将提供我目前所拥有的。

我已经去补习了，但没有得到太多帮助，所以我想我会寻求一些额外的帮助，不希望为我完成家庭作业，而只是指出正确的方向。

Stack.h

using std::iterator;
using std::vector;
using std::string;

template<class T>
class Stack : public vector<T>
{
private:
    T getElement(bool erase);
    typename std::vector<T> ::iterator pEnd;
    T top;

public:
    Stack();
    T pop();
    T peek();
    void push(T elem);
};



template<class T>
Stack<T>::Stack()
{

}

template<class T>
void Stack<T>::push(T elem)
{
    this->push_back(elem);

}

template<class T>
T Stack<T>::peek()
{
    return this->getElement(false);
}

template<class T>
T Stack<T>::pop()
{
    return this->getElement(true);
}

template<class T>
T Stack<T>::getElement(bool erase)
{
    this->pEnd = this->end() - 1;
    T tmp;
    if (this->size() > 0)
    {
        tmp = *this->pEnd;
        if (erase) {
            this->erase(pEnd);
        }
    }

    return tmp;

}

Queue.h

using namespace std;

class Queue
{

private:
    int items[MAXQUEUE];
    int head;
    int tail;

public:
    Queue();
    bool isEmpty();
    bool isFull();
    bool enqueue(int item);
    int dequeue();
    int peek();
};



Queue::Queue()
    :head(QEMPTY), tail(QEMPTY)
{

}

bool Queue::isEmpty()
{
    return this->head == this->tail;

}

bool Queue::isFull()
{

    return this->tail == MAXQUEUE;
}

bool Queue::enqueue(int item)
{
    if (this->isFull())
        return false;

    this->items[this->tail] = item;
    tail = (tail + 1) % MAXQUEUE;
    return true;

}

int Queue::dequeue()
{
    if (this->isEmpty())
        return EMPTY;

    int item = this->items[head];
    this->head = (this->head + 1) % MAXQUEUE;
    return item;
}

int Queue::peek() {

    return this->tail;
}

doublylinkedlist.h

 using std::iterator;
using std::vector;
using std::string;



/*START OF NODE CLASS*/
/*---------------------------------------------*/
template<class T>
struct Node
{

    T Data;
    T Search;
    T value;
    Node<T>*Next;
    Node<T>*Prev;
};


template<class T>
class LinkedList
{
private:
    Node<T> *Head;
public:
    LinkedList();
    void addNode(T Data);
    void deleteNode(T Search);
    void insert(T Search, T value);
    void printListBackwards();
    void printListForwards();
};
template<class T>
LinkedList<T>::LinkedList()
{
    this->Head = NULL;

}

template<class T>
void LinkedList<T>::addNode(T data)
{

    if (Head == NULL)
    {
        Head = new Node<T>;
        Head->Data = data;
        Head->Next = NULL;
        Head->Prev = NULL;

    }
    else
    {
        Node<T>*p = this->Head;


        while (p->Next != NULL)

            p = p->Next;

        Node<T>*n = new Node<T>;
        n->Data = data;
        n->Next = NULL;
        p->Next = n;
        n->Prev = p;
    }


}

template<class T>
void LinkedList<T>::insert(T Search, T value)
{

    Node *p = Head;
    while (p->Data != Search)
    {
        p = p->Next;
    }

    Node *n = new Node;
    n->Data = value;
    n->Next = p->Next;
    p->Next = n;

}

template<class T>
void LinkedList<T>::deleteNode(T Search)
{
    Node *p = Head;
    while (p->Next->Data != Search)
    {
        p = p->Next;
    }

    Node *delPtr = p->Next;
    p->Next = p->Next->Next;

    delete delPtr;
}

template<class T>
void LinkedList<T>::printListBackwards()
{
    Node<T> *p = Head;

    while (p->Next != NULL)
    {

        p = p->Next;
    }
    while (p != NULL)
    {
        cout << p->Data<< endl;
        p = p->Prev;
    }
}

template<class T>
void LinkedList<T>::printListForwards()
{

    Node<T> *p = Head;
    while (p != NULL)
    {
        cout << p->Data << endl;
        p = p->Next;
    }
}

Answer 1

双向链表可以在头部或尾部添加，也可以在尾部移除。

堆栈在一端(头部？)压入并在同一端(头部)弹出。

队列在一端(尾部)压入并在另一端(头部)弹出。