algorithm - スタックのみを使用してリストを実装する方法はありますか?

Question

スタックのみを使用してリストを実装する方法があるのだろうか。ある？

Answer 1

2 つのスタックを使用して (非効率的な) リストを作成できます。アイテムを挿入または取得する必要がある場合は、適切なインデックスが得られるまでアイテムをあるスタックから別のスタックに移動するだけです。

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

リストとは、キューのことですか?スタックとリストの間の接続が表示されないため...

もしそうなら、あなたは2つのスタックを使うことができます: s1 san s2 、それらが下から下にあると想像してください。s1 はリストの先頭で、s2 は末尾です。このリストの機能:

1. insert(ele): s2.push_back(ele) を使用するだけ
2. pop():s1 が空でない場合は s1.pop(); そうでない場合は、s2 から各要素をポップして s1 にプッシュし、次に s1.pop()
3. size():s1.size()+s2.size()
4. ...