栈

什么是栈

栈，只有一个出口，是一种后进先出的线性数据结构，也就是传说中的 LIFO(last in first out) 。

栈，只有一个出口，从哪里进，就从哪里出，这个出口也叫 栈顶 ，对应的底部就叫 栈底 。

如图示：

栈的实现

由于数组的特性，用数组来实现栈是最简单的了。大致的功能如下：

• push: 用来将元素推入栈顶
• pop: 删除栈顶的元素，并返回
• peek: 返回栈顶元素
• isEmpty: 判断栈是否是空栈
• size: 返回栈的长度
• clear: 清空栈

代码实现：

class Stack {
    constructor() {
        this.items = [];
    }
    push(element) {
        return this.items.push(element);
    }
    pop() {
        return this.items.pop();
    }
    peek() {
        return this.items[this.items.length - 1];
    }
    isEmpty() {
        return this.items.length === 0;
    }
    size() {
        return this.items.length;
    }
    clear() {
        this.items = [];
    }
    toString() {
        return this.items.toString();
    }
}

栈的应用

1. 进制转换

10 进制转换为任意进制。

转换原理：

如上用十进制转换为二进制示意，不断的对余数取整， push 进栈，最后从栈顶一一取出即可。

function baseConverter(number, base) {
    const stack = new Stack();
    const digits = '0123456789abcdefghijklmnopqrstuvwxyz';
    let decNumber = number;
    let result = '';
    if (base < 2 || base > 32) {
        return '';
    }
    while (decNumber > 0) {
        stack.push(Math.floor(decNumber % base));
        decNumber = Math.floor(decNumber / base);
    }
    while (!stack.isEmpty()) {
        result += digits[stack.pop()];
    }
    return result;
}

2. 撤销回退功能

const go = new Stack();
const back = new Stack();
go.push(1);
go.push(2);
go.push(3);
let ctrlZ = function () {
    back.push(go.pop());
}
let unCtrlZ = function () {
    go.push(back.pop());
}
console.log('go', go.toString(), 'back', back.toString())
ctrlZ();
console.log('go', go.toString(), 'back', back.toString())
ctrlZ();
console.log('go', go.toString(), 'back', back.toString())
unCtrlZ();
console.log('go', go.toString(), 'back', back.toString())