Javascript[0x02] -- 栈
栈是一种遵从后进先出（LIFO）原则的有序集合
知识点：
- 栈数据结构
- 向栈添加元素
- 从栈移除元素
- 如何使用Stack类
- 十进制转二进制(经典)
栈的一些方法：
- push(element(s))：添加一个（或几个）新元素到栈顶。
- pop()：移除栈顶的元素，同时返回被移除的元素。
- peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
- isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
- isFull(): 如果栈满了，返回false， 在我通过阅读《学习JavaScript数据结构与算法（第二版）》中了解到，没有这个，而现实很多例子像堆栈溢出就有栈满这么一说，一琢磨，加吧。
- clear()：移除栈里的所有元素。
- size()：返回栈里的元素个数。这个方法和数组的length属性很类似。
生活中栈的例子：
生活中栈的例子有很多，像子弹压膛然后发射、课代表把作业交给老师，总是最上面最迟交的那个人先挨批、搞计算机经常听到的内存堆栈溢出等等。
窃以为，栈就是一个稳态。当有一个叫push的家伙往里面塞东西，此时，栈被它改变了。
然后，又有一个叫pop的家伙，从栈的”天灵盖“上一个一个拿走push这位仁兄塞进来的东西。
这样一种客观实在我们称之为”栈“。为了记录push和pop这两位选手在栈中搞事情，于是，我们强烈要求peek、isEmpty、isFull、size、clear、show同志加入其中，组成我们今天要讲的”栈“。
在Javascript中栈和数组实在是太像了，那么我们缕一缕更健康。数组它是可以访问任意一个元素的，而栈它不批准你这样子，你只能访问它最顶上的那位；在内存允许的情况下，数组你可以在任意位置怎么开心怎么插，但是栈你只能往栈顶插入，出去也是一样的；这里有个疑问是栈是不是每次只能传一个，愚以为，只要你能实现，传多个也是可以的啊，所以我这里是认为它可以有，传多个值。
本文目录如下：
Part1 - 我抄书的代码
这里的话，是参考一个外国小姐姐写的《学习Javascript数据结构与算法(第二版)》中的栈，基于ES5的语法写的，后续的话会继续改成ES6的，然后用Typescript也实现下吧，多练练。
整体脉络
我们要明确我们要做什么，我们要实现一个栈。不用太伤害脑子的，我们可以事先做的事，就是罗列下，我们大致需要实现那些功能，能不能符合预期，我们另外说。
stack.js
// 你要实现的栈
function Stack() {
// 一个数组，拿来存放栈里的元素
let items = [];
// 1、push方法，实现元素进栈
this.push = function (element) {
};
// 2、pop方法，实现元素出栈
this.pop = function () {
};
// 3、peek方法，查看栈顶元素
this.peek = function () {
return items[items.length - 1];
};
// 4、判空
this.isEmpty = function () {
};
// 5、获取栈的长度
this.size = function () {
return items.length;
};
// 6、清除栈内数据
this.clear = function () {
items = [];
};
// 7、打印栈的内容
this.print = function () {
console.log(items.toString());
}
}大致是需要实现楼上这些吧，接下来我们一个一个来。
1、push方法
前面我们讲过，用数组来存嘛，那这里自然而然的想到数组的push嘛，所以若楼下所示：
this.push = function (element) {
items.push(element);
};2、pop方法
这个跟楼上也类似的，数组也有pop方法，那就直接用呗，如楼下所示：
this.pop = function () {
return items.pop();
};3、peek方法
我们想知道栈这位选手它的栈顶是什么？在数组的背景下，也就是拿出数组中的最后一个对吧。而数组的下标是从0开始的，那么这里就是lenght - 1对吧，具体的如下：
this.peek = function () {
return items[items.length - 1];
};4、isEmpty方法
什么情况下栈是空的，当且仅当栈的长度为0的时候，在这里也就是数组的长度为0的时候，具体的看楼下：
this.isEmpty = function () {
return items.length === 0;
};5、size方法
就说我们想知道栈的长度，在这里也就是求数组的长度。
this.size = function () {
return items.length;
};6、clear方法
想要清空栈，这里用的是数组，那么，一顿操作猛如虎的做法就是arr = []，如楼下所示：
this.clear = function () {
items = [];
};7、print方法
打印直接打数组似乎有点不美观，这里就转成字符串，更符合审美吧，如楼下：
this.print = function () {
console.log(items.toString());
}至此我们通过JavaScript语言简单地实现了一个栈，关于测试部分，我这里放到第二部分来讲。
Part2 - 我自己实现的代码
期望： 我想实现一个栈，它的长度可控，也就是说，在创建一个栈的对象的时候，你可以传个参数，也可以不传个参数。在进栈方面，我期望它一次可以进一个也可以进多个，出栈方面也是同理，这里你可以选择传参和不传参。除此之外，因为长度可控，那么我们势必要增加一个判满对吧。最后就是格式的输出，这里的话会涉及到一个进制转换问题，那么为了美观，4个一输出，不够补0。
思路： 记得去年有幸在王跃大哥的指导下，用C++写过一版栈。凭着模糊的记忆憋一憋还阔以吧。大致是在外面加入一个计数，然后在对应的方法中讨论极值（这里我也不确切放极端还是极值好，暂且极值吧）问题。因为楼上已经大致讲过一次栈了，所以这里就不费笔墨了，直接贴代码吧。
stack3.0.js
/**
* @description 基于JavaScript的数据结构 - 栈
* @param n n参数可传可不传
* @constructor
* @author Jiangtao Zheng(ataola)
* @contact zjt613@gmail.com
* @github https://github.com/ataola
*/
function Stack(n) {
let items = n === undefined ? [] : new Array(n); //赋予数组状态
let count = 0; //记数
/**
* @description 入栈, 支持插入一个或多个， 多个请用数组传值
* @param element 可以单个插入，也可以多个插入，多个插入传数组
*/
this.push = function (element) {
// 当n不为undefined且栈满的时候，此时插入我不批准
if (n !== undefined && this.isFull()) {
console.log("入栈错误报警：栈满请注意，栈满请注意，栈满请注意！");
return;
}
if (element instanceof Array) {
element.map(value => {
items[count] = value;
count++;
})
} else {
items[count] = element;
count++;
}
};
/**
* @description 出栈，可以出一个或多个元素
* @param m m可以不传，数字代表出栈个数
* @returns {*} 返回出栈元素
*/
this.pop = function (m) {
//当n为undefined或者栈空时
if ((n === undefined && count === 0) || this.isEmpty()) {
console.log("出栈错误报警：栈空请注意，栈空请注意，栈空请注意！");
return;
}
if (m === undefined) {
let cur = items[count - 1];
items[count - 1] = undefined;
count--;
return cur;
}
if (m > 0) {
let res = [];
while (m !== 0) {
res.push(items[count - 1]);
items[count - 1] = undefined;
count--;
m--;
}
return res.toString();
} else {
let res = items[count - 1];
count--;
return res;
}
};
/**
* @description 判空
* @returns {boolean}
*/
this.isEmpty = function () {
return count === 0;
};
/**
* @description 判满
* @returns {boolean}
*/
this.isFull = function () {
if (count === 0 && n === undefined) {
return false;
}
return count === items.length;
};
/**
* @description 查栈顶元素
* @returns {*} 返回栈顶的元素
*/
this.peek = function () {
return items[count - 1];
};
/**
* @description 清除栈所有元素
*/
this.clear = function () {
items.fill(undefined, 0, count);
count = 0;
};
/**
* @description 查栈的长度
* @returns {*} 返回栈的长度
*/
this.size = function () {
return items.length;
};
/**
* @description 查栈实体部分长度
* @returns {number} 返回栈实体部分长度
*/
this.currSize = function () {
return count;
};
/**
* @description 打印栈的所有元素
*/
this.show = function () {
return items.toString();
};
/**
* @description 打印栈的实体元素
*/
this.currShow = function () {
return items.slice(0, count).toString();
}
}Part3 - 测试
代码不经过测试是一件极其危险且不负责任的事，而测试用例的选取，很有门道，运气好，错的也能测成对的，就看你怎么思考用例了，那我们接下来思考下这边要测什么？
很显然，我们想把楼上写的方法都测一遍或者多遍（排除偶然性），那么我们就要思考测试用例怎么写？
组织下语言大致是这样子，我们创建了一个栈对象，我们先来一波判空，这个时候我们期望得到的答案是对的也就是true。紧接着我们测push，往里面塞0-9个正整数，这个时候我们判断的依据是有 10个元素。然后我们开始测pop，把最后面5个给干掉，这个时候我们意思下来个判空和判满，预期都是false。然后我们开始测peek，如果我们思考是同步的话，那么答案应该是4，我们再测下size，也就是这个栈的总长度，应该是10，再测下currSize，当前的长度，因为出去了5个，所以现在还剩5个，最后我们把它全清空。经过摩卡测试，结果符合预期。
问题思考
数组中的空，占“坑”吗？
愚以为是占“坑”位的，就说我们通过let arr = new Array(20), 然后通过arr.push(21),我们发现它是第21个，而前面20个空的是undefined。
做个进制转换的例子
这里就是存的时候取余和整除，然后存的时候整理下输出，如楼下：
const Stack = require('./stack3.0');
function binaryConver() {
this.decToBin = function (num) {
let stack = new Stack();
let count = 0;
let cur = num;
while(cur !== 0) {
stack.push(cur % 2);
cur = Math.floor(cur / 2);
count ++;
}
while(count % 4 !== 0) {
stack.push(0);
count ++;
}
return stack.currShow().split(",").reverse().join("");
}
}我们分别取613、2019、1997、1023、521作为测试用例，经过摩卡测试，还阔以。
以上就是今天的全部内容，感谢您的收听，祝您生活愉快！