1、栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。
2、表尾为栈顶（top），表头为栈底（bottom），不含元素的空表为空栈。
3、栈又称为后进先出（last in first out）的线性表。

栈的顺序存储结构

结构

1、用数组下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小。
2、定义一个top变量来指示栈顶元素在数组中的位置。
3、若存储栈的长度为 StackSize，则栈顶位置 top 必须小于 StackSize。
4、当栈存在一个元素时，top 等于0。因此空栈的判定条件定为 top 等于 -1。

function Stack() {
    this.dataStore = []; /* 用于储存栈元素的数组 */
    this.top = -1; /* 用于栈顶指针 */
}

操作

Stack.prototype = {
    constructor: Stack,push : function (data) { /* 入栈方法 */

    },pop : function () { /* 出栈方法 */

    },peek: function () { /* 返回顶部的栈元素 */

    },clear: function () { /* 清除栈元素 */

    },length: function () { /* 返回栈元素个数 */

    }
};

push方法实现

栈中向top位置插入元素后，top值更新，元素个数+1。

function push (data) {
    this.dataStore[++this.top] = data;
}

pop方法实现

元素出栈，top值减1，指向当前栈顶元素下标位置，删除该元素作为出栈操作。

function pop() {
    var topvalue =  this.dataStore[this.top];
    delete this.dataStore[this.top--];
    return topvalue;
}

peek方法实现

peek方法返回顶部的栈元素，即取dataStore的最后一个位置的值，也就是 dataStore 下标为 top-1 的值。

function peek() {
    return this.dataStore[this.top];
}

clear方法实现

1、clear 方法清除栈内元素，把栈的长度重置为0。
2、另外还要把dataStore数组置空，因为数组中的元素始终被dataStore引用，导致垃圾回收器无法将其回收，从而造成内存浪费。

function clear () {
    this.top = -1;

    //下面两句任选其一清除数组dataStore里的数据
    // this.dataStore = [];
    this.dataStore.length = 0;
}

length 方法实现

length 方法获取栈中的元素个数。

function length() {
    return this.top+1;
}

测试代码

var a = new Stack();
a.push(1);
a.push(2);
a.push(3);
console.log("开始的dataStore为：" + a.dataStore + " 栈的长度为：" + a.length()); 
/* 输出：开始的dataStore为：1,2,3 栈的长度为：3 */
a.pop();
console.log("出栈一个值后dataStore为：" + a.dataStore + " 栈的长度为：" + a.length()); 
/* 输出：出栈一个值后dataStore为：1,栈的长度为：2 */
a.clear();
console.log("清除栈后dataStore为：" + a.dataStore + " 栈的长度为：" + a.length()); 
/* 输出：清除栈后dataStore为： 栈的长度为：0 */

栈的链式存储结构

结构

1、由于单链表有头指针，所以最好的办法就是把栈顶放在单链表的头部。
2、由于有栈顶在头部，单链表的头结点失去了意义，所以对于链栈来说，不需要头结点。
3、对于空栈的判定条件为 top = null 。

function Stack() {
    this.top = null; /* 用于栈顶指针 */
    this.length = 0; /* 用于表示栈的长度 */
}

操作

Stack.prototype = {
    constructor: Stack,push : function (element) { /* 入栈方法 */

    },length: function () { /* 返回栈元素个数 */

    }
};

push方法实现

栈中向top栈顶插入元素后，top值更新，元素个数+1。

function push (data) {
    var node = {
            data: data,next: null
    };
    node.next = this.top;
    this.top = node;
    this.size++;
}

pop方法实现

元素出栈，size值减1，存储要删除的栈顶元素，将栈顶指针下移一位。

function pop() {
    if (this.top === null) 
        return null;

    var out = this.top;
    this.top = this.top.next;
    if (this.size > 0) 
        this.size--;

    return out.data;
},

peek方法实现

peek方法返回顶部的栈元素。

function peek() {
    return this.top === null ?
        null :
        this.top.data;
}

clear方法实现

clear 方法清除栈内元素，把栈的长度重置为0。

function clear () {
    this.top = null;
    this.size = 0;
}

length 方法实现

length 方法获取栈中的元素个数。

function length() {
    return this.size;
}

测试代码

/* 给链栈增加一个展示函数 */
function displayAll(){
    if (this.top === null) 
        return null;

    var arr = [];
    var current = this.top;
    for (var i = 0,len = this.size; i < len; i++) {
        arr[i] = current.data;
        current = current.next;
    }
    return arr;
}

var a = new Stack();
a.push(1);
a.push(2);
a.push(3);
console.log("开始的dataStore为：" + a.displayAll()+ " 栈的长度为：" + a.length()); 
/* 输出：开始的栈为：3,1 栈的长度为：3 */
a.pop();
console.log("出栈一个值后dataStore为：" + a.displayAll()+ " 栈的长度为：" + a.length()); 
/* 输出：出栈一个值后栈为：2,1 栈的长度为：2 */
a.clear();
console.log("清除栈后dataStore为：" + a.displayAll()+ " 栈的长度为：" + a.length()); 
/* 输出：清除栈后栈为： 栈的长度为：0 */

栈的应用

四则运算表达式求值

后缀（逆波兰）表示法

1、不需要括号的后缀表示，所有的符号在运算数字的后面出现。
2、规则：从左到右遍历表达式的每个数字和符号：

• 遇到是数字就进栈；
• 遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

中缀表达式转后缀表达式

1、中缀表达式：平时所用的标准四则运算表达式。
2、规则：从左到右遍历中缀表达式的每个数字和符号：

• 若是数字就输出，即成为后缀表达式的一部分；
• 若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素一次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

因此，要让计算机处理中缀表达式，最重要的就是两步：

1. 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
2. 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。