【数据结构】栈Stack

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, 栈的长度为: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) { /* 入栈方法 */

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

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

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

    },
    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,2,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. 将后缀表达式进行运算得出结果(栈用来进出运算的数字)。
相关文章
相关标签/搜索