时间戳

首页 > 解决方案 > 使用链表在 C++ 中实现堆栈

c++ - 使用链表在 C++ 中实现堆栈

问题描述

所以我正在尝试使用链表和类来实现堆栈。现在我有 6 个不同的文件：node.h、node.cpp、LL.h、LL.cpp、Stack.h 和 Stack.cpp。我想完成 Stack.h 和 Stack.cpp 文件，以便它们可以正常工作。我已经实现了链表函数，它们可以正常工作。这是代码：

节点.h：

// node.h

class node { // node class used in the LL (linked list) class
    private:
        node * next; // Pointer to next node of an LL
        int data;    // integer data stored in this node

    public:
        node(int x, node * n);  // Constructor
        ~node();                // Destructor
        void set_data(int x);   // Change the data of this node
        void set_next(node * n);// Change the next pointer of this node
        int get_data();         // Access the data of this node
        node * get_next();      // Access the next pointer of this node
};

LL.h：

// LL.h
#include "node.h"

// Linked list class, used in the Stack class
class LL {
    private:
        node * head; // pointer to first node
        node * tail; // pointer to last node

    public:
        LL(); // Constructor
        ~LL(); // Destructor
        void prepend(int value); // add a node to the beginning of the LL
        int removeHead();        // remove the first node of the LL
        void print();            // print the elements of the LL
    node * get_head();       // access the pointer to the first node of the LL
};

堆栈.h：

// Stack.h
#include "LL.h"

class Stack {
private:
    LL_t intlist;

public:

    Stack();    // Constructor
    ~Stack();       // Destructor

    void push(int value);
    int pop();      
    int isEmpty();
    void print();
};

最后，Stack.cpp：

// Stack.cpp
#include "Stack.h"
#include <stdio.h>

Stack::Stack() {
    head= NULL;
    tail= NULL;
}

Stack::~Stack() {
    delete intlist;
}

int Stack::isEmpty() {
    return (head==NULL);
}

void Stack::push(int value) {

    head= value;
}

int Stack::pop() {

    if ( !isEmpty() ) {
        int temp= tail->get_data();
        delete tail;
        return temp;    
    }
    return -1;
}

我有编译问题。它说 get_data() 未定义并且“head”和“tail”未定义，即使我在 Stack.h 和 LL.h 中有“#include”LL.h“”，我也有“#include”node.h " "，所以它们都建立在彼此的基础上，所以它应该可以正常工作吗？我希望它能够编译，以便查看我是否正确实现了 Stack.h 和 Stack.cpp。您是否发现我实施它们的方式有任何问题？如果是这样，你能指出它们吗？另外，关于我为什么会遇到这些编译问题的任何想法？任何帮助表示赞赏！

标签： c++functionmethodslinked-liststack

解决方案

让我们看看你的实际问题

Stack::Stack() {
    head= NULL;
    tail= NULL;
}

导致错误"head" and "tail" is undefined。现在看看头文件，和的声明在head哪里tail？回答，在LL课堂上不是在Stack课堂上。LL初始化是类的责任，head它tail在LL类默认构造函数中执行。所以你的Stack构造函数应该是这样的

Stack::Stack() {
}

每当您有一个包含另一个类的类的构造函数时，都会调用另一个类的构造函数。在Stack默认构造函数的情况下，LL隐式调用 for ，这会为您初始化head和tail。你不必做任何事情。

现在让我们看看更多的实现。

Stack::~Stack() {
    delete intlist;
}

intList不是指针，所以不能删除。很明显，您正在尝试为您的列表“调用”析构函数，但就像构造函数一样，这会自动发生。你的析构函数应该是这样的

Stack::~Stack() {
}

或者您可以（可能应该）完全删除它。

继续

int Stack::isEmpty() {
    return (head==NULL);
}

您再次尝试访问head无法访问的地方。你的Stack类有一个LL intlist对象，这就是它应该使用的对象，所以（例如）

int Stack::isEmpty() {
    return intlist.get_head() == NULL;
}

小事在这里

void Stack::push(int value) {
    head= value;
}

应该

void Stack::push(int value) {
    intlist.prepend(value);
}

使用堆栈拥有的对象（the intlist）而不是其他对象的内部。

剩下的就交给你吧。但是你必须了解你的班级设计中存在的职责划分。类Stack不应该（也不能）关注LL类的内部。所有Stack需要执行的操作都应该可以通过LL类的公共接口来实现。如果不是，那么LL就是需要更改的类。

另请注意，您的pop实现不仅在执行上是错误的，而且在概念上也是错误的。Pop应该删除列表的头部，而不是尾部。堆栈是一个 LIFO 列表（后进先出），因此pop会删除最近添加的项目。现在看这个LL类有一个removeHead方法（提示，提示）。

推荐阅读