数据结构（栈实现篇）

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

栈结构示意图

栈结构使用

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

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

实现栈结构的功能

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

进栈与出栈流程

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实现栈结构已经通过了测试可运行。上面是通过数组实现的栈结构，其实链表也可以实现栈结构。下面数据结构链表篇会使用链表实现栈的数据结构