# JavaScript数据结构---栈

栈是一种遵从后进先出原则的集合。新添加的或待删除的元素都保存在栈的同一端,称作栈顶,另一端叫做栈底。通常新的元素在栈顶,旧元素在栈底。

# 创建

Stack 类最简单的是使用一个数组来存储元素。但是使用数组的话,大部分的方法时间复杂度在 O(n) 。最坏的情况需要迭代数组的所有位置,如果数组元素越多,所需要的时间越长。这里我们使用 JavaScript 对象来存储所有栈元素。

class Stack {
  constructor() {
    // 记录栈的大小
    this.count = 0;
    // 保存栈中的元素
    this.items = {};
  }
}

下来要为栈声明一些方法:

  • push(elements(s)): 添加一个或几个元素到栈顶
  • pop(): 移除栈顶的元素,同时返回被移除的元素
  • peek(): 返回栈顶元素
  • isEmpty(): 若栈中没有元素返回 true 否则 false
  • clear(): 移除栈中所有的元素
  • size(): 返回栈里的元素个数
  • toString()

# 内置方法

  • push(elements(s)): 添加一个或几个元素到栈顶
push(element) {
  // 添加元素
  this.items[this.count] = element;
  // 增加个数
  this.count++;
}
  • pop(): 移除栈顶的元素,同时返回被移除的元素
pop() {
  // 是否为空
  if(this.isEmpty()) {
    return undefined;
  }
  // 个数减一
  this.count--;
  // 删除并返回元素
  const result = this.items[this.count];
  delete this.items[this.count];
  return result;
}
  • peek(): 返回栈顶元素
peek() {
  // 是否为空
  if(this.isEmpty()) {
    return undefined;
  }
  return this.items[this.count - 1];
}
  • isEmpty(): 是否为空
isEmpty() {
  return this.count === 0;
}
  • clear(): 移除栈中所有的元素
clear() {
  this.items = {};
  this.count = 0;
}
  • size(): 返回数组大小
size() {
  return this.count;
}
  • toString()
toString() {
  // 是否为空
  if(this.isEmpty()){
    return '';
  }
  // 拼接
  let objString = `${this.items[0]}`;
  for(let i = 1; i<this.count;i++) {
    objString = `${objString},${this.items[i]}`;
  }
  return objString;
}

# 用栈解决问题

# 有效的括号

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 注意空字符串可被认为是有效字符串

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

思路:

  • 初始化栈 S。
  • 一次处理表达式的每个括号。
  • 如果遇到开括号,我们只需将其推到栈上即可。这意味着我们将稍后处理它,让我们简单地转到前面的 子表达式。
  • 如果我们遇到一个闭括号,那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号,那么我们将它从栈中弹出并继续处理。否则,这意味着表达式无效。
  • 如果到最后我们剩下的栈中仍然有元素,那么这意味着表达式无效。
/**
 * @param {string} 需要检查的字符串
 * @return {boolean} 返回结果
 */
var isValid = function (s) {
  const length = s.length
  // 长度为空
  if (!s) return true
  // 奇数返回false
  if (length % 2) return false
  // 创建 map
  const obj = {
    '(': 1, ')': -1, '{': 2, '}': -2, '[': 3, ']': -3
  }
  const temp = []
  let i = 0
  for (; i < length; i++) {
    // 判断当前元素与栈底元素的和为0 出栈
    let value = obj[s[i]]
    const last = temp[temp.length - 1] || 0
    value + last === 0 ? temp.pop() : temp.push(value)
  }
  // 若栈中无元素则为 有效过好
  return temp.length === 0
};

# 完整代码

class Stack {
  constructor() {
    this.count = 0;
    this.items = {};
  }
  push(element) {
    this.items[this.count] = element;
    this.count++;
  }
  size() {
    return this.count;
  }
  isEmpty() {
    return this.count === 0;
  }
  pop() {
    if(this.isEmpty()) {
      return undefined;
    }
    this.count--;
    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];
  }
  clear() {
    this.items = {};
    this.count = 0;
  }
  toString() {
    if(this.isEmpty()){
      return '';
    }
    let objString = `${this.items[0]}`;
    for(let i = 1; i<this.count;i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}
Last Updated: 3/27/2020, 3:05:19 PM