认识栈结构
- 栈也是一种非常常见的数据结构，并且在程序中的应用非常广泛
- 数组：
- 我们知道数组是一种线性结构，并且可以在数组的任意位置插入和删除数据
- 但是，有些时候，我们为了实现一些功能，必须对这种任意性加以限制
- 而栈和队列就是比较常见的受限的线性结构，我们先来学习栈结构
- 栈结构：只能栈顶进，也只能栈顶出
- 插入新元素为入栈/压栈 ，删除元素出栈/退栈
程序中什么是使用栈实现的？
- 函数调用栈：A调用B ，B调用C，C又调用D
- 那样在执行过程中，会先将A压入栈，A没有执行完，所以不会弹出栈
- 在A执行过程中，调用了B,会将B压入到栈，这个时候B在栈顶，A在栈底
- 以此类推
- 栈底A->B->C->D栈顶，D执行完，弹出栈，C/B/D依此弹出
- 所以我们有函数调用栈的称呼，就来自于他们内部的实现机制（通过栈来实现）
- 递归：如果递归无限次一直调用，就会出现栈溢出的情况，不断压入同一个函数，他前面的函数并不能及时的释放
栈结构面试题：
有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈顺序？（）
A.543612 B.453216 c.346521 D.234156
//答案：选c
解析：A答案：65进栈，5出栈，4进栈出栈，3进栈出栈，6出栈，21进栈，1出栈，2出栈
BC答案依此类推
六个元素不一定是连续进栈，只是进栈的顺序要这个顺序。
栈结构封装以及常见操作（这里以数组的方式模拟）
- 实现栈结构有两种比较常见的方式：
- 什么是链表？
- 也是一种数据结构，目前我们还没有学习，并且js中并没有自带链表结构
- 后续，我们会自己实现链表结构，并且对比数组和链表的区别
// method：方法，和某一个对象实例有联系
// function: 函数
// 封装栈类
function Stack() {
// 栈中的属性
this.items = [20,10,100]
// 栈的相关操作
// 1.将元素压入到栈
Stack.prototype.push = function(element){ //给栈类添加原型方法
this.items.push(element)
}
// 2.从栈中取出元素(数组的最后一个元素)
Stack.prototype.pop = function(){ //给栈类添加原型方法
return this.items.pop()
}
// 3.查看一下栈顶元素(pop取出会将元素删除，而这里peek只查看)
Stack.prototype.peek = function(){
return this.items[this.items.length-1]
}
// 4.判断栈是否为空
Stack.prototype.isEmpty = function(){
return this.items.length ==0
}
// 5.获取栈中元素的个数
Stack.prototype.size = function(){
return this.items.length
}
// 6.toString方法
Stack.prototype.toString = function(){
//20 10 12 8 7
let resultString =''
for(let i=0 ; i<this.items.length ; i++){
resultString += this.items[i]+''
}
return resultString
}
}
//栈的使用
var s = new Stack()
s.push(77)
console.log(s)
s.pop()
s.pop()
console.log(s)
console.log(s.peek())
console.log(s.isEmpty())
console.log(s.size())
栈_十进制转二进制
十进制与二进制如何算？
十进制数：100
计算：100/2 余数0
计算：50/2 余数0
计算：25/2 余数1
计算：12/2 余数0
计算：6/2 余数0
计算：3/2 余数1
计算：1/2 余数1
所以从下往上结合：二进制数为1100100
封装函数，将一个十进制转换成二进制：
和栈有什么关系？因为：我们的余数相当于不断压栈，但是确实从最后的栈顶开始取数
代码实现：
// 十进制转二进制
function dec2bin(decNum) {
//1.定义栈对象 （这里使用我们上面封装好的Stack栈类）
var stack = new Stack()
//2.循环操作 (不确定次数的情况下最好用while循环)
while (decNum > 0) {
//2.1 获取余数，并且放入栈中
stack.push(decNum % 2)
//2.2 获取整除后的结果，作为下一次运行的数字
decNum = Math.floor(decNum / 2)
}
//从栈中取出0和1
var binaryString = ''
while (!stack.isEmpty()) { //判断是否栈空
binaryString += stack.pop()
}
return binaryString
}
console.log(dec2bin(100))