java - 我们可以在java中使用数组或List创建自己的堆栈数据结构实现吗？

Question

我在面试中被问了一个问题，如下。

我们可以在不使用数组、列表甚至节点类型的情况下实现自己的堆栈数据结构吗？

可能吗？

Answer 1

您可以使用调用堆栈，但这在大多数情况下没有用。

假设您有一个交互式应用程序，用户可以在其中选择推送或弹出元素。

您将拥有一个带有单个局部变量的方法，该变量保存堆栈的顶部元素。

该方法将要求用户选择是弹出最后一个元素还是推送新元素。

如果用户选择推送，该方法将对自身进行递归调用，将推送的元素作为参数传递(将存储在被调用方法的局部变量中)。

如果用户选择 pop，该方法会将其局部变量返回给调用方法。

这是一些伪代码:

public static Object stack (Object element)
{
    Object top = element;

    int input = 0;
    while (input != 2) {
        input = ... // get user input - 1 for push 2 for pop
        if (input == 1) {
            Object newElement = ... // get input from user
            Object poppedElement = stack (newElement); // push the new element
        } 
    }
    return top; // pop the top of the stack
}