栈和队列
栈(Stack)
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表
特点
后进先出(LIFO即Last in First out),把栈比喻薯片桶,一开始薯片桶的空的,第一片放进去的薯片会在最底部,第二片薯片会在顶部,想要吃掉第一片薯片,就得先把第二片薯片从薯片桶里拿出来or吃掉,然后再拿第一片薯片,也就是最先进去的薯片要到最后才被吃掉。
常用方法
新建一个类
function Stack() {
this.items = []
}
插入元素(压栈)
// 往栈插入一个元素(压栈)
Stack.prototype.push = function (element) {
this.items.push(element)
}
删除元素(出栈)
// 删除并返回栈顶元素(出栈)
Stack.prototype.pop = function (element) {
return this.items.pop()
}
返回栈顶元素
// 返回栈顶元素
Stack.prototype.peek = function (element) {
return this.items[this.items.length - 1]
}
清空栈
// 清空栈
Stack.prototype.clear = function (element) {
this.items = []
}
打印栈
// 打印栈
Stack.prototype.print = function (element) {
console.log(this.items.toString());
}
栈大小
// 判断栈大小
Stack.prototype.size = function (element) {
return this.items.length
}
栈是否为空
// 判断栈是否为空
Stack.prototype.isEmpty = function (element) {
return this.items.length == 0
}
案例
十进制转二进制
采用余数法,和2取余,把得到的结果进行逆序就 是转换结果。比如十进制的10转换为二进制,
第一次:10除以2得5余0
第二次:5除以2得2余1
第三次:2除以2得1余0
第四次:1除以2得0余1
栈实现
进制转换的实现可以比喻成栈,最后计算的结果最先输出,最先计算的结果最后输出(栈也是后进先出)
// 进制转换(栈实现)
function transform(num) {
var stack = new Stack()
var str = ""
while (num > 0) {
var yushu = num % 2 //余数
stack.push(yushu) //入栈
num = Math.floor(num / 2) //每次取余的结果
}
while (!stack.isEmpty()) {
str += stack.pop() + "" //出栈
}
return str
}
console.log(transform(10)) //1010
队列(Queue)
队列是一种先进先出(First in First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。
特点
先进先出(First in First Out),可以把队列比喻成公交车站前面的排队,排队的人们可以看做队列,先排队的人先上车
常用方法
function Queue() {
this.item = []
}
// 入列
Queue.prototype.enqueue = function (ele) {
this.item.push(ele)
}
// 出列
Queue.prototype.dequeue = function () {
return this.item.shift()
}
// 查看队列头
Queue.prototype.front = function () {
return this.item[0]
}
// 检查队列是否为空
Queue.prototype.isEmpty = function () {
return this.item.length == 0
}
// 检查队列大小
Queue.prototype.size = function () {
return this.item.length
}
案例
击鼓传花
// 击鼓传花,给定一个数比如3,一个花,一群人坐在一圈里,一个人拿花喊1,
// 然后把花传给第二个人喊2,第二个人再把花传给第三个人,第三个人喊3并淘汰,
// 继续把花传给下一个人,继续数,继续淘汰,最后一个人是赢家
// 要求,给定一个数和一群人,返回赢家
function game(num, list) {
var queue = new Queue()
for (var i = 0; i < list.length; i++) {
queue.enqueue(list[i])
}
var y = 1
while (queue.size() > 1) { //如果当前队列人数大于1
// 手里有花的且喊的不是num的人往队列最后移
for (var j = 0; j < num - 1; j++) {
queue.enqueue(queue.dequeue())
}
var taotai = queue.dequeue() //花到手且喊num的人里就淘汰
console.log('第' + y + '轮淘汰了:', taotai)
y++
}
return queue.dequeue()
}
//赢家是: a
console.log('赢家是:', game(3, ['a', 'b', 'c', 'd', 'e', 'f']))
优先级队列
普通的队列是一种先进先出(First in First Out)的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征
实现
// 优先级队列
function FirstQueue() {
this.item = []
}
FirstQueue.prototype.enqueue = function (ele, level) {
function QueueItem(ele, level) {
this.ele = ele
this.level = level
}
var quequItem = new QueueItem(ele, level)
var isMin = true
for (var i = 0; i < this.item.length; i++) {
if (this.item[i].level < quequItem.level) {
this.item.splice(i, 0, quequItem)
isMin = false
break
}
}
if (isMin) {
this.item.push(quequItem)
}
}
var firstQueue = new FirstQueue()
console.log(firstQueue)
console.log(firstQueue.enqueue('存10', 1))
console.log(firstQueue.enqueue('存300', 3))
console.log(firstQueue.enqueue('存100000', 10))
console.log(firstQueue.enqueue('存200', 2))
console.log(firstQueue)
版权申明
本文系作者 @admin 原创发布在安忆笔记站点。未经许可,禁止转载。
暂无评论数据