JavaScript数据结构-栈

javascript/jquery

浏览数:1,238

2017-12-11

栈

栈是一种遵循后入先出（LIFO，全称Last In First Out）的数据结构，是一种运算受限的线性表，其限制是仅允许在表的一端进行操作，这一端被称之为栈顶。

由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问，如果要访问栈底的元素，必须先移除上面的元素。

栈的实现

在JavaScript中，采用数组座位存储数据的底层数据结构。

定义Stack构造函数

function Stack(){
    this.items = [];
}

栈具有以下方法

push() 进栈
pop() 退栈
size() 栈大小
empty() 判断栈是否为空
peek() 返回栈顶元素
clear() 清空栈

push

向栈中压入新元素时，元素位于当前栈顶指针所对应的位置，压入后，栈顶指针应指向下一个位置

function push(item){
    this.items[this.top++] = item;
}

pop

pop与push方法相反，返回栈顶元素，同时top的值减1

function pop(){
    if(this.top===0) return;
    var item = this.items[this.top-1]
    this.items.length = --this.top;
    return item;
}

size

size方法返回栈内的元素个数

function size(){
    return this.top;
}

empty

检查栈是否为空，为空则返回true，否则返回false

function empty(){
    return this.top === 0;
}

peek

返回栈顶元素

function peek(){
    return this.items[this.top-1];
}

clear

清空栈内所有元素

function clear(){
    this.items = [];
    this.top = 0;
}

给栈添加方法

利用原型将以上方法添加给Stack构造函数

Stack.prototype = {
    constructor:Stack,
    push:push,
    pop:pop,
    size:size,
    empty:empty,
    peek:peek,
    clear:clear,
}

栈的实际应用

下面是一个递归函数，用来计算数字的阶乘

function factorial(n) {
    if (n === 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

使用该函数计算5的阶乘

factorial(5) // 120

如果使用栈来模拟计算5!的过程，将5到1依次压入栈，然后再将数字依次弹出连乘，即可得到计算结果

function factorial2(n){
    var s = new Stack(),
        result = 1;
    while(n>1){
        s.push(n--)
    }
    while(s.size()>0){
        result*= s.pop()
    }
    return result;
}