题目链接:https://leetcode.cn/problems/design-circular-queue/

题目难度:中等

题意

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

你的实现应该支持如下操作:

  • MyCircularQueue(k): 构造器,设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空,返回 -1 。
  • Rear: 获取队尾元素。如果队列为空,返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

示例 :

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false,队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4

提示:

  • 所有的值都在 0 至 1000 的范围内;
  • 操作数将在 1 至 1000 的范围内;
  • 请不要使用内置的队列库。

题解:模拟

题意非常明了,直接使用数组模拟循环队列即可。

先初始化队头head,队尾rear,head=rear=0;

  • 判断队列为空:head==rear&&a[head]==-1
  • 判断队列已满:(head==1&&rear==n&&a[head]==-1)||(head-rear)==1
  • 插入队列:队列为空时需要特判下
  • 删除队列:删除后若队列为空需要特判下

C++代码:

class MyCircularQueue {
public:
    int head,rear,n;
    int a[1005];
    MyCircularQueue(int k) {
        for(int i=0;i<=k;i++) a[i]=-1;
        head=0;rear=0;n=k;
    }
  
    bool enQueue(int value) {
        if(isFull()) return false;
        if(head==0) head=1;
        if(head==rear&&a[head]==-1){
            a[rear]=value;return true;
        }
        ++rear;
        if(rear>n) rear%=n;
        a[rear]=value;
        return true;
    }
  
    bool deQueue() {
        if(isEmpty()) return false;
        if(head==rear){
            a[head]=-1;return true;
        }
        a[head]=-1;head++;
        if(head>n) head%=n;
        return true;
    }
  
    int Front() {
        return a[head];
    }
  
    int Rear() {
        return a[rear];
    }
  
    bool isEmpty() {
        // cout<<a[head]<<endl;
        if(head==rear&&a[head]==-1) return true;
        return false;
    }
  
    bool isFull() {
        // cout<<head<<"---"<<rear<<endl;
        if((head==1&&rear==n&&a[head]!=-1)||head-rear==1){
            return true;
        }
        return false;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

官方题解

https://leetcode.cn/problems/design-circular-queue/solution/she-ji-xun-huan-dui-lie-by-leetcode-solu-1w0a/

class MyCircularQueue {
public:
    int front,rear,n;
    int a[1005];
    MyCircularQueue(int k) {
        front=rear=0;
        n=k+1;
    }
  
    bool enQueue(int value) {
        if(isFull()) return false;
        a[rear]= value;
        rear = (rear+1)%n;
        return true;
    }
  
    bool deQueue() {
        if(isEmpty()) return false;
        front = (front+1)%n;
        return true;
    }
  
    int Front() {
        if(isEmpty()) return -1;
        return a[front];
    }
  
    int Rear() {
        if(isEmpty()) return -1;
        return a[(rear-1+n)%n];
    }
  
    bool isEmpty() {
        // cout<<a[head]<<endl;
        if(front == rear) return true;
        return false;
    }
  
    bool isFull() {
        // cout<<head<<"---"<<rear<<endl;
        if((rear+1)%n == front) return true;
        return false;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */