如何返回堆栈 c++ 中顶部对象的引用

Question

我正在尝试使用模板为我的 Stack 类创建一个 peek((/top(( 函数，并且遇到了这个问题，我不确定如何返回堆栈的最顶层对象。到目前为止，我已经能够检查顶部对象是否为空，如果不是，则移动当前指针指向堆栈的头部并返回该指针的数据。但是，这返回了一个 int，我想返回对对象的引用，而不是对象中的数据。关于如何做到这一点的任何想法？

Stack.h

#include "LinkedList.h"
#include <cstdlib>
#include <iostream> 
template <typename T>
class LStack
{
public:
//mutator member functions
LStack(){numofstacks = 0;}
~LStack(){}
void push(const T& obj) //insert obj at the top of the stack
{
data.add_to_head(obj);
numofstacks = numofstacks + 1;
}
T pop() //remove and return the top object from the stack, error if stack is empty
{   
if (is_empty()){
std::cout << "Stack is empty" << std::endl;
exit(0);
}
else
{
data.remove_from_head();
numofstacks = numofstacks - 1;
if (is_empty()){
exit(0);
}
else{   
data.move_to_head();
return data.get_current();
}
}           
}
//return a reference to the ***OBJECT** at the top of the stack, NULL if the stack is empty, (also refered to as top())
T& peek() 
{
if (is_empty()){
std::cout << "Stack is empty" << std::endl;
exit(0);
}
else{
data.move_to_head();
return data.get_current();  // Need to return reference to object here
}
}
bool is_empty() const //return a boolean indicating whether the stack is empty
{
return (size() == 0);
}
int size() const  //return the number of objects in the stack
{
return numofstacks; 
}
private:
LinkedList<T> data;
int used;
int numofstacks;
}; 

链接列表

#include "Node.h"
#include <cstdlib>
#include <iostream> 
template <typename T>
class LinkedList
{
public:     
LinkedList() //constructor
{
head = NULL;
tail = NULL;
current = NULL;
list_length=0;
}
~LinkedList()//destructor since we're creating the linked list on the heap
{
while (head != NULL)
{
remove_from_head();
}
tail = NULL;//not sure if in or out of while loop
}
LinkedList(T& item)
{
head = new Node<T>(item);
tail = head;
current = tail;
list_length = 1;
}
void add_to_head(const T& item)
{
if (list_length == 0){ //if list is empty
head = new Node<T>(item);
tail = head;
current = tail;
list_length = 1;
}
else //Else if list is not empty.. Insert node at the head
{       
Node<T>* head_insert = new Node<T>(item);       
head->set_prev(head_insert);
head_insert->set_next(head);
head = head_insert;
list_length++;
head_insert = NULL;
}
}
void add_to_tail(const T& item)
{           
if (list_length == 0){
head = new Node<T>(item);
tail = head;
current = tail;
list_length = 1;
}
else  //insert node at tail 
{               
Node<T>* tail_insert = new Node<T>(item);
tail->set_next(tail_insert);
tail_insert->set_prev(tail);
tail = tail_insert;
list_length++;
tail_insert = NULL;         
}
}
void remove_from_head()
{
if (list_length == 0){
return;
}
else if (list_length == 1){
delete head;
head = NULL;
tail = NULL;
current = NULL;
list_length--;
return;
}
else
{   
Node<T>* temp_head = head;
head = temp_head->get_next();
delete temp_head;
list_length--;
temp_head = NULL;
}
}
void remove_from_tail()
{
if (list_length == 0){
return;
}
else if (list_length == 1)
{
delete head;
head = NULL;
tail = NULL;
current = NULL;
list_length--;
return;
}
else
{
Node<T>* temp_tail = tail;
tail = temp_tail->get_prev();
delete temp_tail;
list_length--;
temp_tail = NULL;               
}
}   
std::size_t size()
{
return list_length;
}
T get_current() 
{
return current->get_data();
}                       
void forward()
{
current = current->get_next();
}
void back()
{
current = current->get_prev();
}
void move_to_head()
{
current = head;
}
void move_to_tail()
{
current = tail;
}
private: //private members
Node<T>* head; //point to start of list
Node<T>* tail; //point to end of list
Node<T>* current; //optional - used to refer to a node in our list
std::size_t list_length;
};

错误信息

在 main.cpp：1：0 包含的文件中： LStack.h： 在实例化 'T& LStack：:p eek(( [with T = int]'： main.cpp：29：19： 需要从 此处 LStack.h：52：28：错误：无法绑定 的非常量左值引用 键入"int&"到类型为"int"的右值 返回 data.get_current((;需要在此处返回对对象的引用

Answer 1

链表中的此方法：

T get_current()

返回类型 T 的右值。根据定义，右值是常量。将get_current的原型更改为：

T& get_current()

您可能还需要更改 Node：：get_data 的返回类型以返回引用。

Answer 2

简短的回答是，尽管在你看来你想这样做，但你真的没有，因为没有办法干净利落地做到这一点。即使pop()按值返回顶部对象也是非常成问题的。特别是，如果存储类型的复制构造函数可以抛出，这几乎是一场等待发生的灾难 - 如果复制构造函数在尝试复制返回值时抛出，则情况基本上是不可恢复的。该值已从堆栈中删除，但未返回给调用方，因此完全丢失。

标准库通过不让 pop 返回任何内容来解决这个问题。因此，您可以通过两个步骤从堆栈中弹出一个项目：首先使用top()获取堆栈上的顶部项目，然后使用pop()删除堆栈顶部的项目：

auto top_item = your_stack.top();
your_stack.pop();

如果复制构造函数在您尝试检索堆栈顶部项时引发，则your_stack.pop()不会执行，因此堆栈不会受到影响 - 顶部项保留在那里。仅当您已成功将顶部项目检索到top_item中时，才会执行pop()。

不幸的是，这使用起来有点笨拙。

更不幸的是，由于我们使用两个步骤来弹出顶部项目，因此基本上不可能使这个线程安全 - 为此，您几乎必须确保检索项目并将其从堆栈中删除是单个原子操作 - 要么两者都发生而没有任何其他干扰，要么根本不发生。

有一个设计可以满足这一要求，而且(至少可以说(使用起来并不那么笨拙：

void pop(T &t) { 
t = storage.back();
storage.pop_back();
}

与前面使用标准堆栈的示例非常相似，如果t=storage.back();行引发异常，则storage.pop_back();根本不会执行 - 您尚未检索项目，但堆栈上的项目不受干扰。

对于简单的并发堆栈，您可以添加互斥锁并将返回类型更改为bool，指示操作是否成功(同样，您不能遵循典型的单线程模式"if (！stack.empty((( stack.pop(("，因为您又回到了使用两个单独的操作，所以即使您找到一个非空堆栈，当您尝试弹出它时， 其他线程可能已经这样做了，并且您尝试弹出将失败。