队列
队列和双端队列
队列遵循先进后出(FIFO, 也称为先来先服务) 原则的. 日常有很多这样场景: 排队购票、银行排队等.
由对列的特性,银行排队为例, 队列应该包含如下基本操作:
class Queue { constructor() { // 队列长度, 类数组 length this.count = 0 // 队列中所有项 this.items = {} // 记录对列头, 类数组 index this.lowestCount = 0 } enqueue(ele) { this.items[this.count++] = ele } dequeue() { if (this.isEnpty()) { return undefined } const ele = this.items[this.lowestCount] delete this.items[this.lowestCount] this.lowestCount++ return ele } peek() { if (this.isEnpty()) { return } return this.items[this.lowestCount] } size() { /** * 当队列为非空时: * 1. count 是长度 * 2. lowestCount 是下标 * 两者关系应该 lowestCount = count - 1 */ return this.count - this.lowestCount } isEnpty() { return this.size() == 0 } clear() { this.items = {} this.lowestCount = 0 this.count = 0 } toString() { if (this.isEnpty()) { return '' } let objString = `${this.items[this.lowestCount]}` for (let i = this.lowestCount + 1; i < this.count; i++) { objString = `${objString}, ${this.items[i]}` } return objString } }
双端队列(deque 或 double-ended queue)
什么是双端队列?
允许从前端(front)和后端(rear)添加元素, 遵循的原则先进先出或后进先出.
双端队列可以理解为就是栈(后进先出)和队列(先进先出)的一种结合体. 既然是结合那么相应的操作也支持队列,栈的操作. 下面我们定义一个Deque
constructor() { this.items = {} this.count = 0 this.lowestCount = 0 } addFront(ele) { if (this.isEmpty()) { this.items[this.count] = ele } else if (this.lowestCount > 0) { this.lowestCount -= 1 this.items[this.lowestCount] = ele } else { for (let i = this.count; i > 0; i--) { this.items[i] = this.items[i - 1] } this.items[0] = ele } this.count++ return ele } removeFront() { if (this.isEmpty()) { return } const delEle = this.items[this.lowestCount] delete this.items[this.lowestCount] this.lowestCount++ return delEle } addBack(ele) { this.items[this.count] = ele this.count++ } removeBack() { if (this.isEmpty()) { return } const delEle = this.items[this.count - 1] delete this.items[this.count - 1] this.count-- return delEle } peekFront() { if (this.isEmpty()) { return } return this.items[this.lowestCount] } peekBack() { if (this.isEmpty()) { return } return this.items[this.count - 1] } size() { return this.count - this.lowestCount } isEmpty() { return this.size() === 0 } clear() { this.items = {} this.count = 0 this.lowestCount = 0 } toString() { if (this.isEmpty()) { return '' } let objString = `${this.items[this.lowestCount]}` for (let i = this.lowestCount + 1; i < this.count; i++){ objString = `${objString}, ${this.items[i]}` } return objString } }
队列的应用
击鼓传花游戏
击鼓传花游戏: 简单描述就是一群人围成一个圈传递花,喊停的时花在谁手上就将被淘汰(每个人都可能在前端,每个参与者在队列位置会不断变化),最后只剩下一个时就是赢者. 更加详细可以自行查阅.
下面通过代码实现:
function hotPotato(elementsList, num) { // 创建一个容器 const queue = new Queue() const elimitatedList = [] // 把元素(参赛者)加入队列中 for (let i = 0, len = elementsList.length; i < len; i++) { queue.enqueue(elementsList[i]) } /** * 击鼓传花 * 首先队列规则: 先进先出 * 那么在传花过程中,任何一个元素都可能是前端, 在传花的过程中应该就是前端位置不断变化. * 当喊停的时(num 循环完), 也就是花落在谁手(谁在前端)则会被淘汰*(移除队列) */ while (queue.size() > 1) { for (let j = 0; j < num; j++) { queue.enqueue(queue.dequeue()) } elimitatedList.push(queue.dequeue()) } return { winer: queue.dequeue(), elimitatedList } }
代码运行如下:
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // { winer: 5, elimitatedList: [4, 8, 2, 7, 3,10, 9, 1, 6]} console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // { winer: 5, elimitatedList: [4, 8, 2, 7, 3,10, 9, 1, 6]} console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // { winer: 8, elimitatedList: [10, 1, 3, 6, 2,9, 5, 7, 4]}
判断回文
上一篇栈中也有涉及回文的实现, 下面我们通过双端队列来实现同样的功能.
function palindromeChecker(aString) { if (!aString || typeof aString !== 'string' || !aString.trim().length) { return false } const deque = new Deque() const lowerString = aString.toLowerCase().split(' ').join('') // 加入队列 for (let i = 0; i < lowerString.length; i++) { deque.addBack(lowerString[i]) } let isEqual = true let firstChar = '' let lastChar = '' while (deque.size() > 1 && isEqual) { firstChar = deque.removeFront() lastChar = deque.removeBack() if (firstChar != lastChar) { isEqual = false } } return isEqual }
下面通过代码演示下:
console.log(palindromeChecker('abcba')) // true 当前为回文
生成 1 到 n 的二进制数
function generatePrintBinary(n) { var q = new Queue() q.enqueue('1') while (n-- > 0) { var s1 = q.peek() q.dequeue() console.log(s1) var s2 = s1 q.enqueue(s1 + '0') q.enqueue(s2 + '1') } } generatePrintBinary(5) // => 1 10 11 100 101
到此这篇关于JS中队列和双端队列实现及应用详解的文章就介绍到这了,更多相关JS 双端队列 内容请搜索小牛知识库以前的文章或继续浏览下面的相关文章希望大家以后多多支持小牛知识库!
queue 在java5中新增加了java.util.Queue接口,用以支持队列的常见操作。该接口扩展了java.util.Collection接口。除了基本的 Collection 操作外,队列还提供其他的插入、提取和检查操作。 每个方法都存在两种形式:一种抛出异常(操作失败时),另一种返回一个特殊值(null 或 false,具体取决于操作)。 抛出异常 返回特殊值 插入 add
主要内容:顺序队列简单实现,顺序队列另一种实现方法顺序队列 ,即采用顺序表模拟实现的队列结构。 我们知道,队列具有以下两个特点: 数据从队列的一端进,另一端出; 数据的入队和出队遵循"先进先出"的原则; 因此,只要使用顺序表按以上两个要求操作数据,即可实现顺序队列。首先来学习一种最简单的实现方法。 顺序队列简单实现 由于顺序队列的底层使用的是数组,因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外,为了满足顺序队列中数据从队尾进,队头出且
本文向大家介绍PHP消息队列实现及应用详解【队列处理订单系统和配送系统】,包括了PHP消息队列实现及应用详解【队列处理订单系统和配送系统】的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了PHP消息队列实现及应用。分享给大家供大家参考,具体如下: 在互联网项目开发者经常会遇到『给用户群发短信』、『订单系统有大量的日志需要记录』或者在秒杀业务的时候服务器无法承受瞬间并发的压力。 这种情况下,我
问题内容: 抱歉,下面是我在这里遇到的一个问题:在这里,我试图运行此方法以从双面队列(双端队列)中删除通用值(EltType),但是我一直遇到错误,我两次调用insertFirst ,然后将值“ 3”插入数组两次,然后,当我运行removeFirst时,它将打印出“ 3”一次,然后打印出“ Null”。有人可以帮我吗? 谢谢 :) 问题答案: 明显的问题是它永远不会改变。 将永远返回。现在,让我们
本文向大家介绍C ++程序在STL中实现双端队列,包括了C ++程序在STL中实现双端队列的使用技巧和注意事项,需要的朋友参考一下 双端队列是一种队列数据结构,其中在两端(前端和后端)都执行插入和删除操作。可以在前后位置插入数据,也可以从前后位置删除数据。 算法 范例程式码 输出结果
双端队列(Double-ended Queue) 注:队列是一种只允许在一端删除而在另一端插入的数据结构。双端队列(Deque)是队列的一种拓展,它可以在队列的两端进行插入和删除。 1. 双端队列(Deque)的概念 1.1 双端队列的定义 双端队列是限定插入和删除操作在表的两端进行的线性表,是一种具有队列和栈的性质的数据结构。 1.2 双端队列的特点 双端队列中的元素可以从两端进队和出队,其限定