JS数据结构与算法之栈结构

太过爱你忘了你带给我的痛 2024-03-25 10:52 156阅读 0赞

### 认识栈结构 ###

栈是比较常见的受限的线性结构，栈结构先进后出last in first out

![b5059fbc41a580798423a82dd9805faf.png][]

#### 程序中对栈的使用： ####

*  函数调用栈

A函数中调用B，B调用C，C调用D；在A执行的过程中会将A压入栈，随后B执行时B也被压入栈，函数C和D执行时也会被压入栈。所以当前栈的顺序为：A->B->C->D（栈顶）；函数D执行完之后，会弹出栈被释放，弹出栈的顺序为D->C->B->A

*  递归

为什么没有停止条件的递归会造成栈溢出？比如函数A为递归函数，不断地调用自己（因为函数还没有执行完，不会把函数弹出栈），不停地把相同的函数A压入栈，最后造成**栈溢出**

### js栈结构的封装 ###

// 封装栈类
        function Stack(){
          // 栈中的属性
          this.items =[]
    
          // 栈的相关操作
          // 1.push():将元素压入栈
          //方式一(不推荐)：给对象添加方法，其他对象不能复用
          // this.push = () => {
          // }
          
          //方式二(推荐)：给Stack类添加方法，能够多对象复用
          Stack.prototype.push = function(element) {
          // 利用数组item的push方法实现Stack类的pop方法
            this.items.push(element)
          }
    
          // 2.pop():从栈中取出元素
          Stack.prototype.pop = () => {
          // 利用数组item的pop方法实现Stack类的pop方法
            return this.items.pop()
          }
    
          // 3.peek():查看一下栈顶元素
          Stack.prototype.peek = () => {
            return this.items[this.items.length - 1]
          }
    
          // 4.isEmpty():判断栈是否为空
          Stack.prototype.isEmpty = () => {
          // 两个小时的教训啊不是this.length(不是Stack对象的length，Stack类没有length属性啊)，而是            Stack类中定义的数组items才有length属性呀
            return this.items.length == 0 
          }
    
          // 5.size():获取栈中元素的个数
          Stack.prototype.size = () => {
            return this.items.length
          }
    
          // 6.toString():以字符串形式输出栈内数据
          Stack.prototype.toString = () => {
            //希望输出的形式：20 10 12 8 7
            let resultString = ''
            for (let i of this.items){
              resultString += i + ' '
            }
            return resultString
          }
        }

测试代码

// 栈的使用
        let  s = new Stack()
        s.push(20)
        s.push(10)
        s.push(100)
        s.push(77)
        console.log(s)                                                    //65
    
        console.log(s.pop());                                            //68
        console.log(s.pop());                                            //69
        
        console.log(s.peek());                                            //71
        console.log(s.isEmpty());                                        //72
       
        console.log(s.size());                                            //74
        console.log(s.toString());                                        //75

### js实现判断栈的压入、弹出序列 ###

一道题目：输入两个整数序列，第一个序列表示栈的压入顺序，判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如：1，2，3，4，5是某个栈的压入顺序，序列4，5，3，2，1是该栈对应的一个弹出序列，但4，3，5，1，2就不可能是该压栈序列的弹出序列。

用数组来模拟栈的操作。主要思路：

在判断第一个弹出的数字时，如果刚好是入栈的栈顶元素，那么直接弹出。继续从第1步开始判断下一个弹出的数字。

如果不是，则将入栈序列中不为弹出数字的数字压入到辅助栈中直到找到这个弹出元素（若没找到，则直接可以退出，说明弹出序列不可能）。

如果弹出序列存在的话，那么接下来的弹出元素只有两个可能：①出现在入栈的栈顶；②存在于辅助栈中。然后循环判断这两种状况直到弹出栈变为空即可。

如果以上两种情况都没匹配到，那么该弹出序列就不可能了。

