你的位置:首页 > Java教程

[Java教程]JavaScript数据结构,队列和栈


在JavaScript中为数组封装了大量的方法,比如:concat,pop,push,unshift,shift,forEach等,下面我将使用JavaScript提供的这些方法,实现队列和栈的操作。

栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。

我们先创建一个表示栈的类,类名为Stock,其实这就是一个函数,在这个函数中有一个数组,这个数组用于保存栈中的数据,除了需要一个保存数据的数组之外,还需要一些对这个数组进行操作的方法,方法介绍如下:

isEmpty:判断栈是否为空

push:添加一个或者多个新的数据到栈顶

pop:移除栈顶的数据,并返回被移除的数据

size:得到栈中数据的个数

clear:清除栈中的所有数据

peek:得到栈顶的数据,但不移除

Stock类具体实现如下:

/** * 栈类 * @constructor */function Stock() {  //保存栈中的数据  this.items = [];}/** * 判断是否栈中数据为空 */Stock.prototype.isEmpty = function(){  return this.items.length === 0;};/** * 向栈顶添加一个或多个新数据 * @param elements 要添加的新数据 */Stock.prototype.push = function(elements){  this.items.push(elements);};/** * 移除栈顶的数据,并返回移除的数据 */Stock.prototype.pop = function(){  return this.items.pop();};/** * 得到栈中数据的个数 * @returns {Number} */Stock.prototype.size = function(){  return this.items.length;};/** * 得到栈顶的数据,但不移除数据 */Stock.prototype.peek = function(){  return this.items[this.items.length - 1];};
/** * 清空栈中的数据 */Stock.prototype.clear = function(){  this.items.length = 0;};


使用stock类

/** * 将十进制转换为二进制 * @param number */function divideBy2(number){  var stockObj = new Stock();  var binaryStr = '';  if(number === 0){    stockObj.push(number);  }else {    while (number > 0) {      var rem = number % 2;      stockObj.push(rem);      number = number / 2 | 0;    }  }  while(!stockObj.isEmpty()){    binaryStr+= stockObj.pop();  }  return binaryStr;}//将十进制8转换为二进制divideBy2(8);

队列

队列是遵循FIFO(First In First Out,先进先出,也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。

先创建一个表示队列的类,类名为Queue,与Stock类类似,也有一个表示队列中数据的数组,还有一些对数据进行操作的方法,方法的描述如下:

enqueue:向队列尾部添加一个或者多个新数据

dequeue:从队列头部移除一个数据

clear:清空队列

size:得到队列数据的个数

isEmpty:判断队列是否为空

front:得到对头的数据

Queue类具体实现如下:

/** * 队列类 * @constructor */function Queue(){  //保存队列中的数据  this.items = [];}/** * 向队尾添加一个或多个新数据 * @param elements 添加的数据 */Queue.prototype.enqueue = function(elements){  this.items.push(elements);};/** * 移除队头的数据,并返回 */Queue.prototype.dequeue = function(){  return this.items.shift();};/** * 清空队列 */Queue.prototype.clear = function(){  this.items.length = 0;};/** *返回队列中数据的长度 */Queue.prototype.size = function(){  return this.items.length;};/** * 返回队头的数据,但不移除 */Queue.prototype.front = function(){  return this.items[0];};

 Queue的使用

/** * 模拟击鼓传花 * @param dataList 操作的数据 * @param num 传花的间隔个数 */function hotPotato(dataList,num){  var queueObj = new Queue();  for(var i = 0,len = dataList.length;i<len;ii){    queueObj.enqueue(dataList[i]);  }  while(queueObj.size() === 1){    for(i = 0;i<num;i++){      queueObj.enqueue(queueObj.dequeue());    }    queueObj.dequeue();  }  console.log('取得胜利的是:',queueObj.dequeue());}hotPotato([1,2,3,4,22,5,6,7,8,9],4);