有没有一种方法可以仅使用堆栈来实现列表？

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

的列表中，你的意思是排队becaue我看不到栈和列表之间的任何连接...

如果是这样，你可以使用两个叠加：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. ...