循环队列

循环队列定义

• 为充分利用向量空间，将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

• 在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。 循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

• 可以使用数组或链表模拟循环队列；

使用数组模拟

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=rear，而队列判满的条件是front = (rear+1)%MaxSize。

class MyCircularQueue {
private:
    int front;  // 队头元素下标
    int back;   // 队尾元素的后面一个的下标
    int capcity;
    vector<int> vec;
public:
    MyCircularQueue(int k) {
        // 当循环队列中只剩下一个空存储单元时，则表示队列已满，所以数组容量为k+1
        capcity = k + 1;
        front = back = 0;
        vec.resize(capcity);
    }
    
    bool enQueue(int value) {
        if (isFull()) return false;
        vec[back] = value;
        back = (back + 1) % capcity;
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % capcity;
        return true;
    }
    
    int Front() {
        if (isEmpty()) return -1;
        return vec[front];
    }
    
    int Rear() {
        if (isEmpty()) return -1;
        int rear = (back - 1 + capcity) % capcity;
        return vec[rear];
    }
    
    bool isEmpty() {
        return front == back;
    }
    
    bool isFull() {
        return front == (back + 1) % capcity;
    }

    // size = (back - front + capacity) % capacity;
};

使用链表模拟

用链表实现队列则较为简单，因为链表可以在 O(1)时间复杂度完成插入与删除。入队列时，将新的元素插入到链表的尾部；出队列时，将链表的头节点返回，并将头节点指向下一个节点。

class MyCircularQueue {
private:
    ListNode *head;
    ListNode *tail;
    int capacity;
    int size;

public:
    MyCircularQueue(int k) {
        this->capacity = k;
        this->size = 0;
        this->head = this->tail = nullptr;
    }

    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        ListNode *node = new ListNode(value);
        if (!head) {
            head = tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
        size++;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        ListNode *node = head;
        head = head->next;  
        size--;
        delete node;
        return true;
    }

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

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

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }
};

笔者最开始使用链表是一次性在构造函数中申请k个节点的空间，结束时再析构函数释放资源，这样就不用动态申请了，但发现速度要慢一些，并且代码更复杂，如下：

struct Node {
    int val;
    Node* next;
    Node(int _val) : val(_val), next(nullptr) {}
    Node(int _val, Node* _next) : val(_val), next(_next) {}
};

class MyCircularQueue {
private:
    Node* dummyHead;
    int size;
    int capcity;
    Node* lastNode;
public:
    MyCircularQueue(int k) {
        capcity = k;
        size = 0;
        // 虚拟头节点
        dummyHead = new Node(-1);
        // 一次性申请k个节点的空间
        Node* cur = dummyHead;
        for (int i = 0; i < capcity; ++i) {
            Node* node = new Node(-1);
            cur->next = node;
            cur = node;
        }
        // 最后一个有效数据的节点，相当于队尾元素
        lastNode = dummyHead;
    }

    ~MyCircularQueue() {
        Node* cur = dummyHead;
        for (int i = 0; i < capcity + 1; ++i) {
            Node* tmp = cur;
            cur = cur->next;
            delete tmp;
        }
    }
    
    bool enQueue(int value) {
        if (isFull()) return false;
        
        // 保证尾节点不为空且空闲；
        // 队尾后移，然后辅助队尾元素，相当于从队尾插入
        lastNode = lastNode->next;
        lastNode->val = value;
        
        ++size;
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) return false;
        // 只有一个有效元素时要单独处理
        if (size == 1) {
            lastNode->val = -1;
            lastNode = dummyHead;
            --size;
            return true;
        }
        // 队头元素就是要删除的元素
        Node* toBeDel = dummyHead->next;
        toBeDel->val = -1;
        // 更新队头元素
        dummyHead->next = toBeDel->next;
        // 空闲节点的开头处
        Node* freeBegin = lastNode->next;
        // 将队头元素移动到队尾后面，就是改变指针指向
        lastNode->next = toBeDel;
        toBeDel->next = freeBegin;
        
        --size;
        return true;
    }
    
    int Front() {
        if (isEmpty()) return -1;
        return dummyHead->next->val;
    }
    
    int Rear() {
        if (isEmpty()) return -1;
        return lastNode->val;
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    bool isFull() {
        return size == capcity;
    }
};

循环双端队列

2022-8-15 更新，其实和上述的差不多，无非是多了一个端口；

class MyCircularDeque {
private:
    int capacity_;
    int front_;
    int back_;
    vector<int> vec_;

    int next(int idx) {
        return (idx + 1) % capacity_;
    }
    int prev(int idx) {
        return (idx - 1 + capacity_) % capacity_;
    }
public:
    MyCircularDeque(int k) {
        capacity_ = k + 1;
        front_ = back_ = 0;
        vec_.resize(capacity_);
    }
    
    bool insertFront(int value) {
        if (isFull()) return false;
        front_ = prev(front_);
        vec_[front_] = value;
        return true;
    }
    
    bool insertLast(int value) {
        if (isFull()) return false;
        vec_[back_] = value;
        back_ = next(back_);
        return true;
    }
    
    bool deleteFront() {
        if (isEmpty()) return false;
        front_ = next(front_);
        return true;
    }
    
    bool deleteLast() {
        if (isEmpty()) return false;
        back_ = prev(back_);
        return true;
    }
    
    int getFront() {
        if (isEmpty()) return -1;
        return vec_[front_];
    }
    
    int getRear() {
        if (isEmpty()) return -1;
        return vec_[prev(back_)];
    }
    
    bool isEmpty() {
        return front_ == back_;
    }
    
    bool isFull() {
        return front_ == next(back_);
    }
};

【参考资料】力扣题解、百度百科