赞
踩
队列是一种列表,用于存储按顺序排列的数据。
先进先出。在一端进行插入,在另外一端进行删除。插入的一端称为队尾,删除的一端称为队头,先进队列的元素优先处理。
可以将队列想象成排队的人群。队列用在很多地方,例如:提交操作系统执行的一系列操作等等。
队列没有自定义属性,通常用数组来模拟队列,直接使用的是数组的一些属性,比如length等。
/** * 队列构造函数 */ function Queue() { /** * 用数组来模拟队列 * @type {Array} */ var items = []; /** * 将元素推入队列 * @param {Any} ele 要推入队列的元素 */ this.enqueue = function(ele) { items.push(ele); }; /** * 将队列中第一个元素弹出 * @return {Any} 返回被弹出的元素 */ this.dequeue = function() { return items.shift() //shift()删除数组的第一个元素 }; /** * 查看队列的第一个元素 * @return {Any} 返回队列中第一个元素 */ this.front = function() { return items[0]; }; /** * 确定队列是否为空 * @return {Boolean} 若队列为空则返回true,不为空则返回false */ this.isAmpty = function() { return items.length === 0 }; /** * 返回队列的长度 * @return {Number} 队列的长度 */ this.size = function() { return items.length; }; /** * 清空队列中所有内容 */ this.clear = function() { items = []; }; /** * 以字符串显示队列中所有内容 */ this.print = function() { console.log(items.toString()); }; } /** * 击鼓传花的小游戏 * @param {Array} nameList 参与人员列表 * @param {Number} num 在循环中要被弹出的位置 * @return {String} 返回赢家(也就是最后活下来的那个) */ function hotPotato(nameList, num) { var queue = new Queue(); for (var i = 0; i < nameList.length; i++) { queue.enqueue(nameList[i]); } var eliminated = ''; while (queue.size() > 1) { for (var i = 0; i < num; i++) { queue.enqueue(queue.dequeue()); } eliminated = queue.dequeue(); console.log(eliminated + " Get out!") } return queue.dequeue() } var nameList = ['小明', '小红', '小王', '小强'] hotPotato(nameList,5);
栈是一种高效的数据结构,因为数据只能在一端(栈顶)进行添加或删除,所以这样的操作很快。
栈是一种很特殊的列表。
先进后出,栈内元素只能通过列表的一端访问,这一端称为栈顶。
栈可以进行:
(1)进制间的相互转换
(2)回文:将字符串的每个字符按从左至右的顺序压入栈
。 当字符串中的字符都入栈后,原来字符串尾部就在栈顶,字符串第一个字符在栈顶, 栈内就保存了一个反转后的字符串
。 通过持续弹出栈中的每个字母
就可以得到一个新字符串, 该字符串刚好是原来的字符串的逆序。 我们只需要比较这两个字符串即可, 如果它们相等
, 就是一个回文。
** * 栈的构造函数 */ function Stack() { /** * 用数组来模拟栈 * @type {Array} */ var items = []; /** * 将元素送入栈,放置于数组的最后一位 * @param {Any} element 接受的元素,不限制类型 */ this.push = function(element) { items.push(element); }; /** * 弹出栈顶元素 * @return {Any} 返回被弹出的值 */ this.pop = function() { return items.pop(); //返回的是被弹出来的值 }; /** * 查看栈顶元素 * @return {Any} 返回栈顶元素 */ this.peek = function() { return items[items.length - 1]; //栈是后进先出,后面进去的是栈顶,这是栈顶元素 } /** * 确定栈是否为空(用于判断) * @return {Boolean} 若栈为空则返回true,不为空则返回false */ this.isAmpty = function() { return items.length === 0 }; /** * 清空栈中所有内容 */ this.clear = function() { items = []; }; /** * 返回栈的长度 * @return {Number} 栈的长度 */ this.size = function() { return items.length; }; /** * 以字符串显示栈中所有内容 */ this.print = function() { console.log(items.toString()); }; } /** * 将10进制数字转为2进制数字 * 原理就是输入要转换的数字,不断的除以二并取整。并且最后运用while循环,将栈中所有数字拼接成字符串输出。 * @param {Number} decNumber 要转换的10进制数字 * @return {Number} 转换后的2进制数字 */ function divideBy2(decNumber) { var remStack = new Stack(), //声明一个新的栈 rem, //表示数字除以2以后的余数 binaryString = ''; while (decNumber > 0) { rem = Math.floor(decNumber % 2); remStack.push(rem); //将余数放入栈中 decNumber = Math.floor(decNumber / 2); //数字每取一次余数,就要除以2 } //最后得到的栈是:第一个余数去到栈底,最后一个余数在栈顶 //然后出栈,就能得到依次余数的逆序,就能得到求得的二进制数 while (!remStack.isAmpty()) { binaryString += remStack.pop().toString(); } return binaryString; }; console.log(divideBy2(10));
补充内容:
列表是一组有序的数据,列表中的每个数据项称为元素。
在 JavaScript 中, 列表中的元素可以是任意数据类型。 列表中可以保存多少元素并没有事先限定,实际中受内存限制。
length
:返回列表中元素的个数append()
:在列表末尾添加新的元素listToString()
: 返回列表的字符串形式getElement()
:返回当前位置的元素find()
:查找给定的元素,如果找到就返回元素的对应下标(元素在列表中的位置),如果没有找到就返回-1.remove()
:删除列表元素contains()
:判断元素是否存在于列表中clear()
:清空列表中所有元素Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。