认识栈结构
我们先来回顾一下数组结构，我们知道数组是一种线性结构，并且可以在数组的任意位置插入和删除，但是有时候，我们为了实现某些功能，必须对这种任意性加以限制而栈和队列就是比较常见的受限的线性数据结构。
在Js中栈结构更像是一种变种的数组。只是没有那么多的方法，也没有数组那么的灵活，但是栈和队列两种数据结构比数组更加高效和可控。而在js中模拟栈，依据的主要形式也是数组或链表，要想实现一个数据结构，首先你要先明白他的基本原理，那么栈是什么，又是如何工作的呢?
栈（stack）是一种遵循先进后出（last in first out）原则的有序集合，新添加的元素和待删除的元素都会保存在栈的同一端，称为栈顶，另一端叫做栈底，在栈里，新元素都接近栈顶，旧元素都接近栈底，我们其实可以把栈结构比喻成一个羽毛球桶。
其限制是只允许在表的一端，进行插入和删除操作，这一端被成为栈顶，相对的，另一端被称为栈底，LIFO（last in first out）表示的就是最后进入的元素将第一个弹出，类似于羽毛球同，先放进去的羽毛球只能最后拿出来，而最后放进去的羽毛球只能第一个拿出来，向一个栈结构中插入新元素称作进栈，入栈或压栈，它是把新元素放在栈顶元素的上面，使之成为新的栈顶元素。从一个栈删除元素又被成为出栈，它是把栈顶元素删除掉，使其相邻的元素吃成为新的栈顶元素
学了这么久的编程是否听说过函数调用栈呢？我们知道函数之间可以相互调用：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依次弹出栈口所以我们有函数调用栈的称呼,就来自于它们内部的实现机制(通过栈结构实现的)
经典面试题
有6个元素 :6，5，4，3，2，1他们会按照顺序进栈（不是一次性），问下列哪一个是不合法的出栈顺序？
1.5，4，3，6，1，2
2.4，5，3，2，1，6
3.3，4，6，5，2，1
4.2，3，4，1，5，6
实现
由于js中原生没有提供栈的数据结构，下面我们就简单做一下简单封装，并实现栈结构常用的操作方法，其中用到了 ES6的新特性 Map（集合）
//通过闭包把声明的变量变成私有属性
let Stack = (function() {
//声明栈的基本依赖
const _items = new WeakMap();
//声明计数器
const _count = new WeakMap();
return class Stack {
constructor() {
//初始化stack和计数器的值，这里的set是WeakMap的自身方法，通过set和get来设置值和取值，这里用this作为设置值的键名，那this又指向啥呢？自行console！
_count.set(this, 0);
_items.set(this, {});
console.log(_items.get(this))
}
// 入栈
push(element) {
//在入栈之前先获取长度和栈本身
const items = _items.get(this);
const count = _count.get(this);
//这里要注意_count可是从0开始的噢
items[count] = element;
_count.set(this, count + 1);
console.log(_items.get(this))
}
// 出栈
pop() {
//如果为空，那么则无法出栈
if (this.isEmpty()) {
return undefined;
}
//获取items和count，使长度减少1
const items = _items.get(this);
let count = _count.get(this);
count--;
//重新为_count赋值
_count.set(this, count);
//删除出栈的元素，并返回该元素
const result = items[count];
delete items[count];
return result;
}
// 查看栈顶元素
peek() {
if (this.isEmpty()) {
return undefined;
}
const items = _items.get(this);
const count = _count.get(this);
//返回栈顶元素
return items[count - 1];
}
// 判断栈是否为空
isEmpty() {
return _count.get(this) === 0;
}
// 栈的大小
size() {
return _count.get(this);
}
// 清空栈
clear() {
/* while (!this.isEmpty()) {
this.pop();
} */
_count.set(this, 0);
_items.set(this, {});
}
// 将栈结构转换为字符串返回
toString() {
if (this.isEmpty()) {
return "";
}
const items = _items.get(this);
const count = _count.get(this);
let objString = `${items[0]}`;
for (let i = 1; i < count; i++) {
objString = `${objString},${items[i]}`;
}
return objString;
}
// 想控制台打印栈结构
print() {
console.log(this.toString());
}
};
})();
const stack = new Stack();
stack.push(1);
stack.push(3);
// stack.print(); // 1, 3, 1
上面我们简单实现了一下栈结构的封装，其中包括了常用的方法，压栈，出栈，判断栈是否为空，查看栈结构的字符串内容等
那下面我们就做个简单的应用，利用栈结构将十进制数字转换为二进制数字
// 利用栈结构 将 10进制数字转换为2进制数字
function dec2bin(decNumber){
// 新建栈结构
let s = new Stack()
// 循环 接收的参数大于0就 进入循环
while (decNumber > 0) {
// 向栈中添加一条数据
// 参数求模，并添加
s.push(decNumber % 2)
// 改变devNumber 的值
// 向下取整
decNumber = Math.floor(decNumber / 2)
}
// 定义返回值
let bindaryString = ''
while (!s.isEmpty()) {
bindaryString += s.pop()
}
return bindaryString
}
console.log(dec2bin(10))
console.log(dec2bin(100))
console.log(dec2bin(1000))
