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);

JavaScript数据结构，队列和栈

栈

队列

推荐阅读