1.什么是栈？

栈是一种后进先出，或者说先进后出的结构。
JavaScript中没有栈，但是可以用数组实现栈的所有功能。

2.常用方法

• push：压入新元素
• pop：弹出顶部元素，返回弹出的值
• length：返回栈的长度

3.使用示例

//1.创建一个栈
const stack = [];    //stack为空
//2.往栈内压入元素
stack.push(1);      //stack = [1]
stack.push(2);      //stack = [1,2]
//3.弹出栈顶元素,获取返回值
const item1 = stack.pop();      //stack = [1],item1 = 2
const item2 = stack.pop();      // stack = [],item2 = 1
//4.获取栈顶元素值的
stack.push(666);         //stack = [666]
const top = stack[stack.length - 1];    //数组长度减一就是栈顶下标

4.LeetCode

接下来使用栈这个数组结构来刷LeetCode有关栈的题目，巩固提升对栈的了解。

题号20.有效的括号（简单）

题目要求:解题思路:

1. 构建栈，遍历字符串s
2. 遇到左括号就压入栈中，遇到右括号则判断栈顶左括号是否与右括号相匹配，匹配就把栈顶左括号弹出栈，继续遍历字符串s，不匹配则可以直接返回false
3. 遍历结束后，如果栈内没有剩余左括号，返回true

注意：有效字符串的长度一定为偶数，对于长度为奇数的字符串可以直接返回false
编写代码：

var isValid = function(s) { const stack = [];if(s.length % 2 == 1) {  return false;}for(let i = 0; i < s.length; i+=1) {  const c = s[i];if(c === '{' || c === '(' || c === '[') {  stack.push(c);} else {  const t = stack[stack.length - 1];if( (t === '(' && c === ')') || (t === '{' && c === '}') || (t === '[' && c === ']')  ) {  stack.pop();} else { return false ;}}}return stack.length === 0;
}

复杂度分析

1. 时间复杂度: O(n),其中n是字符串s的长度 (因为只有一个for循环)
2. 空间复杂度: O(n),栈的长度 (最坏的情况都是左括号)

题号316.去除重复字母（中等）

题目要求:

解题思路:

1. 首先要明白什么叫做字典序:
   字典序就是把两个字符串逐个字母比较，比如,abc, adc两个字符串 ,首先a === a，两个字符串第一个字母相同，比较第二个字母, b < d，所以，字符串abc < adc ，以此类推。

2. 明白了字典序之后，就可以开始做题了，题目要求所有出现的字母都得出现一次，且字典序最小，那我们可以来构造一个单调栈。

3. 每次遍历新的元素，就判断栈中是否已经有该元素了，因为我们是单调栈，如果栈中已经有这个元素了，就丢弃掉，继续遍历。比如4564，丢弃掉后面的4，而不是丢掉前面的4，才能让我们的字典序最小.

4. 关键点来了:如果栈非空，当前遍历到的元素s[i]栈中还没有，并且s[i]比栈顶stack[stack.length - 1]小。正常来说我们是要把栈顶stack[stack.length - 1]弹出后压入s[i]，不过因为我们要让所有不同字母都至少出现一次，所以要确保s[i]之后还有stack[stack.length - 1]对应的元素，如果s[i]后面该元素了，那只能委屈求全，直接压入s[i]了。

编写代码：

var removeDuplicateLetters = function(s) {const stack = [];//定义一个单调栈let i = -1;while(++i < s.length) { //遍历字符串if(stack.includes(s[i])) continue; //舍弃当前的，继续遍历，保持字典序最小//栈非空,栈顶大于s[i],s[i]后面还有栈顶元素才能弹出栈。while(stack.length && stack[stack.length -1] > s[i] && s.includes(stack[stack.length - 1], i)) {stack.pop();  }stack.push(s[i]);  //排除上方因素有就可以直接加入栈中了}return stack.join('');//将栈改造为字符串
};

复杂度分析

1. 时间复杂度: O(n)
2. 空间复杂度: O(n)

题号224.基本计算器（困难）

题目要求: