基本概念
夯下数据结构和算法基础,JS 里没有栈、队列、链表巴拉巴拉明显的结构,只能用类去伪造,不然做算法题真的费劲。
先造最简单的栈类吧,这边底层使用数组,当然有空的话,你也可以试试对象。
- 栈是一种遵从后进先出(LIFO)原则的有序集合
- 新添加或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底(类似,叠盘子)
- 在栈里,新元素都靠近栈顶,旧元素都靠近栈底。
基本方法
- push(i) 添加一个(或几个)新元素到栈顶。
- pop() 移除栈顶的元素,同时返回被移除的元素。
- peek() 返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它)。
- isEmpty() 如果栈里没有任何元素就返回 true,否则返回 false。
- clear() 移除栈里的所有元素。
- size() 返回栈里的元素个数。这个方法和数组的 length 属性很类似。
类实现
class Stack {
stack: any[];
constructor() {
this.stack = [];
}
size() {
return this.stack.length;
}
peek() {
return this.stack[this.stack.length - 1];
}
push(value: any) {
this.stack.push(value);
}
pop() {
return this.stack.pop();
}
isEmpty() {
return this.size() === 0;
}
clear() {
this.stack = [];
}
}
可以头上顶个注释,就容易调用方法了
应用场景
栈的应用场景:浏览器的历史记录、存储访问过的任务、撤销的操作等等。
练习 1:十进制数字转化为二进制
十进制数字转化为二进制的逻辑是:
关键逻辑:用十进制数除以 2,得到的余数存入栈中,得到的商(迭代)继续除以 2, 得到的余数再继续存入栈中(循环),直到商为 0 为止(终止条件)。
function toBinary(decNumber: number) {
const s = new Stack();
// 迭代指针,每次得到的商,初始是原始值
let p = decNumber;
// 商不为0 就一直循环
while (p !== 0) {
// 余数进栈
s.push(p % 2);
// 迭代
p = Math.floor(p / 2);
}
let result = '';
// 数字出栈,拼接,直至栈为空
while (!s.isEmpty()) {
result += s.pop();
}
return result;
}
加上注释的话
练习 2:十进制数字转化为任意进制
转化逻辑和上面的二进制大同小异,但这里有个限制,任意进制的范围是 2-36,然后超过 10 就是ABCD....
,注意下这里就行
function toBaseConverter(decNumber: number, base: number) {
// 范围限定
if (base < 2 || base > 36) throw new Error('base must between 2 and 36');
const s = new Stack();
let p = decNumber;
// 加了这行,超过10的表示
const baseStr = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
while (p !== 0) {
// s.push(p % 2) 换下,因为有字母,所以这样写法,没有字母的话p % base就够用
s.push(baseStr[p % base]);
// p = Math.floor(p / 2) 的2换成base
p = Math.floor(p / base);
}
let result = '';
while (!s.isEmpty()) {
result += s.pop();
}
return result;
}
加上注释的话
引用
- 《JavaScript数据结构与算法》(希望我能看完)
以上就是JS表示Stack类练习用栈实现任意进制转换的详细内容,更多关于JS表示Stack类进制转换的资料请关注编程网其它相关文章!