Stack 栈 简单了解

什么是 栈？

计算机科学中是一种数据结构。

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

特点

栈模型.png

• 先进先出
• 主要操作有 进栈push 出栈 pop

js简单模拟 stack 类

class Stack {
    constructor() {
            this.data = []; //栈元素
            this.topIndex = 0; //顶级栈元素下标
        }
        //进栈
    push() {
            let args = [...arguments];
            args.forEach(arg => this.data[this.topIndex++] = arg);
            return this.topIndex;
        }
        //出栈
    pop() {
            if (this.topIndex === 0) throw new Error('当前栈为空');
            let top = this.data[this.topIndex - 1];
            this.data = this.data.slice(0, -1);
            this.topIndex = this.topIndex - 1;
            return top; //出栈元素
        }
        //清栈
    clear() {
            this.topIndex = 0;
            this.data = [];
            return this.topIndex;
        }
        //获取顶级元素
    top() {
            if (this.topIndex === 0) throw new Error('当前栈为空');
            return this.data[this.topIndex - 1];
        }
        //是否为空栈
    isEmpty() {
            return this.topIndex === 0;
        }
        //栈长度
    size() {
        return this.topIndex;
    }
}
console.log('push', stack.push(1, 2, 3));//push 3
console.log('isEmpty', stack.isEmpty());//isEmpty false
console.log('size', stack.size());//size 3
console.log('pop', stack.pop());//pop 3
console.log('top', stack.top());//top 2
console.log('clear', stack.clear());//clear 0
console.log('isEmpty', stack.isEmpty());//isEmpty true

栈的两个小应用

• 十进制 转 二进制

const convert = (num, base) => {
    let result = '',
        stack = new Stack();
    while (num > 0) {
        stack.push(num % base);
        num = Math.floor(num / base);
    }
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    return +result;
}
console.log('convert', convert(11, 2));//convert 1011

• 翻转字符串

const revers = (str) => {
    let stack = new Stack(),
        result = '';
    str = str.toString();
    for (let i = 0; i < str.length; i++) {
        stack.push(str.charAt(i))
    }
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    return result;
}

console.log('revers', revers(131241));//revers 142131