在哪裏刪除節點 - >日期在鏈接列表實現的堆棧

Question

當我實現pop（）和析構函數的堆棧持有節點，我應該刪除node->數據之前刪除節點本身或者我應該刪除讓創建節點​​ - >數據的調用者刪除節點 - >數據？如果讓主叫方這樣做，主叫方何時以及如何刪除數據？它應該以這種方式調用：{data = stack.top（）;刪除數據; stack.pop（）;}？

我還沒有看到任何刪除節點 - >數據的代碼，既不在pop（）的實現中，也不在調用者函數中。這就是我困惑的原因。

這裏我複製我使用鏈接列表實現的堆棧。請參閱pop（）和〜stack（）我的問題的註釋。謝謝你的幫助。

typedef struct Node_t{ 
    struct Node_t* next; 
    void* data; 
}Node; 

class stack { 
public: 
    stack(): _head(null), _size(0){} 
    ~stack(); 
    void push(void* data); 
    void pop(); 
    void* top(); 
    bool empty(); 
    stack(const stack& original); 
    stack& operator=(const stack& original);  
private: 
    Node* _head;  
    int _size; 
}; 
stack::~stack{ 
Node* next = null; 
while(_head){ 
     next = _head->next; 
     //should delete _head->_data??? 
     delete _head;      
     _head = next; 
} 
_size = 0; 
} 
void stack::push(void* data){ 
    Node* elem = new Node; 
    elem->data = data; 
    elem->next = _head; 
    _head = elem; 
    _size++; 
}  

void stack::pop(){ 
Node* next = NULL; 
if (_head) { 
    next = _head->next; 
    //should delete _head->_data??? 
    delete _head; 
    _head = next;   
    _size--; 
} 
}  

void* stack::top() const{ 
if (_head) { 
    return _head->_data; 
}   
} 

bool stack::empty(){ 
    if(_size>0) return false; 
    else return true; 
} 

Answer 1

你的數據是一個指向其他地方的指針。這裏的策略是：你在堆棧外創建一個數據對象，並將數據指針推入你的堆棧。所以，通過對稱性，刪除數據的控制也應該存在於你的堆棧中。如果你不需要它，你需要明確地刪除它。例如：

stack s; 
char mydata[] = {'a','b','c'}; 
s.push((void*)mydata); 
//do things 
s.pop(); 
delete [] mydata; 

如果你真的想控制棧中的數據（通過它可能不是一個好主意，假設您的數據可能在其他地方使用），也有問題。由於數據類型是無效的*，因此您可能無法'安全地'刪除它。看到這個線程Is it safe to delete a void pointer?

Answer 2

有幾個部分，以這樣的回答：

1. 對於實際的編程，沒有理由永遠建立在那裏這些數據結構已經由標準庫提供你自己的數據結構。

2. 如果你必須建立自己的數據結構作爲學習練習，原則上你可以有任何你希望的分配和刪除的語義。

3. 但是，如果您必須構建自己的堆棧，我強烈建議使用與標準庫stack相同的語義，它使用複製和引用語義來避免在用戶代碼中顯式分配和刪除。

遵循標準庫語義提高了一致性，減少了理解接口的認知負載並大大降低了內存泄漏的機會。