algorithm - 有没有办法只使用堆栈来实现列表？

Question

我想知道是否有一种方法可以仅使用堆栈来实现列表。在那儿？

Answer 1

您可以使用两个堆栈制作一个（低效的）列表。当您需要插入或检索项目时，只需将项目从一个堆栈移动到另一个堆栈，直到获得正确的索引。

这是 JavaScript 中的一个示例：

function List() {
    this.stack1 = [];
    this.stack2 = [];

    Object.defineProperty(this, 'length', {
        get: function() { return this.stack1.length + this.stack2.length; }
    });
}

List.prototype.item = function(index) {
    if(index < this.stack1.length) {
        while(index < this.stack1.length - 1) {
            this.stack2.push(this.stack1.pop());
        }

        return this.stack1[this.stack1.length - 1];
    }

    while(index > this.stack1.length) {
        this.stack1.push(this.stack2.pop());
    }

    return this.stack2[this.stack2.length - 1];
};

List.prototype.insert = function(item, index) {
    this.item(index - 1);
    this.stack1.push(item);
};

Answer 2

列表，你的意思是队列吗？因为我看不到堆栈和列表之间的任何连接......

如果是这样，您可以使用两个堆栈： s1 san s2 ，想象它们是从下到下的。s1 是列表的头部，s2 是尾部。此列表的功能：

1. 插入（ele）：只需使用 s2.push_back（ele）
2. pop():如果 s1 不为空，s1.pop();否则从 s2 中弹出每个元素并推入 s1，然后 s1.pop()
3. 尺寸():s1.size()+s2.size()
4. ...