JS数据结构&算法学习——栈

栈

与数组相比，栈是受限的线性结构

概念

为什么说栈是一种受限的数据结构呢？栈和数组不同，如果我们想删除或者插入数组中的某一个元素后，其没有限制，但是栈不同，由于他的结构原因，他的操作是受限制的。

通过上面的结构，我们可以知道，栈只有一个可操作端，也就是我们想删除中间的元素，我们需要先移除这个元素上面的元素才能对目标元素进行移除，对于这种特性，我们称作为后进先出(LIFO)，我们对于栈的操作有两种名词即：

0. 入栈：在栈顶添加新元素
1. 出栈：删除栈顶元素

生活应用

0. 叠放的盘子：如果我们想要拿到一摞盘子中间的一个，那么我们需要去将上面的盘子移开，进而拿到我们想要的盘子
1. 停车场的车：如果停车场内放满了车，你想要把自己的车开走，那么你就需要将其他人的车移开，给自己的车开辟一条路

程序应用（函数调栈）

A函数调用B函数，B函数调用C函数，C函数调用D函数

0. A压入进栈（未执行完）
1. A调用B将B压入栈
2. 以此类推
3. D执行完成出栈
4. C执行完成出栈
5. 以此类推

PS：递归很容易出现栈溢出

栈结构

我们通常可以使用链表和数组来实现栈结构

0. 栈封装结构结构：

function stack(){
    //栈的属性
    this.items = []
    //栈的相关操作
}
var stack = new stack()
stack.psuh()
复制代码

0. 因为JS中的类是基于对象的所以我们封装了一个栈类，在类中我们可以定义栈的属性与方法，封装好之后我们可以去通过调用来对栈实现我们上文所提及的入栈，出栈等操作。
1. 操作封装
   这里我们有两种封装方式，一种是为对象实例添加方法，一种是通过原型为类添加方法，我们一般是通过原型来封装，节省内存

//对象实例
this.push = function() {}
//类
Stack.prototype.push = function (element) {}
复制代码

0. 添加栈顶元素压栈:使用push方法来进行压栈封装

Stack.prototype.push = function (element) {
    this.items.push(element)
}
复制代码

0. 删除栈顶元素出栈:使用pop()方法来进行取元素封装

Stack.prototype.pop = function () {
    return this.items.pop()
}
复制代码

0. 查看栈顶元素:通过调用数组的length来返回栈顶元素

Stack.prototype.peek = function () {
    return this.items[this.items.length - 1]
}
复制代码

0. 判空:同样通过数组的length来进行栈的判空

Stack.prototype.isEmpty = function () {
    return this.items.length === 0
}
复制代码

0. 取栈长

Stack.prototype.size = function () {
    return this.items.length
}
复制代码

0. 栈转换字符串：通过声明字符串变量，对栈进行遍历，通过JS字符串的特性，来进行字符串拼接，最后返回其字符串

Stack.prototype.toString = function (element) {
    var reString = ''
    for(let i = 0; i < this.items.length; i++){
        reString += this.items[i] + ''
    }
    return reString
}
复制代码

使用

1. 压栈 将1，20通过push压入栈中，此时的栈为[1,20]

stack.push(1)
stack.push(20)、
console.log(stack)
复制代码

1. 取栈顶 这个时候栈顶为20，所以返回为20

console.log(stack.peek())
复制代码

1. 拼接栈元素 返回值为120，即将栈中元素拼接起来

console.log(stack.toString())
复制代码

十进制—>二进制de转换

十进制&二进制的转换是计算机中比较常见的操作，我们先来了解一下他们是如何转换的

举个栗子：100(10进制)转换

100/2 = 50 余0 ，50/2 = 25 余0 ，25/2 = 12 余1 ，12/2 = 6 余0 ， 6/2 = 3 余0 ，3/2 = 1 ,余1 ，1/2 = 0 余1

得到1100100，这就是十进制数100转换为二进制的结果

那么我们现在知道了十进制转换二进制的原理，那么我们就可以根据栈的特性来对与十进制与二进制转换的封装

function TtoT(tNumber) {
    var stack = new stack
    while (tNumber > 0) {
        stack.push(tNumber%2)
        iNumber = Math.floor(tNumber/2)
    }
    return stack.UtoString
}
复制代码

我们根据栈的先入后出的特性，对待转换数字进行转换，压入转换数字对于2的除法运算的余数，并通过变量保存当前的运算结果为下一次计算做准备，最后获取到我们转换后的栈，当然我们可以将我们上文toString方法的封装，将其倒置，可以得到二进制结果的字符串。

Stack.prototype.UtoString = function (element) {
    var reString = ''
      for (let i = this.items.length; i > 0; i--) {
        reString += this.items[i - 1] + ''
      }
      return reString
}
复制代码