链表队列

实现

构造器

var MyCircularQueue = function(k) {
    this.head=null;
    this.tail=null;
    this.length=0;
    this.capacity=k;
};

添加元素

MyCircularQueue.prototype.enQueue = function(value) {
    if(this.length==this.capacity){
        return false;
    }
    if(!this.head){
        this.head=this.tail=new Node(value);
    }else{
        this.tail.next=new Node(value);
        this.tail=this.tail.next;
    }
    this.length++;
    return true;
};

删除元素

MyCircularQueue.prototype.deQueue = function() {
    if(this.length==0){
        return false;
    }
    this.head=this.head.next;
    this.length--;
    return true;
};

从队首获取元素

MyCircularQueue.prototype.Front = function() {
    if(this.length==0){
        return -1;
    }
    return this.head.value;
};

从队尾获取元素

MyCircularQueue.prototype.Rear = function() {
    if(this.length==0){
        return -1;
    }
    return this.tail.value;
};

队列是否为空

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

队列是否已满

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

完整代码

function Node(value){
    this.value=value;
    this.next=null;
}
var MyCircularQueue = function(k) {
    this.head=null;
    this.tail=null;
    this.length=0;
    this.capacity=k;
};

MyCircularQueue.prototype.enQueue = function(value) {
    if(this.length==this.capacity){
        return false;
    }
    if(!this.head){
        this.head=this.tail=new Node(value);
    }else{
        this.tail.next=new Node(value);
        this.tail=this.tail.next;
    }
    this.length++;
    return true;
};

MyCircularQueue.prototype.deQueue = function() {
    if(this.length==0){
        return false;
    }
    this.head=this.head.next;
    this.length--;
    return true;
};

MyCircularQueue.prototype.Front = function() {
    if(this.length==0){
        return -1;
    }
    return this.head.value;
};

MyCircularQueue.prototype.Rear = function() {
    if(this.length==0){
        return -1;
    }
    return this.tail.value;
};

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

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

性能分析:

时间复杂度：O(1)，所有方法都具有恒定的时间复杂度。

空间复杂度：O(N)，与数组实现相同。但是单链表实现f方式的内存效率更高。