栈和队列的应用

前言

最近在看数据结构和算法的书，《学习JavaScript数据结构和算法》。记录一下一些感兴趣的算法

一、栈

栈是先进后出的原则

// 栈的类
function Stack(){
	// 栈模拟数据
	let items = []
	// 添加数据。自动加到栈尾
	this.push = function(e){
		items.push(e)
	}
	// 删除数据。自动删除栈尾
	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 = []
	}
}


// 进制转换的方法，传入需要处理的数和进制、输出转换之后的数字
function baseConverter(decNumber,base){
	// 初始化数据，空栈、栈内数据、下一步处理数、用于显示非二进制的数
	var remStack = new Stack(),
		rem,
		baseString = '',
		digite = '0123456789ABCDEF';
	// 遍历数据
	while(decNumber > 0){
		// 栈内的数据。余数
		rem = Math.floor(decNumber % base);
		remStack.push(rem);
		// 下一次循环需要用的数据
		decName=Math.floor(decNumber / base)
	}
	// 遍历栈内数据
	while(!remStack.isEmpty()){
		// 取数据进行十六进制的转换
		baseString += digite[remStrack.pop()]
	}
	return baseString
}

二、队列

队列是先进先出的原则

// 队列类
function Queue(){
	let items = []
	// 添加数据。添加到队列尾部
	this.enqueue=function(e){
		items.push(e)
	}
	//删除数据。删除队列头部
	this.dequeue=function(){
		items.shift()
	}
	// 返回队列头部
	this.front=function(){
		return items[0]
	}
	// 判断队列是否有值
	this.isEmpty=function(){
		return items.length == 0
	}
	// 返回队列长度
	this.size=function(){
		return items.length
	}
}


// 优先队列，在先进先出的原则上再加上优先级
function PriorityQueue(){
	let items = []
	// 创建一个原型，包含优先级
	function QueueElement(element,priority){
		this.element = element
		this.priority = priority
	}
	// 内置方法
	this.enqueue = function(e,p){
		// 初始化对象
		let queueElement = new QueueElement(e,p)
		// 如果队列为空，则直接添加
		if(this.isEmpty()){
			items.push(queueElement)
		}else{
		// 如果队列不为空，则需要判断优先级
			// 判断是否要添加到队列尾部
			let added = false
			// 遍历队列数据
			if(let i=0;i<items.length;i++){
				// 如果数据的优先级小于现有的数据，则直接添加于该数据后面
				if(queueElement.priority < items[i].priority){
					items.splice(i,0,queueElement)
					added = true
					break
				}
			})
			// 如果数据的优先级大于现有的所有数据，则直接添加到队列尾部
			if(!added){
				items.push(queueElement)
			}
		}
	}
}

// 击鼓传花，即鼓声停，花落谁手谁淘汰
function hotPatato(nameList,num){
	// 初始化队列
	let queue = new Queue()
	// 每个人的名字都添加到队列上去。map如果没有返回值，则会返回所有数据的index的数组
	nameList.map(i => queue.enqueue(nameList[i]))
	// 定义被淘汰的人
	let eliminated = ''
	// 循环队列，直到剩下之后一个数据
	while(queue.size() > 1){
		// 模拟鼓声
		for(let i=0;i<num;i++){
			// 谁在队列的头部则花在谁手。先是删除头部的数据，然后排在队尾，表示花给出去
			queue.enqueue(queue.dequeue())
		}
		// 鼓声停，则淘汰
		eliminated = queue.dequeue()
		console.log(`${eliminated}在击鼓传花游戏中淘汰`)
	}
	return queue.dequeue()
}