JavaScript数据结构-栈

栈
栈是一种遵循后入先出（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