概念

栈是一种遵从 后进先出 原则的有序集合。
添加新元素的一端称为栈顶，另一端为栈底。
操作栈的元素时，只能从栈顶操作（添加、移除、取值）

栈的实现

我们需要实现以下功能：

  • push() 入栈的方法
  • pop() 出栈的方法
  • top() 获取栈顶元素的方法
  • size() 获取栈中元素个数的方法
  • clear() 清空栈的方法

基于 JavaScript 内置对象的方法实现一个数据结构，会对性能有所损耗，所以实现时优先选择传统 JavaScript 对象进行功能的实现。

  1. class Stack {
  2.     constructor() {
  3.         // 存储栈中数据
  4.         this.data = [];
  6.         // 记录栈中数据个数(相当于数组的 length )
  7.         this.count = 0;
  8.     }
  9.     // push() 入栈方法
  10.     push(item) {
  11.         // 方法1：数组方法 push 添加
  12.         // this.data.push(item);
  14.         // 方法2：利用数组长度
  15.         // this.data[this.data.length] = item;
  17.         // 方法3：计数方式
  18.         this.data[this.count] = item;
  19.         this.count++; // 入栈后，count 自增
  20.     }
  22.     // pop() 出栈方法
  23.     pop() {
  24.         // 出栈前提是栈中存在元素
  25.         if (this.isEmpty()) {
  26.             console.log('栈为空！移除失败');
  27.             return;
  28.         }
  29.         // 移除栈顶数据
  30.         // 方法1：数组方法 pop移除
  31.         // return this.data.pop();
  33.         // 方法2：计数方式
  34.         const temp = this.data[this.count - 1];
  35.         delete this.data[this.count - 1];
  36.         this.count--;
  37.         return temp;
  39.     }
  40.     // isEmpty() 检测栈是否为空
  41.     isEmpty() {
  42.         return this.count === 0;
  43.     }
  45.     // top() 获取栈顶的元素
  46.     top() {
  47.         if (this.isEmpty()) {
  48.             console.log('栈为空！获取失败');
  49.             return;
  50.         }
  51.         return this.data[this.count - 1];
  52.     }
  54.     // size() 获取栈中元素个数
  55.     size() {
  56.         return this.count;
  57.     }
  59.     // clear() 清空栈
  60.     clear() {
  61.         this.data = [];
  62.         this.count = 0;
  63.     }
  64. }

力扣精选题

剑指 Offer 30.包含min函数的栈

LeetCode 剑指 Offer 30. 包含min函数的栈(简单)

image.png

方法一：

在存储数据的栈外，再创建一个辅助栈，用于存储栈的最小值 stack = [-2, 0, -3] minStack = [-2, -2, -3]

  1. class MinStack {
  2.     constructor() {
  3.         // stackA 用于存储数据
  4.         this.stackA = [];
  5.         this.countA = 0;
  7.         // stackB 为辅助栈 用于存储栈道最小值(数据降序排序)
  8.         this.stackB = [];
  9.         this.countB = 0;
  10.     }
  12.     push(item) {
  13.         // stackA 正常入栈
  14.         this.stackA[this.countA] = item;
  15.         this.countA++;
  17.         // stackB 如果没有数据，直接入栈
  18.         // 如果当前元素小于等于 stackB栈顶元素，入栈
  19.         if (this.countB === 0 || item <= this.min()) {
  20.             this.stackB[this.countB] = item;
  21.         } else {
  22.             // 否则 入栈元素为 当前栈中最小值
  23.             this.stackB[this.countB] = this.min();
  24.         }
  25.         this.countB++;
  26.     }
  28.     // 最小值函数 返回栈中最小值 即时辅助栈栈顶元素
  29.     min() {
  30.         return this.stackB[this.countB - 1];
  31.     }
  33.     // 获取栈顶元素
  34.     top() {
  35.         return this.stackA[this.countA - 1];
  36.     }
  38.     // 出栈
  39.     pop() {
  40.         delete this.stackA[this.countA - 1];
  41.         this.countA--;
  43.         delete this.stackB[this.countB - 1];
  44.         this.countB--;
  45.     }
  46. }
  47. // 时间复杂度：O(1)，push(), pop(), top(), min() 四个函数的时间复杂度均为常数级别。
  48. // 空间复杂度：O(N)，当共有 N 个待入栈元素时，辅助栈B 需要存储 N 个元素，使用O(N)额外空间。

方法二：

stack = [-2, 0, -3, 2 , -6] minStack = [-2, -3, -6] push()：stack 正常入栈，minStack遇到小于等于 min() 元素时入栈 pop()：先 检测辅助栈 top() === min() stack ，minStack出栈 再 stackA 正常出栈。

方法三：API大法

  1. class MinStack {
  2.     constructor() {
  3.         this.stack = [];
  4.     }
  5.     push(item) {
  6.         this.stack.push(item);
  7.     }
  8.     top() {
  9.         return this.stack[this.stack.length - 1];
  10.     }
  11.     min() {
  12.         // return Math.min(...this.stack);
  13.         return Math.min.apply(null, this.stack);
  14.     }
  15.     pop() {
  16.         this.stack.pop();
  17.     }
  18. }