顺序队列和链式队列 和 环的实现

顺序队列和链式队列 和 环的实现

• 顺序队列
• 循环队列

---

Java中用数组实现的就叫顺序队列，用链表实现的就叫链式队列。

顺序队列

public class ArrayQueue {
    // 数组：items，数组大小：n
    private String[] items;
    private int n = 0;
    // head 表示队头下标，tail 表示队尾下标
    private int head = 0;
    private int tail = 0;

    // 申请一个大小为 capacity 的数组
    public ArrayQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }

    // 入队 *** 作，将 item 放入队尾
    public boolean enqueue(String item) {
        // tail == n 表示队列末尾没有空间了
        if (tail == n) {
            // tail ==n && head==0，表示整个队列都占满了
            if (head == 0) return false;
            // 数据搬移
            for (int i = head; i < tail; ++i) {
                items[i - head] = items[i];
            }
            // 搬移完之后重新更新 head 和 tail
            tail -= head;
            head = 0;
        }
        items[tail] = item;
        ++tail;
        return true;
    }

    // 出队
    public String dequeue() {
        // 如果 head == tail 表示队列为空
        if (head == tail) return null;
        // 为了让其他语言的同学看的更加明确，把 --  *** 作放到单独一行来写了
        String ret = items[head];
        ++head;
        return ret;
    }
}

• 使用数组制作队列的时候，主要是使用首尾指针进行标记，队头队尾。
• 出队的时候始终为n(1)，入队的时候当尾部指针数组后续未满时，入队为N(1),当尾部数组指向最后一个索引的时候，数组整体迁移到数组索引第一个位置。当发生数据迁移的时候时间复杂度为o(n)，
• 这样会大大的节省入队的时候，每次都需要发生数据迁移的时间浪费。

循环队列

循环队列的难度会直线上升，主要把握好队空和队满的判定条件。

public class CircularQueue {
    // 数组：items，数组大小：n
    private String[] items;
    private int n = 0;
    // head 表示队头下标，tail 表示队尾下标
    private int head = 0;
    private int tail = 0;

    // 申请一个大小为 capacity 的数组
    public CircularQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }

    // 入队
    public boolean enqueue(String item) {
        // 队列满了
        if ((tail + 1) % n == head) return false;
        items[tail] = item;
        tail = (tail + 1) % n;
        return true;
    }

    // 出队
    public String dequeue() {
        // 如果 head == tail 表示队列为空
        if (head == tail) return null;
        String ret = items[head];
        head = (head + 1) % n;
        return ret;
    }
}

如有错误欢迎指正