讨论/技术交流/循环队列的优劣比较/
循环队列的优劣比较

那么问题来了:循环队列两种写法(1)数组实现(2)链表实现;
空间复杂度:数组比链表小
时间复杂度:
添加:数组操作下标直接赋值,O(1);链表也是O(1)
删除:都是逻辑删除,改变头head位置O(1)
哪种更好?

再者是否可以延伸出ArrayDeque和LinkedList的区别?
但是我看ArrayDeque的源码中没有进行循环,而是将头元素置为null,那岂不是普通数组队列了吗,形成伪满队列,后面满前面空?

求解释,欢迎交流

方法一:单链表实现

class MyCircularQueue {
    private int length;//队列的长度
    //private ListNode node;//队列的数据存储结构
    ListNode head;//队列头
    ListNode tail;//队列尾
    private int fealLen;

    public MyCircularQueue(int k) {
        length = k;
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        if (isEmpty()) {
            ListNode tmp = new ListNode(value);
            head = tmp;
            tail = tmp;
        } else {
            if (tail.next == null) {
                tail.next = new ListNode(value);
            } else {
                tail.next.val = value;
            }
            tail = tail.next;
            if (fealLen == length - 1) {
                tail.next = head;
            }
        }
        fealLen++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        if (head == tail) {
            fealLen--;
            return true;
        }
        head = head.next;
        fealLen--;
        return true;
    }

    public int Front() {
        if (isEmpty()) return -1;
        return head.val;
    }

    public int Rear() {
        if (isEmpty()) return -1;
        return tail.val;
    }

    public boolean isEmpty() {
        if (fealLen == 0) return true;
        return false;
    }

    public boolean isFull() {
        if (fealLen == length) return true;
        return false;
    }
}

方法二:动态数组实现

class MyCircularQueue {
    private int length;//队列的长度
    private int[] ints;//队列的数据存储结构
    int head;//队列头
    int tail;//队列尾

    public MyCircularQueue(int k) {
        ints = new int[k];
        head = -1;
        tail = -1;
        length = k;
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        if (isEmpty()) head++;
        ints[(tail + 1) % length] = value;
        tail = (tail + 1) % length;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % length;
        return true;
    }

    public int Front() {
        if (isEmpty()) return -1;
        return ints[head];
    }

    public int Rear() {
        if (isEmpty()) return -1;
        return ints[tail];
    }

    public boolean isEmpty() {
        if (head == -1 && tail == -1) return true;
        return false;
    }

    public boolean isFull() {
        //尾的下一个元素是头
        if ((tail + 1) % length == head) return true;
        return false;
    }
}

1
共 0 个回复
暂无回复