1. 栈数据结构
- 栈是类似于数组的数据结构，在添加和删除元素时更为可控。
- 遵从后进先出（LIFO）原则的有序组合。
- 新添加或待删除的元素保存在栈顶。
- 栈可被用在编程语言的编译器和内存中保存变量、方法调用等，也被用于浏览器历史记录（浏览器返回按钮）。
JavaScript数据结构与算法 - 栈1. 栈数据结构2. 创建一个基于JavaScript对象的Stack类3. 保护数据结构内部元素4. 将十进制转换为二进制5. 进制转换算法
1.1 创建一个基于 数组
数组
创建一个类来表示栈：
class Stack {
constructor() {
this.items = []; // 可以选择数组来保存栈里的元素
};
// 方法
}
为栈声明一些方法：
- push(element(s))：添加一个（或几个）新元素到栈顶
- pop()：移除栈顶的元素，同时返回被移除的元素
- peek()：返回栈顶的元素，不对栈做任何修改
- isEmpty()：如果栈里没有任何元素就返回true，否则返回false
- clear()：移除栈里所有元素
- size()：返回栈里的元素个数
1.2 向栈添加元素
只添加元素到栈顶，即栈的末尾。
可以同时向Stack类中添加多个元素。
push(element) {
this.items.push(element);
}
1.3 从栈移除元素
移除的是最后添加进去的元素。
pop() {
return this.items.pop();
}
1.4 查看栈顶元素
// 因为类内部是用数组保存的，所以访问数组的最后一个元素可以用 length - 1
peek() {
return this.items[this.items.length - 1];
}
1.5 检查栈是否为空
isEmpty() {
// 简单判断内部数组的长度是否为0
return this.items.length === 0;
}
1.6 栈的大小
类似数组的length属性，我们也能实现栈的length。
对于集合，栈最好用size代替length。因为栈的内部使用数组保存元素，所以能简单地返回栈的长度。
size() {
retutn this.items.length;
}
1.7 清空栈元素
clear() {
this.items = [];
}
也可以用多次pop方法，把数组元素全部移除。
1.8 使用Stack类
<script>
class Stack {
constructor() {
this.items = [];
};
// 声明方法
// 添加元素
push(element) {
return this.items.push(element);
};
// 移除元素
pop() {
return this.items.pop();
};
// 查看栈顶元素
peek() {
return this.items[this.items.length - 1];
};
// 判断栈是否为空
isEmpty() {
return this.items.length === 0;
};
// 栈的长度
size() {
return this.items.length;
};
// 清空栈元素
clear() {
this.items = [];
};
}
// 先初始化类
const stack = new Stack();
// 检验栈是否为空
console.log(stack.isEmpty()); // true
// 往栈中添加元素
stack.push(10);
stack.push(20);
console.log(stack); // [10, 20]
console.log(stack.isEmpty()); // false
// 查看栈顶元素
console.log(stack.peek()); // 20
stack.push(30); // [10, 20, 30]
// 查看栈的长度
console.log(stack.size()); // 3
// 移除栈顶元素
stack.pop();
console.log(stack.size()); // 2
</script>
- 使用数组时，大部分方法时间复杂度为O(n)
- 数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间
2. 创建一个基于JavaScript 对象
对象
先声明一个Stack类：
class Stack {
constructor() {
this.count = 0; // 记录栈的大小
this.items = {};
};
// 方法
}
2.1 向栈中插入元素
对象的版本不同于数组版本，只允许一次插入一个元素。
push(element) {
this.items[this.count] = element;
this.count++;
}
在JavaScript中，对象是一系列键值对的集合。
所以向栈中添加元素时，将使用count变量作为items对象的键名，插入的元素是它的值。
使用：
const stack = new Stack();
stack.push(10);
stack.push(20);
2.2 验证一个栈是否为空
可以直接判断count是否为0。
isEmpty() {
return this.count === 0;
}
2.3 栈的大小
可以简单返回count属性的值来实现size。
size() {
return this.count;
}
2.4 从栈中弹出元素
pop() {
// 先检验栈是否为空
if (this.isEmpty()) {
return undefined;
}
this.count--;
// 保存栈顶的值，以便在删除后将它返回
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
使用：
2.5 查看栈顶的值
peek() {
if(this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
2.6 清空栈元素
clear() {
this.items = {};
this..count = 0;
}
也可以遵循后进先出原则使用pop方法删除
while(!this.isEmpty()) {
this.pop();
}
2.7 创建toString方法
数组版本中，可以直接使用数组已经提供的toString方法。
对象版本，需要创建一个toString方法来像数组一样打印出栈的内容。
toString() {
// 如果栈为空，返回一个空字符串
if (this.isEmpty()) {
return ''
}
// 用底部的第一个元素作为字符串的初始值
let objString = `${this.items[0]}`;
// 如果只有1个元素，循环不执行
// 迭代整个栈的健，直到栈顶
for (let i = 1; i < this.count; i++) {
// 添加一个逗号以及下一个元素
objString = `${objString}, ${this.items[i]}`;
}
return objString;
}
3. 保护数据结构内部元素
希望Stack类的用户只能访问我们在类中暴露的方法。
3.1 下划线命名约定
部分开发者喜欢在JavaScript中使用下划线命名约定一个属性为私有属性。
class Stack {
constructor() {
this._count = 0;
this._items = {};
}
}
这种方式只是一种约定，并不能保护数据，只能依赖于开发者所具备的常识。
3.2 用限定作用域 Symbol
Symbol
ES2015新增了Symbol的基本类型，它是不可变的，可以用作对象的属性。
// 声明了Symbol类型的变量_items
const _items = Symbol('stackItems');
class Stack {
// 初始化_items的值
constructor() {
this[_items] = [];
}
// 栈的方法
}
要访问_items，只需要把所有的this.items换成this.[_items]
这种方法创造了一个假的私有属性，因为Object.getOwnPropertySymbol方法能够取到类里面声明的所有Symbol属性。
一个破坏Stack类的例子：
const stack = new Stack();
stack.push(10);
stack.push(20);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1); // 10,20,1
stack.print();
上面的代码可以访问到_items，并且_items属性是一个数组，可以进行任意的数组操作。但我们操作的是栈，不应该出现这种行为。
3.3 WeakMap
WeakMap
- WeakMap可以确保属性是私有的
- 可以存储键值对，其中键是对象，值是可以任意数据类型
// 声明一个WeakMap类型的变量items
const items = new WeakMap();
class Stack {
constructor() {
// 以this为键，把代表栈的数组存入items
items.set(this, []);
}
push(element) {
// 以this为键从items中取值
const s = items.get(this);
const r = s.pop();
return r;
}
// 其他方法
}
但是采用这种方法，代码可读性不强，而且在扩展该类时无法继承私有属性。
4. 将十进制转换为二进制
<script>
class Stack {
constructor() {
this.items = [];
};
// 声明方法
// 添加元素
push(element) {
return this.items.push(element);
};
// 移除元素
pop() {
return this.items.pop();
};
// 查看栈顶元素
peek() {
return this.items[this.items.length - 1];
};
// 判断栈是否为空
isEmpty() {
return this.items.length === 0;
};
// 栈的长度
size() {
return this.items.length;
};
// 清空栈元素
clear() {
this.items = [];
};
};
function decimalToBinary(decNumber) {
const remStack = new Stack();
let number = decNumber;
let rem;
let binaryString = '';
while (number > 0) {
rem = Math.floor(number % 2);
remStack.push(rem);
number = Math.floor(number / 2);
}
while (!remStack.isEmpty()) {
// 把出栈的元素连接成字符串
binaryString += remStack.pop().toString();
}
return binaryString;
}
console.log(decimalToBinary(10)); // 1010
</script>
5. 进制转换算法
<script>
class Stack {
constructor() {
this.items = [];
};
// 声明方法
// 添加元素
push(element) {
return this.items.push(element);
};
// 移除元素
pop() {
return this.items.pop();
};
// 查看栈顶元素
peek() {
return this.items[this.items.length - 1];
};
// 判断栈是否为空
isEmpty() {
return this.items.length === 0;
};
// 栈的长度
size() {
return this.items.length;
};
// 清空栈元素
clear() {
this.items = [];
};
};
function baseConverter(decNumber, base) {
const remStack = new Stack();
// 从十一进制开始，字母表中的字母将代表相应基数
const digits = '0123456789ABCDEFGHIJKLMNOPQRETUVWXYZ';
let number = decNumber;
let rem;
let baseString = '';
if (!(base >= 2 && base <= 36)) {
return '';
}
while (number > 0) {
rem = Math.floor(number % base);
remStack.push(rem);
number = Math.floor(number / base);
}
while (!remStack.isEmpty()) {
baseString += digits[remStack.pop()];
}
return baseString;
}
console.log(baseConverter(167, 16)); // A7
</script>