栈(Stack)
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表
特点
后进先出（LIFO即Last in First out），把栈比喻薯片桶，一开始薯片桶的空的，第一片放进去的薯片会在最底部，第二片薯片会在顶部，想要吃掉第一片薯片，就得先把第二片薯片从薯片桶里拿出来or吃掉，然后再拿第一片薯片，也就是最先进去的薯片要到最后才被吃掉。
常用方法
代码语言：javascript复制新建一个栈类
function Stack() {
this.items = []
}插入元素(压栈)
代码语言：javascript复制// 往栈插入一个元素（压栈）
Stack.prototype.push = function (element) {
this.items.push(element)
}删除元素(出栈)
代码语言：javascript复制// 删除并返回栈顶元素（出栈）
Stack.prototype.pop = function (element) {
return this.items.pop()
}返回栈顶元素
代码语言：javascript复制// 返回栈顶元素
Stack.prototype.peek = function (element) {
return this.items[this.items.length - 1]
}清空栈
代码语言：javascript复制// 清空栈
Stack.prototype.clear = function (element) {
this.items = []
}打印栈
代码语言：javascript复制// 打印栈
Stack.prototype.print = function (element) {
console.log(this.items.toString());
}栈大小
代码语言：javascript复制// 判断栈大小
Stack.prototype.size = function (element) {
return this.items.length
}栈是否为空
代码语言：javascript复制// 判断栈是否为空
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 将得到的结果进行逆序，所以十进制的10转换为二进制是1010
栈实现
代码语言：javascript复制进制转换的实现可以比喻成栈，最后计算的结果最先输出，最先计算的结果最后输出（栈也是后进先出）
// 进制转换(栈实现)
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），可以把队列比喻成公交车站前面的排队，排队的人们可以看做队列，先排队的人先上车
常用方法
代码语言：javascript复制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
}案例
击鼓传花
队列实现
代码语言：javascript复制// 击鼓传花，给定一个数比如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）的行为特征
实现
代码语言：javascript复制// 优先级队列
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)
