使用鏈表的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; 
} 

當然，現在你必須確保當你完成所分配的節點free'd。這應該在彈出所有節點的stack的析構函數中完成，並且在pop中，您需要使用delete運算符來釋放內存。

Answer 2

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

該函數的問題是n有自動存儲期限，並且在函數返回後被銷燬。

相反，使用動態分配：

node* n = new node(x, top); 

Answer 3

除非這是一類編程作業，使用隨STL std::stack。