认识栈结构：

  • 栈也是一种非常常见的数据结构，并且在程序中的应用非常广泛。

  • 数组：

    我们知道数组是一种线性结构，并且可以在数组的任意位置插入和删除数据
    但有时候，我们为了实现某些功能，必须对这种任意性加以限制
    而栈和队列就是比较常见的受限的线性结构。

  • 栈结构示意图：

image.png 后进先出

  • 栈，它是一种受限的线性表，后进先出。

其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
LIFO 表示就是后进入的元素，第一个弹出栈空间。
向一个栈插入新元素又称作进栈、入栈或压栈，他是把新元素放到栈顶元素的上面，使之成为新的栈顶
从一个栈删除元素又称为出栈或退栈，他是把栈顶元素删掉，使其相邻的元素成为新的栈顶元素。

栈的应用

  • 调用栈

    我们知道函数之间和相互调用：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执行完，弹出栈。C/B/A依次弹出栈。

    栈结构的面试题

    image.png

题目答案: C

  • A答案: 65进栈, 5出栈, 4进栈出栈, 3进栈出栈, 6出栈, 21进栈,1出栈, 2出栈
  • B答案: 654进栈, 4出栈, 5出栈, 3进栈出栈, 2进栈出栈, 1进栈出栈, 6出栈
  • D答案: 65432进栈, 2出栈, 3出栈, 4出栈, 1进栈出栈, 5出栈, 6出栈

栈结构的实现

栈的创建

  • 我们先来创建一个栈的类, 用于封装栈相关的操作

    1. // 栈类
    2. function Stack() {
    3.   // 栈中的属性
    4.   var items = []
    6.   // 栈相关的方法
    7. }

  • 代码解析:

    • 我们创建了一个Stack构造函数, 用户创建栈的类.
    • 在构造函数中, 定义了一个变量, 这个变量可以用于保存当前栈对象中所有的元素.
    • 这个变量是一个数组类型. 我们之后无论是压栈操作还是出栈操作, 都是从数组中添加和删除元素.
    • 栈有一些相关的操作方法, 通常无论是什么语言, 操作都是比较类似的.

      栈的操作

  • 栈常见有哪些操作呢?

    • push(element): 添加一个新元素到栈顶位置.
    • pop()：移除栈顶的元素，同时返回被移除的元素。
    • peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
    • isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
    • clear()：移除栈里的所有元素。
    • size()：返回栈里的元素个数。这个方法和数组的length属性很类似。
  • 现在我们来实现这些方法:

  • push方法

    • 注意: 我们的实现是将最新的元素放在了数组的末尾, 那么数组末尾的元素就是我们的栈顶元素
      1. // 压栈操作
      2. this.push = function (element) {
      3. items.push(element)
      4. }

  • pop方法

    • 注意: 出栈操作应该是将栈顶的元素删除, 并且返回.
    • 因此, 我们这里直接从数组中删除最后一个元素, 并且将该元素返回就可以了
      1. // 出栈操作
      2. this.pop = function (element) {
      3. return items.pop()
      4. }

  • peek方法

    • peek方法是一个比较常见的方法, 主要目的是看一眼栈顶的元素.
    • 注意: 和pop不同, peek仅仅的瞥一眼栈顶的元素, 并不需要将这个元素从栈顶弹出.
      1. // peek操作
      2. this.peek = function () {
      3. return items[items.length - 1]
      4. }

  • isEmpty方法

    • isEmpty方法用户判断栈中是否有元素.
    • 实现起来非常简单, 直接判断数组中的元素个数是为0, 为0返回true, 否则返回false
      1. // 判断栈中的元素是否为空
      2. this.isEmpty = function () {
      3. return items.length == 0
      4. }

  • size方法

    • size方法是获取栈中元素的个数.

    • 因为我们使用的是数组来作为栈的底层实现的, 所以直接获取数组的长度即可.(也可以使用链表作为栈的顶层实现)

      1. // 获取栈中元素的个数
      2. this.size = function () {
      3. return items.length
      4. }

      完整代码

      实现栈结构有两种比较常见的方式
      基于数组实现
      基于链表实现
      function Stack() {
      //栈中的属性
      _this.items =[]
      //栈的相关操作
      //1.将元素压入栈
      Stack_.prototype.push = function (element) {
      this.items.push(element)

      }
      //2.从栈中取出元素
      Stack      .prototype.pop = function () {
      return this.items.pop()
      }
      //3查看一下栈顶元素
      Stack      .prototype.peek = function () {
      return this.items[this.items.length-1]
      }
      //判断栈是否为空
      Stack      .prototype.isEmpty = function () {
      return this.items.length === 0
      }
      //获取栈中元素的个数
      Stack      .prototype.size = function () {
      return this.items.length

      }
      //toString方法
      // Stack.prototype.toString() = function () {
      // //20 23 45 67
      // var resultString =””
      // for (var i =0;i // resultString += this.items[i] + ‘’
      // }
      // return resultString
      // }
      }

      栈的使用

  • 我们来使用封装的栈, 模拟刚才的面试题

    • 我们做了一下A, 其他大家可以自己练习一下.
    • C是无法使用栈来模拟的, 因为不正确的是C

s.push(6)
s.push(5)
s.push(4)
s.pop()
s.pop()
s.push(3)
s.pop()
s.push(2)
s.pop()
s.push(1)
s.pop()
s.pop()
//栈的使用
_let s = new _Stack()
s.push((20))
s.push(34)
s.push(56)
alert(s.items)
s.pop()
alert(s.items)
alert( s.isEmpty())

栈结构的应用

十进制转二进制

  • 为什么需要十进制转二进制?
    • 现实生活中，我们主要使用十进制。
    • 但在计算科学中，二进制非常重要，因为计算机里的所有内容都是用二进制数字表示的（0和1）。
    • 没有十进制和二进制相互转化的能力，与计算机交流就很困难。
  • 如何实现十进制转二进制?
    • 要把十进制转化成二进制，我们可以将该十进制数字和2整除（二进制是满二进一），直到结果是0为止。
    • 举个例子，把十进制的数字10转化成二进制的数字，过程大概是这样：

栈 - 图3
如果我们希望使用代码来实现这个功能呢?
function dec2bin(a) {
//定义变量
_function Stack() {
// 栈中的属性
_var items = []

  1.     _// 栈相关的方法<br />        // 压栈操作<br />        _this.push = function (element) {<br />            items.push(element)<br />        }
  3.     _// 出栈操作<br />        _this.pop = function () {<br />            return items.pop()<br />        }<br />        this.isEmpty = function () {<br />            return items.length === 0<br />        }<br />    }<br />    var stack = new Stack()<br />    var reminder;<br />    _//<br />_    _while (a > 0){<br />     reminder = a % 2<br />     a = Math.floor(a / 2)<br />     stack.push(reminder)<br />    }<br />    var binayriStrng = ''<br />    while (!stack.isEmpty()) {<br />        binayriStrng += stack.pop()<br />    }<br />    return binayriStrng

}

alert(dec2bin(10))
alert(dec2bin(34))
image.png