/**
     * 这里使用JS实现，用数组来模拟栈的操作
     * @param {栈输入的顺序（数组表示）} pushOrder 
     * @param {栈输出的顺序（数组表示）} popOrder 
     */
    
    
    function isPopPossible(pushOrder, popOrder) {
        var isPossible = false
        /** 1. 确认输入的合法性 */
        if (pushOrder != null && popOrder != null && Array.isArray(pushOrder) && Array.isArray(popOrder)) {
            /** 2. 都为空直接返回true（这里认为两个栈都是空的话，就是true） */
            if (pushOrder.length === 0 && popOrder.length === 0) {
                return true
            }
            /** 3. 保证两个输入的序列长度是相等的  */
            if (pushOrder.length === popOrder.length) {
                /** JS中数组传入的是引用，为了保证不改变原数组，这里创建一份他们的副本 */
                var pushOrder_copy = [...pushOrder]
                var popOrder_copy = [...popOrder]
                /** 这个数组作为辅助的栈 */
                var helpStack = []
                /** 获取第一个弹出的元素（此时弹出序列减少了一个元素） */
                var now = popOrder_copy.shift()
                /** 将栈顶不为第一个弹出的元素的元素压入辅助栈 */
                while (pushOrder_copy.length > 0 && pushOrder_copy[pushOrder_copy.length - 1] !== now) {
                    helpStack.unshift(pushOrder_copy.pop())
                }
                /** 若所有元素都弹出了还没找到和第一个弹出元素相等的元素，则直接返回false */
                if (pushOrder_copy.length === 0) {
                    return false
                }
                /** 说明找到了，则将匹配到的这个元素弹出 */
                pushOrder_copy.pop()
                /** 4. 遍历剩下的弹出栈元素（这里入栈序列可能不为空，辅助栈可能不为空，弹出栈可能不为空） */
                while (popOrder_copy.length > 0) {
                    /** 获取下一个弹出元素 */
                    now = popOrder_copy.shift()
                    /** 如果入栈序列的栈顶为该弹出元素，则将其从入栈中弹出 */
                    if (pushOrder_copy.length > 0 && pushOrder_copy[pushOrder_copy.length - 1] === now) {
                        pushOrder_copy.pop()
                    } else {
                        /** 遍历辅助栈，看弹出的元素是否在辅助栈中 */
                        while (helpStack.length > 0) {
                            /** 如果辅助栈栈顶的元素不为弹出的元素，则将其压入到入栈中 */
                            if (helpStack[0] !== now) {
                                pushOrder_copy.push(helpStack.shift())
                            } else {
                                /** 辅助栈中找到了该弹出元素，则将该元素弹出，跳出循环，进行下一轮弹出元素的判断 */
                                helpStack.shift()
                                break
                            }
                        }
                    }
                }
                /** 最终入栈和出栈都为空，说明都匹配到了，则是可能的弹出序列 */
                if(popOrder_copy.length === 0 && pushOrder_copy.length === 0) {
                    isPossible = true
                }
            }
        }
        return isPossible
    }
    
    
    /** =====测试用例===== */
    /** 1.两个都为空 */
    console.log(isPopPossible([], [])) //true，
    /** 2.其中一个不存在 */
    console.log(isPopPossible(null, [])) //false
    /** 3.元素个数不匹配 */
    console.log(isPopPossible([1, 2, 3, 4], [1, 2, 3])) //false
    /** 4.元素不匹配 */
    console.log(isPopPossible([1, 2, 3, 4], [1, 2, 3, 5])) //false，
    /** 5.比较常规的测试 */
    console.log(isPopPossible([1, 2, 3, 4, 5], [4, 5, 3, 2, 1])) //true
    /** 5.不匹配 */
    console.log(isPopPossible([1, 2, 3, 4, 5], [4, 5, 3, 1, 2])) //false
    /** 6.入栈的序列为空，都在辅助栈中 */
    console.log(isPopPossible([1, 2, 3, 4, 5], [5, 4, 3, 2, 1])) //true，
    /** 7. 输入栈和辅助栈来回交替 */
    console.log(isPopPossible([1, 3, 2, 0], [1, 2, 0, 3])) //true

### 利用栈结构实现十进制转二进制 ###

//简单应用：
        //封装函数：将十进制转成二进制(十转二的运算最后倒叙取余的特点符合栈'先进后出')
        let dec2bin = decNumber => {
          //1.定义一个栈对象，保存余数
          var  stack = new Stack()
    
          // 2.循环操作
          while(decNumber > 0){
            // 2.1.获取余数并放入栈中
            stack.push(decNumber % 2)
            // 2.2.获取整除后的结果作为下一次运算的数字(floor:向下取整)
            decNumber = Math.floor(decNumber / 2)
          }
    
          // 3.从栈中取出0和1
          let  binaryString = '';
          let a = stack.items.length
         while(stack.items.length != 0){
            binaryString += stack.pop();
          }
          return binaryString;
        }
        
        //测试代码
        console.log(dec2bin(10));                                        //103
        console.log(dec2bin(100));                                        //104
        console.log(dec2bin(1000));                                        //105

[b5059fbc41a580798423a82dd9805faf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/cb4bfab444be4424ad31c4ba09f6bc97.png