622. 設計循環隊列

思路

建立兩個變數left，right，
加入資料就加到right所在的位置，讀資料則是left。處理完之後將變數+1。
主要關鍵在模運算來讓左指針重新回到起點。

變數limit以其size則是用來紀錄可以存放的數字上限，以及當前 queue 的大小。

程式碼

數組

class MyCircularQueue {
private:
    int left, right, limit, size;
    vector<int> nums;
public:
    MyCircularQueue(int k): left(0), right(0), size(0), limit(k) {
        nums.resize(k);
    }
    
    bool enQueue(int value) {
        if(isFull()) {
            return false;
        }
        else {
            nums[right] = value;
            right = (right + 1) % limit;
            ++size;
            return true;
        }
    }
    
    bool deQueue() {
        if(isEmpty()) {
            return false;
        }
        else {
            left = (left + 1) % limit;
            --size;
            return true;
        }
    }
    
    int Front() {
        if(isEmpty()) {
            return -1;
        }
        return nums[left];
    }
    
    int Rear() {
        if(isEmpty()) {
            return -1;
        }
        else {
            // 需要注意的是，right 當下的位置是要放數字的
            // right - 1 才是最後一個加入的數字。
            return nums[right == 0 ? limit - 1 : right - 1];
        }
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    bool isFull() {
        return size == limit;
    }
};

複雜度分析

• 時間複雜度：$O(1)$
• 空間複雜度：$O(k)$