数据结构与算法（JS版）—— 栈

1. 概念

• 类似于数组，但在添加和删除元素时更为可控
• 是遵从后进先出原则（LIFO）的有序集合
• 新元素或待删除的元素都靠近栈顶
• 旧元素都接近栈底
• 现实生活中，类似于一摞书或者一叠盘子
• 应用：编译器内存中保存变量、方法调用等；浏览器历史记录

2. 创建一个基于数组的栈

• 需要实现的方法：

  • push(element(s))：添加一个或几个新元素到栈顶
  • pop()：移除栈顶的元素，同时返回被移除的元素
  • peek()：返回栈顶元素，不改变栈
  • isEmpty()：是否为空栈，返回布尔值
  • clear()：清空栈
  • size()：返回栈的元素个数
  • toString()：将栈元素变成字符串输出

• 代码实现 stack-array.js

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

    push(i) {
        this.items.push(i);
    }

    pop() {
        // 注意要有返回值
        return this.items.pop();
    }

    peek() {
        // 返回栈顶元素
        return this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

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

    size() {
        return this.items.length;
    }

    toString() {
        return this.items.toString();
    }
}

// 使用
const stack = new Stack();
console.log(stack.isEmpty());

stack.push(5);
stack.push(8);
stack.push(1);
console.log(stack.pop());
console.log(stack.peek());
console.log(stack.size())
console.log(stack.toString());

补充

• 在使用数组时，大部分方法的时间复杂度是O(n)。
  • O(n)的意思是，我们需要迭代整个数组直到找到要找的那个元素，最坏的情况下需要迭代数组的所有位置，其中n代表数组的长度。
• 数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。

3. 创建一个基于对象的栈

• 为了占用较少内存，且降低时间复杂度，可以基于对象创建Stack类
• 类中需要一个count属性辅助记录
• 除了toString方法，时间复杂度均为O(1)

class Stack {
    constructor() {
        this.items = {};
        this.count = 0;
    }

    push(i) {
        this.items[this.count] = i;
        this.count++;
    }

    pop() {
        // 不要忘记为空判断
        if (this.isEmpty()) {
            return undefined;
        }

        this.count--;
        // 需要先用变量保存一下this.items[this.count]值，否则返回undefined
        const result = this.items[this.count];
        delete this.items[this.count];
        return result;
    }

    peek() {
        // 不要忘记为空判断
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.count - 1];
    }

    isEmpty() {
        return this.count === 0;
    }

    clear() {
        this.items = {};
        // 计数不要忘记归0
        this.count = 0;
    }

    size() {
        return this.count;
    }

    toString() {
        if (this.isEmpty()) {
            return '';
        }
        return Object.values(this.items).toString();
    }
}

4. 保护数据结构内部元素（to do）

5. 用栈解决问题（to do）

十进制转二进制

有效括号

汉诺塔

函数调用堆栈