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 - 您的堆栈的实现。

希望对你有帮助