数组模拟 JavaScript数据结构之栈（Stack）存储原理

た入场券 2023-02-28 01:50 42阅读 0赞

##### 什么是栈 ？ #####

一种后进先出（LIFO）的数据结构

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDQzOTIz_size_16_color_FFFFFF_t_70]

如图所示这就好比一个单向开口的网球筒，先放入网球筒的在筒底需要最后才能拿出来。后放入球筒的先拿出来。栈的数据存储就是以这种方式实现

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDQzOTIz_size_16_color_FFFFFF_t_70 1]

> `push()` 入栈  
> `pop()` 出栈  
> `peek()` 查看栈顶

这几种栈的底层操作方法，我们可以依照数组的使用模拟出来，这样就很容易理解程序概念中的栈操作

##### 数组模拟栈 #####

因为JavaScript比较高级，自带了 `push()` 和 `pop()`两个方法，这样理解起来变得更加容易

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDQzOTIz_size_16_color_FFFFFF_t_70_pic_center]

数组的`push()` 将数据添加到栈顶， `pop()` 则取出最后一项数据。模拟出栈的存入和取出操作

以下的类便是使用数组模拟出完整的栈操作

/** * 模拟栈创建的类 * */
    var Stack = function () { 
    
    	// 定义私有变量 外部不能操作访问，保护栈规则 
        var items = []  
        // this.items 外部可以通过实例化操作到
    
        // 栈的存入操作
        this.push = function (el) { 
            items.push(el)
        }
    
        // 栈的取出操作
        this.pop = function (el) { 
            return items.pop()
        }
        
        // 获取元素
        this.getItems = function () { 
            return items
        }
        
        // 检查栈顶
        this.peek = function () { 
            return items[items.length - 1]
        }
    
        // 检查是否为空栈
        this.isEmpty = function () { 
            return items.length === 0
        }
    
        // 清空栈
        this.clear = function () { 
            items = []
        }
    
        // 栈元素个数
        this.size = function () { 
            return items.length
        }
    
    }

##### 使用栈操作十进制转二进制 #####

余数法：采用连续除2纪录余数的方法，直到除数小于2。将最终结果和余数连接得出二进制数据

> 10/2 = 5 余 `0`  
> 5/2 = 2 余 `1`  
> 2/2 = `1`余 `0`  
> 红字结果 ：`1010`

/** * 利用封装的Stack() * 实现十进制转二进制 * 利用余数法进行转换 */
     var s = new Stack()
     var decimalToBinary = function (number) { 
         while (number > 0) { 
             s.push(number % 2)
             number = Math.floor(number / 2)
         }
         return getBinary()
     }
    
     var getBinary = function () { 
         var binStr = ''
         while (!s.isEmpty()){ 
             binStr += s.pop()
         }
         return binStr
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDQzOTIz_size_16_color_FFFFFF_t_70]: /images/20230209/943e0d8fb4cc4d88a2851581219c0c84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDQzOTIz_size_16_color_FFFFFF_t_70 1]: /images/20230209/913cdc1632c24e1e84444cbca63624ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDQzOTIz_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/6fbae7bcb7f0447094b2225a0f54562f.png