JavaScript数据结构6——循环队列和链式队列

循环队列

//循环队列
function Queue(maxSize) {
    this.data = new Array(maxSize);
    this.front = 0;//头指针
    this.rear = 0;//尾指针
    this.maxSize = maxSize;
}
//长度
Queue.prototype.length = function(){
    return (this.rear-this.front+this.maxSize)%this.maxSize;
}
Queue.prototype.enterQueue = function(data){
    if((this.rear+1)%this.maxSize==this.front){
        //满
        return 1;
    }
    this.data[this.rear] = data;
    this.rear = (this.rear+1)%this.maxSize;
    return 0;
}
Queue.prototype.deleteQueue = function(){
    if(this.front == this.rear){
        //空
        return 1;
    }
    this.front = (this.front+1)%this.maxSize;
    return 0;
}
var que = new Queue(10);
que.enterQueue(1);
que.enterQueue(2);
que.enterQueue(3);
que.deleteQueue();
console.info(que.length());

结果:

2

链式队列

//节点
function Node(data){
    this.data = data;
}
function Queue() {
    var node = new Node(null);
    this.front = node;
    this.rear = node;
}
//长度
Queue.prototype.length = function(){
    var length = 0;
    var node = this.front;
    while(node!=this.rear){
        node = node.next;
        length++;
    }
    return length;
}
Queue.prototype.enterQueue = function(node){
    node.next = null;
    this.rear.next = node;
    this.rear = node;
    return 0;
}
Queue.prototype.deleteQueue = function(){
    var p = this.front.next;
    if(this.rear == this.front){
        return 1;
    }
    this.front.next = p.next;
    if(this.rear == p){
        this.rear = this.front;
    }
    delete p;
}
var que = new Queue(10);
que.enterQueue(new Node(1));
que.enterQueue(new Node(2));
que.deleteQueue();
console.info(que.length());

输出

1