leetcode.622. 设计循环队列(Design Circular Queue)

622. 设计循环队列(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 的范围内；
• 请不要使用内置的队列库。

思路与代码

方法一：数组

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，
便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。

循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

这道题说「循环」的意思是要求我们在数组里实现。使用链表的实现，创建结点和删除结点都是动态的，也就不存在需要循环利用的问题了。

在数组里的操作，我们参考「动态数组」的实现，是为了让每一步的操作复杂度都最低。

「MyCircularQueue(k): 构造器，设置队列长度为 k 」，这句话说明：题目 不要求我们实现动态扩容与动态缩容。

---

需要注意的地方：

1. 定义循环变量 front 和 rear 。一直保持这个定义，到底是先赋值还是先移动指针就很容易想清楚了。

front：队列首元素对应的数组的索引
rear：队列尾元素对应的索引的下一个索引

（说明：这个定义是依据“动态数组”的定义模仿而来。）

1. 为了避免「队列为空」和「队列为满」的判别条件冲突，我们有意浪费了一个位置。

浪费一个位置是指：循环数组中任何时刻一定至少有一个位置不存放有效元素。

• 判别队列为空的条件是：front == rear;
• 判别队列为满的条件是：(rear + 1) % capacity == front;。可以这样理解，当 rear 循环到数组的前面，要从后面追上 front，还差一格的时候，判定队列为满。

1. 因为有循环的出现，要特别注意处理数组下标可能越界的情况。指针后移的时候，下标 + 1+1，并且为了防止数组下标越界要取模。

cpp代码

class MyCircularQueue {
private:
    int front; // 队列首元素对应的数组的索引
    int rear;  // 队列尾元素对应的索引的下一个索引
    int capacity; // 循环队列的容量，即队列中最多可以容纳的元素数量。
    vector<int> elements;// 一个固定大小的数组，用于保存循环队列的元素。

public:
	//构造器，设置队列长度为 k 。
    //Initializes the object with the size of the queue to be k.
    MyCircularQueue(int k) {
        this->capacity = k + 1;
        this->elements = vector<int>(capacity);
        rear = front = 0;
    }

    // 向循环队列插入一个元素。如果成功插入则返回真。
    // Inserts an element into the circular queue. Return true if the operation is successful.
    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    // 从循环队列中删除一个元素。如果成功删除则返回真。
    // Deletes an element from the circular queue. Return true if the operation is successful.
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    // 从队首获取元素。如果队列为空，返回 -1 。
    // Gets the front item from the queue. If the queue is empty, return -1.
    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    // 获取队尾元素。如果队列为空，返回 -1 。
    // Gets the last item from the queue. If the queue is empty, return -1.
    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }

    // 检查循环队列是否为空。
    // Checks whether the circular queue is empty or not.
    bool isEmpty() {
        return rear == front;
    }

    // 检查循环队列是否已满。
    // Checks whether the circular queue is full or not.
    bool isFull() {
        return ((rear + 1) % capacity) == front;
    }
};

方法二：链表

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

循环队列的属性如下:

head head：链表的头节点，队列的头节点。
tail tail：链表的尾节点，队列的尾节点。
capacity capacity：队列的容量，即队列可以存储的最大元素数量。
size size：队列当前的元素的数量。

cpp代码

class MyCircularQueue {
private:
    ListNode *head; //链表的头节点，队列的头节点。
    ListNode *tail; //链表的尾节点，队列的尾节点。
    int capacity; //队列的容量，即队列可以存储的最大元素数量。
    int size; //队列当前的元素的数量。

public:
    //构造器，设置队列长度为 k 。
    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;
    }

    //从队首获取元素。如果队列为空，返回 -1 。
    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return head->val;
    }

    //获取队尾元素。如果队列为空，返回 -1 。
    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return tail->val;
    }

    //检查循环队列是否为空。
    bool isEmpty() {
        return size == 0;
    }

    //检查循环队列是否已满。
    bool isFull() {
        return size == capacity;
    }
};

rust代码

rust代码

use std::rc::Rc;
use std::cell::RefCell;

