《学习javascript的数据解构与算法》--笔记--栈与队列的实现

记录的目的是学习一下数据结构和ES6，代码都是根据书中的代码修改的

typescript实现版本

栈

栈是一种遵循后进先出原则的结构。
class Stack {
constructor () {
this.items = []
}

push (element) { this.items.push(element) }

pop () { return this.items.pop() }

peek () { return this.items[this.items.length - 1] }

isEmpty () { return this.items.length === 0 }

size () { return this.items.length }

clear () { this.items = [] }

print () { console.log(this.items.toString()) } }

// 描述把十进制转成其他进制的函数 function baseConverter (decNumber, base) { let remStack = new Stack(), rem, baseString = '', digits = '0123456789ABCDEF'

while (decNumber > 0) { rem = Math.floor(decNumber % base) remStack.push(rem)
decNumber = Math.floor(decNumber / base) }

while (!remStack.isEmpty()) { baseString += digits[remStack.pop()] }

return baseString }

console.log(baseConverter(100345, 2)) // 输出 11000011111111001 console.log(baseConverter(100345, 8)) // 输出 303771 console.log(baseConverter(100345, 16)) // 输出 187F9


## 队列
> 队列遵循先进先出的原则。

class Queue { constructor () { this.items = []
}

enqueue (element) { this.items.push(element) }

dequeue () { return this.items.shift() // 移出数组首位 }

front () { return this.items[0] }

isEmpty () { return this.items.length === 0 }

clear () { this.items = [] }

size () { return this.items.length }

print () { console.log(this.items.toString()) } } const queue = new Queue() queue.enqueue('a') queue.enqueue('b') queue.enqueue('c') console.log(queue.dequeue()) // a console.log(queue.front()) // b queue.print() // b,c queue.size() // 2

### 优先队列
> 给队列的元素添加优先级属性，元素的添加和移出都基于优先级；实例在医院的急诊，医生会优先救治病情严重的患者

// 最小优先队列（就是优先级小的排前面），要实现最大优先队列，改变一下算法就可以了 class PriorityQueue extends Queue { constructor () { super() }

getQueueElement (element, priority) { return { element: element, priority: priority } }

enqueue (element, priority) { const queueElement = this.getQueueElement(element, priority)

this.queueWay(queueElement)

} // 排序方式， priority越大优先级越低 queueWay (queueElement) { if (this.isEmpty()) { this.items.push(queueElement) } else { let added = false

  for (let i = 0; i < this.items.length; i++) {
    if (queueElement.priority < this.items[i].priority) {
      this.items.splice(i, 0, queueElement)
      added = true
      break
    }
  }

  if (!added) {
    this.items.push(queueElement)
  }
}

} }

const priorityQueue = new PriorityQueue() priorityQueue.enqueue('a', 1) priorityQueue.enqueue('b', 2) priorityQueue.enqueue('c', 3) priorityQueue.enqueue('d', 1) priorityQueue.print()

### 循环队列

// 循环队列--击鼓传花 function hotPotato (nameList, num) { const queue = new Queue()

nameList.forEach(val => { queue.enqueue(val) })

while (queue.size() > 1) { // 这个循环，把队头插到队尾 for (let i = 0; i < num; i++) { queue.enqueue(queue.dequeue()) } // 淘汰并宣布淘汰者 console.log(${queue.dequeue()}，在击鼓传花游戏中淘汰) } // 最后的胜利者 return queue.dequeue() } const names = ['a', 'b', 'c', 'd', 'e'] const winner = hotPotato(names, 7) console.log(获胜者：${winner})

lulusir / my-blog

数据结构--笔记--栈与队列的实现 #3

《学习javascript的数据解构与算法》--笔记--栈与队列的实现

记录的目的是学习一下数据结构和ES6，代码都是根据书中的代码修改的

栈