2__栈(先进后出)__
程序员文章站
2024-03-17 21:52:10
...
栈(先进后出)
创建一个基于数组的栈
class Stack {
constructor() {
this.items = [];
}
// 添加一个(或几个)新元素到栈顶
push(element) {
this.items.push(element);
}
// 移除栈顶的元素,同时返回被移除的元素
pop() {
return this.items.pop();
}
// 返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它)
peek() {
return this.items[this.items.length - 1];
}
// 如果栈里没有任何元素就返回true,否则返回false
isEmpty() {
return this.items.length === 0;
}
// 返回栈里的元素个数。该方法和数组的length属性很类似
size() {
return this.items.length;
}
// 移除栈里的所有元素
clear() {
this.items = [];
}
}
创建一个基于 JavaScript 对象的 Stack 类
class Stack {
constructor() {
// 栈的大小
this.count = 0;
this.items = {};
}
// 向栈中插入元素
push(element) {
this.items[this.count] = element;
this.count++;
}
// 栈的大小
size() {
return this.count;
}
// 栈是否为空
isEmpty() {
return this.count === 0;
}
// 从栈中弹出元素
pop() {
if (this.isEmpty()) {
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
// 查看栈顶的值
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
// 清空栈
clear() {
this.items = {};
this.count = 0;
}
// 创建一个toString方法来像数组一样打印出栈的内容
toString() {
if (this.isEmpty()) {
return "";
}
let objString = `${this.items[0]}`;
for (let i = 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
}
保护数据结构内部元素
const _items = Symbol("stackItems");
class Stack {
constructor() {
this[_items] = [];
}
// 向栈中插入元素
push(element) {
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] = [];
}
// 打印栈
print() {
console.log(this.toString());
}
// 创建一个toString方法来像数组一样打印出栈的内容
toString() {
return this[_items].toString();
}
}
用 ES2015 的 WeakMap 实现类
const _items = new WeakMap();
const _count = new WeakMap();
class Stack {
constructor() {
_count.set(this, 0);
_items.set(this, {});
}
// 向栈中插入元素
push(element) {
const items = _items.get(this);
const count = _count.get(this);
items[count] = element;
_count.set(this, count + 1);
}
// 从栈中弹出元素
pop() {
if (this.isEmpty()) {
return undefined;
}
const items = _items.get(this);
let count = _count.get(this);
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;
}
}
从十进制到二进制
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); // {4}
}
while (!remStack.isEmpty()) {
binaryString += remStack.pop().toString();
}
return binaryString;
}
进制转换算法
// 把十进制转换成基数为2~36的任意进制
function baseConverter(decNumber, base) {
const remStack = new Stack();
const digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
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;
}