一：认识栈结构

栈（stack）是一种非常常见的数据结构，是一种受限制的线性结构。
栈结构示意图：
image.png

二、栈的特点

是一种受限制的线性结构，后进先出（LIFO）

  • 其限制是仅允许在表的一端信息插入和删除运算，这一端被称为栈顶，相对的，另一端称为栈底。
  • LIFO(last in first out)表示就是后进入的元素，第一个弹出栈空间，类似自助餐托盘（最后放上去的托盘往往最先被拿走使用）。
  • 向一个栈中插入新元素称为进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。

  • 从栈中删除元素称为出栈或退栈，它是把栈顶元素删除，使其相邻的元素成为新的栈顶元素

    三、生活中类似于栈结构的实例

  • 自助餐托盘，最后放上去的，最先被客人拿走

  • 过去的信箱，最先收到的邮件(信件)都是在最小面
  • 程序中的调用栈
  • 十进制转二进制也是栈结构的使用

  • 注意：栈结构不能改变次序或者优先级，如果想要改变次序和优先级，就要使用队列的优先级队列结构

    四、栈在程序中的应用

  • 函数调用栈

  • 函数之间是相互调用，A调用B，B中又调用C，C中又调用D；
  • 这样在执行过程中，就会先将A压入栈中，A没有执行完，所以不会弹出栈；
  • 在A执行的过程中调用了B，会将B压入栈中，这个时候，B在栈顶，A在栈底；
  • 如果这个时候B执行完，那么B会弹出栈，如果没有执行完，就不会弹出，因为B中调用了C；
  • 所以C会被压入栈，并且是在栈顶，而C调用了D，D就会压入栈顶
  • 所以当前栈结构：A -> B -> C -> D（栈顶）
  • 当D执行完，D先弹出栈，剩下的依次出栈C/B/A

  • 所以我们就有了函数调用栈的称呼，就是来自于他们的内部实现机制

    示意图

    image.png

    注意

  • JavaScript中的普通(基本类型)变量一般都是存在栈内存中，如果是特殊变量（对象，数组…）变量存在栈内存中，指针指向堆内存，这也就是造成基本类型和引用类型拷贝问题的原因。

  • 在栈中取数据，不能随便取，只能从栈顶到栈底进行取
  • 在javascrips的引擎中对变量的存储主要有两种方式：栈内存和堆内存

    五、栈结构面试题

    有六个元素654321的顺序进栈，问下面哪一个不是合法的出栈序列（C）
    A 543612
    B 453216
    C 346521
    D 234156

    六、栈的封装

    ```javascript // 实现栈结构 1、基于数据实现 2、基于链表实现 Method和function的区别： method：和某一个对象的实例有联系 function：普通的函数

// 我们将使用数组来实现栈的封装，也可以使用链表实现 function Stack() { // 栈的属性 this.items = [] }

  1. <a name="PBHRr"></a>
  2. # 七、栈常见方法
  4. - push(element)：添加一个新元素到栈顶位置
  5. - pop()：移除栈顶元素，同时返回移除的元素
  6. - peek()：返回栈顶元素，不对栈做任何操作
  7. - isEmpty()：判断栈是否为空
  8. - size()：返回栈里的元素个数
  9. - toString()：将栈结构的内容以字符形式返回
  10. <a name="vDNs7"></a>
  11. # 八、栈常见方法的封装
  12. ```javascript
  13. function Stack() {
  14.     // 栈的属性
  15.     this.items = []
  16.     // 1、将元素压入栈
  17.     Stack.prototype.push = function(element) {
  18.         this.items.push(element)
  19.     }
  20.     // 2、从栈中取出元素
  21.     Stack.prototype.pop = function() {
  22.         return this.items.pop()
  23.     }
  24.     // 3、查看栈顶元素
  25.     Stack.prototype.peek = function() {
  26.         return this.items[this.items.length - 1]
  27.     }
  28.     // 4、判断栈是否为空
  29.     Stack.prototype.isEmpty = function() {
  30.         return this.items.length === 0
  31.     }
  32.     // 5、获取栈中元素的个数
  33.     Stack.prototype.size = function() {
  34.         return this.items.length
  35.     }
  36.     // 6、toString
  37.     Stack.prototype.toString = function() {
  38.         var str = ''
  39.         for(var i = 0; i < this.items.length; i ++) {
  40.             str += this.items[i] + ' '
  41.         }
  42.         return str
  43.     }
  44. }
  45. // 栈的使用
  46. var s = new Stack()
  47. s.push('11')
  48. s.push('22')
  49. s.push('33')
  50. s.pop()
  51. console.log(s.items)
  52. console.log(s.peek())
  53. console.log(s.isEmpty())
  54. console.log(s.size())
  55. console.log(s.toString())

九、栈十进制转二进制的实现

  1. // 十进制转二进制：不断除以2取余，直到余数为0
  2. // 封装十进制转二进制
  3. function dec2bin(decNumber) {
  4.     // 1、new一个栈
  5.     var stack = new Stack()
  6.     // 2、循环操作
  7.     while(decNumber > 0) {
  8.         // 获取余数，并放入栈中
  9.         stack.push(decNumber % 2)
  10.         // 获取整除后的结果，作为下一次运行的数字
  11.         // 向下取整
  12.         decNumber = Math.floor(decNumber / 2)
  13.         console.log(stack.items, '=====')
  14.     }
  15.     // 现在栈中有压如的数据
  16.     // 从栈中取出0 1
  17.     var sttr = ''
  18.     while(!stack.isEmpty()) {
  19.         sttr += stack.pop()
  20.     }
  21.     return sttr
  22. }
  23. console.log(dec2bin(100))

十、附加思考：栈溢出了怎么办？？？

导致栈溢出的原因：

  • 函数调用层次过深，每调用一次，函数的参数、局部变量等信息就会压一次栈
  • 局部静态变量体积过大

解决：

  • 增加栈内存数目
  • 使用堆内存
  • 避免递归无限调用