JavaScript数据结构-栈

javascript/jquery

浏览数:628

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;
}

使用该函数计算5的阶乘

factorial(5) // 120

原文链接:https://mp.weixin.qq.com/s/F5VtpnqAxprpYbpN1rsTDg