数据结构与算法 （栈实现篇）

数据结构与算法 （栈实现篇）

在数据结构与算法中，栈(stack)又名堆栈，栈是一种受限的线性储存结构，只允许在一端加入元素和删除元素。这一端称为栈顶，加入元素称作入栈、压栈、进栈；删除元素又称作出栈、退栈。被删除元素的相邻元素会重新称为栈顶元素。栈遵循先进后出（FILO）的规则。

栈结构示意图

stack.png

栈结构使用

在编程语言中很多时候使用到栈的数据结构。例如函数栈结构。A函数调用B函数，B函数调用了C函数。语言执行先会把A函数、B函数、C函数依次进栈；待C函数执行完成出栈，B函数出栈，最后A函数完成出栈。

function.png

生活中具有比较多的类似于栈的结构，比如叠罗汉、子弹夹、文件叠在一起等等。理解栈结构原理对我们编程具有很大的帮助。下面会使用 JavaScript实现我们的栈结构。

实现栈结构的功能

• push(element)：push是进栈操作，其中element是需要进栈的元素，返回操作成功与否布尔值。
• pop()：pop移除栈顶元素操作，返回移除的栈顶元素。
• size()：获取栈中的栈元素数量，返回一个数字。
• isEmpty()：判断栈是否为空，返回一个布尔值。
• peek()：返回栈顶元素，但不移除栈顶元素。
• bottom()：返回栈底元素。
• clear()：清除所有栈元素，返回操作成功与否布尔值。

进栈与出栈流程

flow.png

ES6 栈结构代码

class Stack{
    constructor(){
        this.lists = [];
    }
    size(){
        return this.lists.length;
    }
    isEmpty(){
        return this.lists.length === 0;
    }
    peek(){
        const topIndex = this.size() -1;
        return this.lists[topIndex];
    }
    bottom(){
        return this.list[0];
    }
    push(element){
        this.lists.push(element);
        return true;
    }
    pop(){
        return this.lists.pop();
    }
    clear(){
        this.lists = [];
        return true;
    }
    toString(){
        let result = "";
        this.lists.forEach(value=>{
            result = result + ""+value;
        });
        return result;
    }
}

ES5 栈结构代码

通过ES5把功能函数可以绑定在对象的实例上，也可以把功能函数加在函数的原型链上

function Stack(){
    this.lists = [];
}
Stack.prototype.push = function(element){
    this.lists.push(element);
    return true;
}
Stack.prototype.pop = function(){
    return this.lists.pop();
}
Stack.prototype.clear = function(){
    this.lists = [];
    return true;
}
Stack.prototype.peek = function(){
    var topIndex = this.size() -1;
    return this.lists[topIndex];
}
Stack.prototype.size = function(){
    return this.lists.length;
}
Stack.prototype.isEmpty = function(){
    return this.lists.length === 0;
}
Stack.prototype.bottom = function(){
    return this.lists[0];
}
Stack.prototype.toString = function(){
    var result = "";
    for(var i=0;i<this.lists.length;i++){
        result = result + '' +this.lists[i];
    }
    return result;
}

ES5和ES6实现栈结构已经通过了测试可运行。上面是通过数组实现的栈结构，其实链表也可以实现栈结构。下面数据结构链表篇会使用链表实现栈的数据结构