程序的递归是使用栈实现的
操作系统中进程调度，网络管理中的打印服务是队列实现的

栈的定义

  1. 又名堆栈
  2. 受限操作，限定只能在表尾增加和删除操作，可进行操作的一端称为栈顶，不可操作的一端称为栈底
  3. 增加元素称为进栈，入栈，或者压栈，
  4. 删除元素称为出栈或者退栈，意思是把元素从栈底移除，使其相邻元素称为栈底元素

队列的定义

  1. 受限操作： 限定只能在表的前端进行删除操作，只能在表的后端进行插入操作
  2. 进行插入操作的一端称为队尾，进行删除的一端操作称为队头
  3. 增加元素的操作称为入队列，即把元素添加到队尾的位置
  4. 删除元素的操作称为出队列，即把元素从队头移除

特点
栈是先入后出， 队列是先入先出

实现栈

  1. class Stack{
  2.     constructor() {
  3.       this.data = []
  4.   }
  5.   push(el) {
  6.       this.data.push(el)
  7.     return this.data.length
  8.   }
  9.   pop() {
  10.       if (this.data.length) {
  11.         let el = this.data.pop()
  12.       return  el;
  13.     }
  14.     return false;
  15.   }
  17.   searchStackTop() {
  18.       return this.data[this.data.length - 1]
  19.   }
  21.   isEmpty() {
  22.       return this.data.length === 0
  23.   }
  25.   clear() {
  26.       this.data = []
  27.   }
  28. }

实现队列

  1. class Queue {
  2.     constructor() {
  3.       this.data = []
  4.   }
  6.   enqueue(el) {
  7.       this.data.push(el)
  8.     return this.data.length;
  9.   }
  11.   dequeue(el) {
  12.       if (this.data.length) {
  13.         let el = this.data.shift()
  14.       return el;
  15.     }
  16.     return false;
  17.   }
  19.   searchQueueHead() {
  20.       return this.data[0]
  21.   }
  23.   clear() {
  24.       this.data = []
  25.   }
  27.   isEmpty() {
  28.       return this.data.length === 0;
  29.   }
  30. }

栈溢出
一般指定义的数据所需要的内存超过的栈的大小，就会发生栈溢出

  1. function sum(a) {
  2.     sum(a)
  3. }
  4. // 执行过程，函数调用会在内存形成一个调用记录，又称调用帧，保存调用位置和内部变量等信息
  5. // 1. 执行sum函数
  6. // 2. 无限循环调用sum函数
  7. // 3. 直到调用记录超过了执行栈的最大存储范围，然后系统抛出错误，终止程序

栈溢出的解决方法 - 尾递归优化
函数在最后一步调用其他函数，称为尾调用

  1. // 情况1, 不属于尾调用。 在调用函数之后还有其他操作
  2. function s() {
  3.     let x = y()
  4.   console.log(x)
  5. }
  7. // 情况2 属于尾调用
  8. function s(result) {
  9.     if (result) {
  10.       return y()
  11.   }
  12.   return y()
  13. }

尾调用不一定出现在函数最后，只需要最后一步执行的是函数即可

尾递归
函数在最后一步调用自身，称为尾递归

  1. function s() {
  2.     return s()
  3. }
  4. // 执行过程，在执行第二行代码的时候会将第一行代码的函数释放掉
  5. // 结论， 对于尾递归，只会存在一个调用记录，所以栈不会溢出

队列溢出
队列溢出分为真溢出和假溢出

  1. 真溢出， 指的是由于存储空间不够而产生溢出，扩容即可解决
  2. 假溢出，队列中尚余有足够的空间，但元素不能入队，一般是由队列的存储结构或者操作方式选择不当所致，解决方式删除元素后将所有元素向前移动一位，或者使用循环队列

使用两个栈实现队列

  1. /**
  2.     1. 创建两个栈
  3.   2. stack1 中添加元素，模拟入队操作
  4.   3. stack1 的元素反向遍历出栈，并入stack2,
  5.   4. 出队列，从stack2出栈即可
  6. */
  8. let stack1 = []
  9. let stack2 = []
  11. function enqueue(el) {
  12.     stack1.push(el)
  13. }
  15. function dequeue() {
  16.   // 若stack2不为空，表示stack2中还有元素，直接做出栈操作
  17.     if (stack2.length) {
  18.       return stack2.pop()
  19.   } else {
  20.       if (stack1.length) {
  21.       // stack2为空，查看stack1 若stack1不为空，则将stack1逆序入栈到stack2
  22.       //  stack1 -- 1,2,3,4,5
  23.       //  stack2 -- 5,4,3,2,1
  24.         for (var i = 0; i < stack1.length; i++) {
  25.           stack2.push(stack1.pop())
  26.       }
  27.       // 逆序完成，出栈栈顶元素
  28.       return stack2.pop()
  29.     } else {
  30.         return null
  31.     }
  32.   }
  33. }

小结

  1. 栈和队列的基本概念
  2. 栈溢出的出现和解决方法 - 尾递归
  3. 队列的真溢出和假溢出

练习题


去除最外层的括号**

  1. 使用size模拟一个栈操作，入栈size++, 出栈size—
  2. 如果size的值为0， 表示当前括号为最外层括号，最外层括号不进入结果中
  3. 遍历结束后，返回result即可 ```javascript // 原有字符串为 let originStr = “(()(())(()()))((()))”; // 删除最外层的之后成为如下字符串 let resultStr = “()(())(()())(())”

function countStr(S) { let size = 0 let result = ‘’

for (let i = 0; i < S.length; i++) { if (S[i] === ‘(‘) { if (size !== 0) { result += S[i] } size++ //左括号，入栈size++ } else { // 右括号，出栈 size— size— if (size !== 0) { result += S[i] } } } return result; } countStr(originStr) ```