ES6的JavaScript数据结构实现之栈

目的：ES6标准下的JS数据结构的一些实现代码。（作为记录和启发）

内容：栈。（未完成，待继续）

所有源码在我的Github上（如果觉得不错记得给星鼓励我哦）：ES6的JavaScript数据结构实现之栈

一、基础数据结构

1、栈（先入后出）

// @ts-check

class Stack {
constructor() {
this.count = 0;
this.items = {};
}

push(element) {
this.items[this.count] = element;
this.count++;
}

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];
}

isEmpty() {
return this.count === 0;
}

size() {
return this.count;
}

clear() {
/* while (!this.isEmpty()) {
this.pop();
} */
this.items = {};
this.count = 0;
}

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 stack = new Stack(); // new StackArray();

// using WeakMap to store Stack items we ensure true privacy
// console.log(Object.getOwnPropertyNames(stack));
// console.log(Object.keys(stack));
// console.log(stack.items);

console.log('stack.isEmpty() => ', stack.isEmpty()); // outputs true

stack.push(6);
stack.push(8);

console.log('stack after push 5 and 8 => ', stack.toString());

console.log('stack.peek() => ', stack.peek()); // outputs 8

stack.push(11);

console.log('stack.size() after push 11 => ', stack.size()); // outputs 3
console.log('stack.isEmpty() => ', stack.isEmpty()); // outputs false

stack.push(15);

stack.pop();
stack.pop();

console.log('stack.size() after push 15 and pop twice => ', stack.size());

Stack

二、栈应用：数据进制转换；平衡圆括号；汉诺塔

1、由十进制传为二进制。

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(233));//输出转换结果11101001

decimalToBinary

2、同理，可以把任意十进制转为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;
}

console.log(baseConverter(1023, 2));
console.log(baseConverter(1023, 4));
console.log(baseConverter(1023, 16));
console.log(baseConverter(1023, 25));

baseConverter

3、平衡圆括号

function parenthesesChecker(symbols){
const stack = new Stack();
const opens ='([{';
const closers = ')]}';
let symbol;
let balanced = true;
let index = 0;
let top;
while (index < symbols.length && balanced) {
symbol = symbols[index];
if (opens.indexOf(symbol) >= 0) {
stack.push(symbol);
} else if (stack.isEmpty()) {
balanced = false;
} else {
top = stack.pop();
if (!(opens.indexOf(top) === closers.indexOf(symbol))){
balanced = false ;
}
}
index++;
}
return balanced && stack.isEmpty();
}

console.log(parenthesesChecker('{}()([])'));//true
console.log(parenthesesChecker('{}()([}{}])'));//false

parenthesesChecker

4、汉诺塔

//注释：汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

//例如把一根柱子上的3个盘移动到另一根柱子上。

//构建汉诺塔结构
function hanoiStack(plates) {
const source = new Stack();
const dest = new Stack();
const helper = new Stack();

for (let i = plates; i > 0; i--) {
source.push(i);
}

return towerOfHanoi(plates, source, helper, dest, 'source', 'helper', 'dest');
}

function towerOfHanoi(plates, source, helper, dest, sourceName, helperName, destName, moves = []) {
if (plates <= 0) {
return moves;
}
if (plates === 1) {
dest.push(source.pop());
const move = {};
move[sourceName] = source.toString();
move[helperName] = helper.toString();
move[destName] = dest.toString();
moves.push(move);
} else {
towerOfHanoi(plates - 1, source, dest, helper, sourceName, destName, helperName, moves);
dest.push(source.pop());
const move = {};
move[sourceName] = source.toString();
move[helperName] = helper.toString();
move[destName] = dest.toString();
moves.push(move);
towerOfHanoi(plates - 1, helper, source, dest, helperName, sourceName, destName, moves);
}
return moves;
}

function hanoi(plates, source, helper, dest, moves = []) {
if (plates <= 0) {
return moves;
}
if (plates === 1) {
moves.push([source, dest]);
} else {
hanoi(plates - 1, source, dest, helper, moves);
moves.push([source, dest]);
hanoi(plates - 1, helper, source, dest, moves);
}
return moves;
}

console.log(hanoiStack(3));

/*

[ { source: '3,2', helper: '', dest: '1' },
{ source: '3', dest: '1', helper: '2' },
{ dest: '', source: '3', helper: '2,1' },
{ source: '', helper: '2,1', dest: '3' },
{ helper: '2', dest: '3', source: '1' },
{ helper: '', source: '1', dest: '3,2' },
{ source: '', helper: '', dest: '3,2,1' } ]

*/

console.log(hanoi(3, 'source', 'helper', 'dest'));

/*

[ [ 'source', 'dest' ],
[ 'source', 'helper' ],
[ 'dest', 'helper' ],
[ 'source', 'dest' ],
[ 'helper', 'source' ],
[ 'helper', 'dest' ],
[ 'source', 'dest' ] ]

*/

hanoiStack