JavaScript数据结构5——栈

栈仅允许在一头进行插入和删除；
以下是栈的顺序结构实现：

function Node(data) {
        this.data = data;
    }
    function Stack(){
        this.top = -1;
        this.data = [];
    }
    Stack.prototype.push = function(node){
        this.top++;
        this.data[this.top] = node;
        return 0;
    };
    Stack.prototype.pop = function(){
        if(this.top==-1){
            return -1;
        }
        var data = this.data[this.top];
        this.data[this.top] = null;
        this.top--;
        return data;
    };
    //遍历方法
    Stack.prototype.ergodic = function(){
        var data = '';
        for (var i = 0; i < this.data.length; i++) {
            if(this.data[i]!=null){
                data += this.data[i].data+' ';
            }
        }
        return data;
    };
    Stack.prototype.length = function () {
        var i = 0;
        while (this.data[i]!=null){
            i++;
        }
        return i;
    };
console.info('初始化一个stack');
var stack = new Stack(20);
console.info('推入一个元素1');
stack.push(new Node(1));
stack.ergodic();
console.info('推出');
stack.pop();
stack.ergodic();

打印后输出

初始化一个stack
推入一个元素1
Node { data: 1 }
推出
[Finished in 0.1s]

以下是链式的实现

function Node(data) {
    this.data = data;
}
function Stack(){
    this.top = this;
}
Stack.prototype.push = function(node){
    node.next = this.top;
    this.top = node;
}
Stack.prototype.pop = function(){
    this.top = this.top.next;
}
//遍历方法
Stack.prototype.ergodic = function(){
    var string = '';
    var elem = this.top;
    while(elem!=this){
        console.info(elem.data);
        elem = elem.next;
    }
}
console.info('初始化一个stack');
var stack = new Stack(20);
stack.push(new Node(1));
stack.push(new Node(2));
stack.push(new Node(4));
stack.push(new Node(5));
stack.ergodic();
console.info('推出');
stack.pop();
stack.ergodic();

打印输出

初始化一个stack
5
4
2
1
推出
4
2
1

实现双向共享堆栈

//共享堆栈
function Node(data) {
    this.data = data;
}
function Stack(maxSize){
    this.maxSize =maxSize;
    this.data = new Array(maxSize);
    this.top1 = -1;
    this.top2 = maxSize;
}
Stack.prototype.push = function(node,instance){
    if(this.top1+1 == this.top2){
        return 1;
    }
    if(instance ==1){
        this.top1++;
        this.data[this.top1] = node;
        return 0;
    }
    if(instance==2){
        this.top2--;
        this.data[this.top2] = node;
        return 0;
    }
    return 1;
}
Stack.prototype.pop = function(instance){
    if(this.top1==-1||this.top2 == this.maxSize){
        return 1;
    }
    if(instance ==1){
        this.data[this.top1] = undefined;
        this.top1--;
        return 0;
    }
    if(instance == 2){
        this.data[this.top2] == undefined;
        this.top2++;
        return 0;
    }
    return 1;
}
Stack.prototype.ergodic = function(instance){
    var string = '';
    if(instance ==1){
        for (var i = 0; i <= this.top1; i++) {
            string+=this.data[i].data;
        }
    }
    if(instance ==2){
        for (var i = this.maxSize-1; i >= this.top2; i--) {
            string+=this.data[i].data;
        }
    }
    console.info(string+'(最外面的是栈头)');
}
var stack = new Stack(100);
stack.push(new Node(1),1);
stack.push(new Node(2),1);
stack.push(new Node(3),1);
stack.push(new Node(4),2);
stack.push(new Node(5),2);
stack.push(new Node(6),2);
stack.ergodic(1);
stack.ergodic(2);
stack.pop(1);
stack.ergodic(1);

打印结果

123(最外面的是栈头)
456(最外面的是栈头)
12(最外面的是栈头)