language-agnostic - 使用栈实现数组

Question

我的编程语言没有数组、列表、指针、eval 和可变变量。它拥有的一切:

• 您从大多数编程语言中了解到的普通变量:它们都有确切的名称和值。

• 一个堆栈。提供的函数有:push(向栈顶添加元素)、pop(从栈顶移除元素、获取值)和empty(检查栈是否为空)

我的语言是图灵完备的。 (实现了基本算术、条件跳转等)这意味着，一定可以实现某种列表或数组，对吧？

但我不知道如何...

我想要实现的目标:创建一个可以检索和/或更改堆栈的元素 x 的函数。

我可以很容易地将这个函数添加到我的语言的实现中，在解释器中，但我想用我的编程语言来实现。

• “解决方案”一(访问一个元素x，从栈顶开始计数)

创建一个循环。从栈顶弹出元素 x 次。弹出的最后一个元素是元素号 x。我最终得到了一个被破坏的堆栈。

• 解决方案二:

与上面的操作相同，但将所有弹出的值存储在第二个 堆栈中。然后你可以在完成后将所有元素移回。但你知道吗？我没有第二个堆栈!

Answer 1

听起来像是一道家庭作业题，因为它涉及计算机科学的随机部分...

我认为您会希望使用递归来执行此操作。假设我有这样的东西..

Queue globalQueue = new Queue();

然后我可以得到像这样获取元素 X 的代码

public Object findElement(stepsToTake s) {

    if (queue.empty()) {
        throw new EmptyQueueYouFailException();
    }

    Object o = queue.pop();


   if (s == 0) {
        queue.push(o);
        return o;
    }

    Object actualResult = findElement( s - 1 );
    //restore this element to the stack
    queue.push(o);
    //return actual result
    return actualResult;
}

所以很有可能是我犯了一些错误……还没有想好。特别担心我会因为我的调用顺序而重新排序堆栈..

希望这能让您沿着正确的路线思考以获得解决方案？