如何在C++中返回栈底元素？

Question

我正在尝试向我的“堆栈”类添加一个附加方法，该方法将返回堆栈中的底部元素。然而..我只是很难理解这个问题。这是我迄今为止在 stack.cpp 中的代码，但它无法正常工作：

bool Stack::bot(StackItemType& stackBottom){
  if (isEmpty()) return false;

  StackItems *temp = top;
  while (temp != NULL) {
    temp = temp->below;
  }

  stackBottom = temp->item;
  return true;
} // end bottom

有帮助吗？谢谢。

Answer 1

堆栈设计为仅暴露其顶部。就你而言，它没有“底部”。如果您想访问集合的两端，请不要使用堆栈！ （也许您更喜欢双端队列或列表？）

Answer 2

您是否考虑过使用另一种数据结构。堆栈确实不适合这样做。不过，我不会成为一个混蛋而不回答你的问题。

乍一看，您的代码在逻辑上是合理的，假设您使用链接列表实现堆栈并向其添加将元素推送到列表头部。您的代码的问题是 temp 在离开 while 循环时为空。尝试访问空指针是一个错误。

如果将 while 条件更改为使用 temp->below != NULL，则 temp 将在离开 while 循环之前指向有效元素。

bool Stack::bot(StackItemType& stackBottom){
  if (isEmpty()) return false;

  StackItems *temp = top;
  while (temp->below != NULL) {
    temp = temp->below;
  }

  stackBottom = temp->item;
  return true;
} // end bottom

Answer 3

我认为你必须这样做

StackItems *temp = top;
while (temp->below != NULL) {
   temp = temp->below;
 }

但是堆栈是后进先出的。这里不是:p

Answer 4

鉴于您使用链接列表作为底层存储，我只需在每次推送到空堆栈时设置底部指针，并在弹出最后一项时取消设置它。

如果您使用数组（希望是动态的）作为底层存储，您只需索引第一项即可。