栈是一种遵从后进先出(LIFO)原则的有序集合
知识点:
栈的一些方法:
生活中栈的例子:
生活中栈的例子有很多,像子弹压膛然后发射、课代表把作业交给老师,总是最上面最迟交的那个人先挨批、搞计算机经常听到的内存堆栈溢出等等。
窃以为,栈就是一个稳态。当有一个叫push的家伙往里面塞东西,此时,栈被它改变了。
然后,又有一个叫pop的家伙,从栈的”天灵盖“上一个一个拿走push这位仁兄塞进来的东西。
这样一种客观实在我们称之为”栈“。为了记录push和pop这两位选手在栈中搞事情,于是,我们强烈要求peek、isEmpty、isFull、size、clear、show同志加入其中,组成我们今天要讲的”栈“。
在Javascript中栈和数组实在是太像了,那么我们缕一缕更健康。数组它是可以访问任意一个元素的,而栈它不批准你这样子,你只能访问它最顶上的那位;在内存允许的情况下,数组你可以在任意位置怎么开心怎么插,但是栈你只能往栈顶插入,出去也是一样的;这里有个疑问是栈是不是每次只能传一个,愚以为,只要你能实现,传多个也是可以的啊,所以我这里是认为它可以有,传多个值。
本文目录如下:
这里的话,是参考一个外国小姐姐写的《学习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());
}
}
大致是需要实现楼上这些吧,接下来我们一个一个来。
前面我们讲过,用数组来存嘛,那这里自然而然的想到数组的push嘛,所以若楼下所示:
this.push = function (element) {
items.push(element);
};
这个跟楼上也类似的,数组也有pop方法,那就直接用呗,如楼下所示:
this.pop = function () {
return items.pop();
};
我们想知道栈这位选手它的栈顶是什么?在数组的背景下,也就是拿出数组中的最后一个对吧。而数组的下标是从0开始的,那么这里就是lenght - 1对吧,具体的如下:
this.peek = function () {
return items[items.length - 1];
};
什么情况下栈是空的,当且仅当栈的长度为0的时候,在这里也就是数组的长度为0的时候,具体的看楼下:
this.isEmpty = function () {
return items.length === 0;
};
就说我们想知道栈的长度,在这里也就是求数组的长度。
this.size = function () {
return items.length;
};
想要清空栈,这里用的是数组,那么,一顿操作猛如虎的做法就是arr = [],如楼下所示:
this.clear = function () {
items = [];
};
打印直接打数组似乎有点不美观,这里就转成字符串,更符合审美吧,如楼下:
this.print = function () {
console.log(items.toString());
}
至此我们通过JavaScript语言简单地实现了一个栈,关于测试部分,我这里放到第二部分来讲。
期望: 我想实现一个栈,它的长度可控,也就是说,在创建一个栈的对象的时候,你可以传个参数,也可以不传个参数。在进栈方面,我期望它一次可以进一个也可以进多个,出栈方面也是同理,这里你可以选择传参和不传参。除此之外,因为长度可控,那么我们势必要增加一个判满对吧。最后就是格式的输出,这里的话会涉及到一个进制转换问题,那么为了美观,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();
}
}
代码不经过测试是一件极其危险且不负责任的事,而测试用例的选取,很有门道,运气好,错的也能测成对的,就看你怎么思考用例了,那我们接下来思考下这边要测什么?
很显然,我们想把楼上写的方法都测一遍或者多遍(排除偶然性),那么我们就要思考测试用例怎么写?
组织下语言大致是这样子,我们创建了一个栈对象,我们先来一波判空,这个时候我们期望得到的答案是对的也就是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作为测试用例,经过摩卡测试,还阔以。
以上就是今天的全部内容,感谢您的收听,祝您生活愉快!