数组队列

实现

构造器

• queue：一个固定大小的数组，用于保存循环队列的元素
• headIndex：一个整数，保存队首 head 的索引。
• count：循环队列当前的长度，即循环队列中的元素数量。使用 hadIndex 和 count 可以计算出队尾元素的索引，因此不需要队尾属性。
• capacity：循环队列的容量，即队列中最多可以容纳的元素数量。

var MyCircularQueue = function(k) {
    this.queue=[];
    this.headIndex=0;
    this.length=0;
    this.capacity=k;
};

添加元素

MyCircularQueue.prototype.enQueue = function(value) {
    if(this.length==this.capacity){
        return false
    }
    this.queue[(this.headIndex+this.length)%this.capacity]=value;
    this.length++;
    return true;
};

删除元素

MyCircularQueue.prototype.deQueue = function() {
    if(this.length==0){
        return false
    }
    this.headIndex=(this.headIndex+1)%this.capacity;
    this.length--;
    return true;
};

从队首获取元素

MyCircularQueue.prototype.Front = function() {
    if(this.length==0){
        return -1
    }
    return this.queue[this.headIndex];
};

从队尾获取元素

思路:对于一个固定大小的数组，任何位置都可以是队首，只要知道队列长度，就可以根据下面公式计算出队尾位置：

• tailIndex=(headIndex+count−1) % capacity

MyCircularQueue.prototype.Rear = function() {
    if(this.length==0){
        return -1
    }
    let tailIndex=(this.headIndex+this.length-1)%this.capacity;
    return this.queue[tailIndex];
};

队列是否为空

MyCircularQueue.prototype.isEmpty = function() {
    return this.length==0;
};

队列是否已满

MyCircularQueue.prototype.isFull = function() {
    return this.length==this.capacity;
};

完整代码

var MyCircularQueue = function(k) {
    this.queue=[];
    this.headIndex=0;
    this.length=0;
    this.capacity=k;
};

MyCircularQueue.prototype.enQueue = function(value) {
    if(this.length==this.capacity){
        return false
    }
    this.queue[(this.headIndex+this.length)%this.capacity]=value;
    this.length++;
    return true;
};

MyCircularQueue.prototype.deQueue = function() {
    if(this.length==0){
        return false
    }
    this.headIndex=(this.headIndex+1)%this.capacity;
    this.length--;
    return true;
};

MyCircularQueue.prototype.Front = function() {
    if(this.length==0){
        return -1
    }
    return this.queue[this.headIndex];
};

MyCircularQueue.prototype.Rear = function() {
    if(this.length==0){
        return -1
    }
    let tailIndex=(this.headIndex+this.length-1)%this.capacity;
    return this.queue[tailIndex];
};

MyCircularQueue.prototype.isEmpty = function() {
    return this.length==0;
};

MyCircularQueue.prototype.isFull = function() {
    return this.length==this.capacity;
};