栈的出入js实现_js实现栈结构
实现栈结构
//创建栈
function Stack (){
let items = []
this.push = function(element){
items.push(element)
}
this.pop = function(){
return items.pop()
}
this.peek = function(){
return items[items.length - 1]
}
this.isEmpty = function(){
return items.length === 0
}
this.size = function(){
return items.length
}
this.clear = function(){
items = []
}
this.print = function(){
console.log(items.toString())
}
}
ES6改造
//使用Symbol添加私有属性
class Stack {
let _items = Symbol()
constructor(){
this[_items] = []
}
push(element){
this[_items].push(element)
}
}
//可以拿到所有的symbol对象
Object.getOwnPropertySymbols(Stack)
//使用weakMap
const items = new weakMap()
class Stack {
constructor(){
items.set(this,[])
}
push(element){
let s = items.get(this)
s.push(element)
}
pop(){
let s = items.get(this)
let r = s.pop()
return r
}
}
//利用闭包实现私有属性
let Stack = (function(){
const items = new WeackMap()
class Stack {
constructor(){
items.set(this,[])
}
push(element){
let s = items.get(this)
s.push(element)
}
pop(){
let s = items.get(this)
let r = s.pop()
return r
}
}
return Stack
})()
进制转换
//10进制转2进制
function divideBy2(decNumber){
var remStack = new Stack(),
rem,
binaryString = '';
while(decNumber > 0){
rem = Math.floor(decNumber % 2)
remStack.push(rem)
decNumber = Math.floor(decNumber / 2)
}
while(!remStack.isEmpty()){
binaryString += remStack.pop().toString()
}
}
//任意进制转换
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;
}
平衡圆括号
function balancedSymbols(symbols){
const stack = new Stack()
const opens = `([{`
const closers = `)]}`
let balanced = true
let index = 0
let symbol
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()
}
汉诺塔
递归，即定义一组基本操作，这组操作将规模小一点(或大一点)的操作当做一个整体——无需关心它的细节，只当它已经完成了——然后执行剩下的操作。而在更小或更大的规模中也依此操作，直到规模达到预定值。
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 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 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])
}
return moves
}
//用栈来实现汉诺塔
console.log(hanoiStack(3));
//用递归来来实现
console.log(hanoi(3, 'source', 'helper', 'dest'));