我正在尝试使用链表实现一个简单的堆栈。当我运行下面的代码时,我得到
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
为什么会这样呢?
这段代码是错误的:
void stack::push(int x) {
node n(x,top);
top = &n;
}
在这里,您创建一个局部变量,然后将top
设置为指向该变量。但是当函数返回时,局部变量不再存在,并且top
指向一些无效的内存。
您需要使用 new
运算符在堆上创建一个新node
:
void stack::push(int x) {
node* n = new node(x,top);
top = n;
}
当然,现在您必须确保分配的节点在完成后是空闲的。这应该在弹出所有节点的 stack
析构函数中完成,pop
您需要使用 delete
运算符来释放内存。
除非这是类的编程作业,否则请使用 STL 提供的 std::stack。
void stack::push(int x) {
node n(x,top);
top = &n;
}
此函数的问题在于 n 具有自动存储持续时间,并且在函数返回后被销毁。
请改用动态分配:
node* n = new node(x, top);