使用链表的C++堆栈

Question

我正在尝试使用链接列表实现一个简单的堆栈.当我运行下面的代码时,我明白了

6
<some random integer>

我一直在寻找我的错误几个小时而没有成功.我想某处有一个未经传播的变量,但我似乎无法找到它.

#include <iostream>

using namespace std;

class node {
    public:
        node operator = (const node&);
        node(int d,node* n): data(d), prev(n) {}
        node(){}
        node* prev;
        int data;
};

node node::operator = (const node &n) {
    node r(n.data, n.prev);
    return r;
}

class stack {
    public:
        stack();
        void push(int);
        int pop();
        bool empty();
    private:
        node* top;
};

stack::stack() {
    top = 0;
}

bool stack::empty() {
    return top == 0;
}

void stack::push(int x) {
    node n(x,top);
    top = &n;
}

int stack::pop() {
    if (!empty()) {
        node r = *top;
        //cout << "r.data: " << r.data << endl;
        top = top->prev;
        return r.data;
    }
    else {
        cout << "Stack empty!" << endl;
        return 0;
    }
}

int main() {
    stack a;
    a.push(5);
    a.push(6);
    cout << a.pop() << endl;
    cout << a.pop() << endl;
}

现在让我感到困惑的是,当我取消注释时

        //cout << "r.data: " << r.data << endl;

出于测试目的,输出更改为

r.data: 6
6
r.data: 6
6

为什么会这样？

Answer 1

这段代码错了:

void stack::push(int x) {
    node n(x,top);
    top = &n;
}

在这里创建一个局部变量,然后设置top为指向该变量.但是当函数返回时,局部变量不再存在,并top指向一些无效的内存.

您需要node使用new运算符在堆上创建新的:

void stack::push(int x) {
    node* n = new node(x,top);
    top = n;
}

当然,现在你必须确保完成时分配的节点是免费的.这应该在析构函数中完成stack,弹出所有节点,并且pop需要使用delete运算符来释放内存.