java - 使用递归实现 Stack 的 Pop 方法

Question

我正在自学java。这两天我一直在研究数据结构。我正在阅读“Java 中的数据结构和算法”一书。我有一个练习有问题。它要求使用递归实现 pop 方法，以便在调用该方法时它应该立即删除所有项目。有人可以帮忙吗？关于如何做到这一点的指针将不胜感激。谢谢。（以下是当前实现的pop方法）。

    public double pop() // take item from top of stack
{


        return stackArray[top--]; // access item, decrement top
}

Answer 1

首先，IMO 您应该了解如何实现此方法的非递归对应物。

它可以是这样的：

public void popAll() {

  while(!stack.isEmpty()) {
      stack.pop();
  }
}

一旦你理解了这一点，递归版本应该很容易：

public void popAllRecursive() {

     if(stack.isEmpty()) {
        //nothing to remove, return
        return;
     }
     stack.pop();  // remove one stack element

     popAllRecursive(); // recursive invocation of your method

}

由于它是一个练习，我只是为您提供一个想法并将实现留给您（您可以考虑在类 Stack 中提供方法并使用顶部计数器和 stackArray - 您的堆栈的实现。

希望这可以帮助

Answer 2

您需要考虑堆栈中没有任何内容的基本情况，即stack.pop() == null.

对于递归情况，它非常直观，因为您只需要递归调用pop()直到满足基本情况。

Answer 3

重复调用pop()直到堆栈结束。由于您没有提到数据的存储方式，因此无法帮助您提供代码。

Answer 4

谢谢大家，我解决了这个问题。不知道是否有效，但我确实喜欢以下内容：

    public void pop()
{

    if(isEmpty()){

        return;
    }

    if (top>=0){

        stackArray[top] = stackArray[top--];
        pop();
    }


}