struct ListNode {
    prev: Option<Rc<RefCell<ListNode>>>,
    next: Option<Rc<RefCell<ListNode>>>,
    val: i32,
}

struct MyCircularQueue {
    head: Option<Rc<RefCell<ListNode>>>,
    cnt: i32,
    capacity: i32,
}

impl ListNode {
    fn new(val: i32) -> ListNode {
        ListNode { val, prev: None, next: None }
    }
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyCircularQueue {
    
    //构造器，设置队列长度为 k 。
    fn new(k: i32) -> Self {
        let mut head = Rc::new(RefCell::new(ListNode::new(-1)));
        head.borrow_mut().next = Some(head.clone());
        head.borrow_mut().prev = Some(head.clone());
        MyCircularQueue { head: Some(head), cnt: 0, capacity: k }
    }

    //向循环队列插入一个元素。如果成功插入则返回真。
    fn en_queue(&mut self, value: i32) -> bool {
        if self.is_full() { false } else {
            let mut head = self.head.clone();
            let prev = head.as_ref().unwrap().borrow().prev.clone();
            let mut new_node = Rc::new(RefCell::new(ListNode::new(value)));

            prev.as_ref().unwrap().borrow_mut().next = Some(new_node.clone());
            new_node.borrow_mut().prev = prev.clone();
            new_node.borrow_mut().next = head.clone();
            head.as_ref().unwrap().borrow_mut().prev = Some(new_node.clone());

            self.cnt += 1;
            true
        }
    }

    //从循环队列中删除一个元素。如果成功删除则返回真。
    fn de_queue(&mut self) -> bool {
        if self.is_empty() { false } else {
            let mut head = self.head.clone();
            let mut next_node = head.as_ref().unwrap().borrow().next.clone();

            next_node.as_ref().unwrap().borrow().next.as_ref().unwrap().borrow_mut().prev = head.clone();
            head.as_ref().unwrap().borrow_mut().next = next_node.as_ref().unwrap().borrow().next.clone();

            self.cnt -= 1;
            true
        }
    }

    //从队首获取元素。如果队列为空，返回 -1 。
    fn front(&self) -> i32 {
        if self.is_empty() { -1 } else { self.head.as_ref().unwrap().borrow().next.as_ref().unwrap().borrow().val }
    }

    //获取队尾元素。如果队列为空，返回 -1 。
    fn rear(&self) -> i32 {
        if self.is_empty() { -1 } else { self.head.as_ref().unwrap().borrow().prev.as_ref().unwrap().borrow().val }
    }

    //检查循环队列是否为空。
    fn is_empty(&self) -> bool {
        self.cnt == 0
    }

    //检查循环队列是否已满。
    fn is_full(&self) -> bool {
        self.cnt == self.capacity
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * let obj = MyCircularQueue::new(k);
 * let ret_1: bool = obj.en_queue(value);
 * let ret_2: bool = obj.de_queue();
 * let ret_3: i32 = obj.front();
 * let ret_4: i32 = obj.rear();
 * let ret_5: bool = obj.is_empty();
 * let ret_6: bool = obj.is_full();
 */

其他

一、循环队列的三种实现方式： 1、牺牲一个存储空间。 2、布尔标记法。 3、计数器法。

总要是为了，解决循环队列的判空、判满冲突

1. 浪费一个元素的存储空间：front指向队首的实际位置，rear指向实际位置的下一个位置，front==rear时为空，(rear+1) % m == front时为满
2. 使用标记tag，front指向队首实际位置，rear指向队尾实际位置的下一个位置，入队时tag=1，出队时tag=0，当front == rear && tag == 0时队空，当front == rear && tag == 1时队满
3. 使用front,rear, length作为判断队空队满的标志，这样就不用浪费一个元素的存储空间了，和tag的作用是一样的，front指向队首实际位置，rear指向队尾实际位置

二、因为是环形设计，所以往后走不能直接++，容易越界，应该为front=（front+1）%size，rear=（rear+1）%size。

参考

百科-循环队列

leetcode-设计循环队列

leetcode-威哥

通过设置标志位tag判断队空队满的顺序存储的循环队列