原始指針，棧和隊列

Question

我有以下問題二叉樹：

.... 

template class BinaryTree { private: template struct Node { T value; Node* left; Node* right; }; private: Node* root;

std::stack<Node<T>const *> stack; 

stack.push(root); 

while(false == stack.empty()) 
{ 
    Node<T>* node = stack.pop(); 

    this->visited(node->value); 

後，當我試圖執行廣度優先搜索： 模板 類二叉樹 { 私有： 模板 結構節點 { T值; Node * left; 節點*權利; }; private： Node * root;

std::stack<Node<T>const *> stack; 

stack.push(root); 

while(false == stack.empty()) 
{ 
    Node<T>* node = stack.pop(); 

    this->visited(node->value); 

我收到一個錯誤：

錯誤4錯誤C2440：初始化：不能從 '無效' 轉換爲「二叉樹::節點* C：\用戶\斯蒂芬\文檔\ Visual工作室2012 \項目\圖\二叉樹\ binarytree.cpp 152 1二叉樹

Answer 1

的問題是在這裏：

Node<T>* node = stack.pop(); 

pop()刪除元素，並返回void。事先使用top()。

Node<T>* node = stack.top(); 
stack.pop(); 

原來STL documentation解釋這種設計背後的原因：

One might wonder why pop() returns void, instead of value_type. That is, why must one use top() and pop() to examine and remove the top element, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use top() to inspect the value at the top of the stack.