数据结构-队列结构

package com.s4.queue;
public interface IQueue {
    // 队列的已用长度
    public abstract int getLength();
    // 队列的预设长度
    public abstract int getPresetLength();
    // 入队操作
    public abstract boolean enqueue(Object value);
    public abstract boolean isEmpty();
    public abstract boolean isFull();
    // 出队操作，复杂度是 O(1)
    public abstract Object dequeue();
}

/*
     * 入队操作: 这个是优化后的方案。入队操作的时间复杂度还是 O(1)
     */
    @Override
    public boolean enqueue(Object value) {
        if (this.isFull()) {
            if (this.head == 0) {
                return false;
            }
            // 进行迁移[head, tail) 左移 head 位
            for (int i = this.head; i < this.tail; i++) {
                this.datas[i - this.head] = this.datas[i];
            }
            // 搬移完之后更新 head 和 tail
            this.tail -= this.head;
            this.head = 0;
        }
        this.datas[this.tail] = value;
        this.tail++;
        return true;
    }
    // 入队操作: 这是一个错误示例，一个较差的方法
    public boolean enqueueBad(Object value) {
        if (this.isFull()) {
            return false;
        }
        this.datas[this.tail] = value;
        this.tail++;
        return true;
    }
    /*
     * 出队操作，复杂度是 O(1)
     */
    @Override
    public Object dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        Object ret = this.datas[this.head];
        this.head++;
        return ret;
    }
    // 每次出队都会迁移，会增加时间复杂度为O(n)，因此不推荐这么做
    @Deprecated
    public Object dequeue2() {
        if (this.isEmpty()) {
            return null;
        }
        // 每次进行出队操作都相当于删除数组下标为 0 的数据
        Object ret = this.datas[0];
        // [1, tail -1] 整体左移一位 [1, tail) | [0, tail - 1)
        for (int i = 0; i < tail - 1; i++) {
            this.datas[i] = this.datas[i + 1];
        }
        this.tail--;
        this.datas[this.tail] = null;
        return ret;
    }
}

// 入队操作
    public boolean enqueue(Object value) {
        if (this.isFull()) {
            return false;
        }
        Node node = new Node();
        node.data = value;
        node.next = null;
        if (this.isEmpty()) {
            this.head = node;
        } else {
            this.tail.next = node;
        }
        this.tail = node;
        this.length++;
        return true;
    }
    // 出队操作，复杂度是 O(1)
    public Object dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        Node nextNode = this.head.next;
        Object ret = this.head.data;
        this.head.data = null;
        this.head.next = null;
        this.head = nextNode;
        if (nextNode == null) {
            this.tail = null;
        }
        this.length--;
        return ret;
    }

/*
     * 入队
     */
    @Override
    public boolean enqueue(Object value) {
        if (this.isFull()) {
            return false;
        }
        this.datas[this.tail] = value;
        this.tail = indexPlus(this.tail);
        return true;
    }
    /*
     * 出队，复杂度是 O(1)
     */
    @Override
    public Object dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        Object ret = this.datas[this.head];
        this.head = this.indexPlus(this.head);
        return ret;
    }