【初阶数据结构和算法】Leetcode 刷题之设计循环队列

一只蜗牛儿

737人浏览 · 2024-12-26 09:30:24

一只蜗牛儿 · 2024-12-26 09:30:24 发布

循环队列是一种基于数组实现的队列，它通过首尾指针来实现队列的循环结构，从而避免了队列中前端元素的空闲空间浪费。在实际应用中，循环队列可以解决传统队列（如线性队列）在达到数组容量时无法继续插入元素的问题，特别适用于要求队列操作具有固定大小且需要循环的场景。

本篇文章将介绍如何设计一个循环队列，并通过 Leetcode 刷题的方式来实现这个数据结构。我们将实现一个类 MyCircularQueue，并通过 Leetcode 题目进行演示。

1. 循环队列的基本概念

循环队列是一个固定大小的队列，其中队列的最后一个元素与第一个元素相连接，形成一个环形结构。它有两个指针：一个指向队头（front），一个指向队尾（rear）。队列的元素的入队和出队操作都是在这两个指针的帮助下进行的。

入队（enqueue）：在队列尾部插入一个新元素。
出队（dequeue）：从队列头部移除一个元素。
队列为空时：front == rear，表示队列没有任何元素。
队列满时：(rear + 1) % capacity == front，表示队列已经没有空间插入新元素。

2. 循环队列的设计

我们可以使用一个固定大小的数组来实现循环队列，定义以下几个基本操作：

构造函数：初始化队列的容量和指针。
enqueue：将元素插入队列的尾部。
dequeue：移除队列头部的元素。
Front：返回队列头部的元素。
Rear：返回队列尾部的元素。
isEmpty：判断队列是否为空。
isFull：判断队列是否已满。

3. Leetcode 刷题：设计循环队列

Leetcode 题目：622. Design Circular Queue

题目要求设计一个固定大小的循环队列，支持以下操作：

MyCircularQueue(k): 构造函数，队列的大小是 k。
enQueue(value): 将一个元素插入队列，如果队列已满返回 false。
deQueue(): 从队列中移除一个元素，如果队列为空返回 false。
Front(): 获取队头元素。
Rear(): 获取队尾元素。
isEmpty(): 判断队列是否为空。
isFull(): 判断队列是否已满。

4. 代码实现

#include <iostream>
#include <vector>

using namespace std;

class MyCircularQueue {
private:
    vector<int> queue;  // 用于存储队列元素
    int front, rear;    // 队头和队尾指针
    int size;           // 队列当前的元素个数
    int capacity;       // 队列的容量

public:
    // 构造函数，初始化队列大小
    MyCircularQueue(int k) {
        capacity = k;
        queue.resize(k);
        front = rear = -1;
        size = 0;
    }

    // 入队操作，将元素插入队列
    bool enQueue(int value) {
        if (isFull()) return false;  // 队列已满，无法插入
        
        if (isEmpty()) {
            front = 0;  // 如果队列为空，设置队头指针
        }
        
        rear = (rear + 1) % capacity;  // 环形队列，更新队尾指针
        queue[rear] = value;  // 插入元素
        size++;  // 更新队列大小
        return true;
    }

    // 出队操作，移除队头元素
    bool deQueue() {
        if (isEmpty()) return false;  // 队列为空，无法删除

        if (front == rear) {
            front = rear = -1;  // 如果删除后队列为空，重置指针
        } else {
            front = (front + 1) % capacity;  // 环形队列，更新队头指针
        }
        size--;  // 更新队列大小
        return true;
    }

    // 获取队头元素
    int Front() {
        if (isEmpty()) return -1;
        return queue[front];
    }

    // 获取队尾元素
    int Rear() {
        if (isEmpty()) return -1;
        return queue[rear];
    }

    // 判断队列是否为空
    bool isEmpty() {
        return size == 0;
    }

    // 判断队列是否已满
    bool isFull() {
        return size == capacity;
    }
};

int main() {
    MyCircularQueue queue(3);  // 创建一个容量为 3 的循环队列

    // 入队操作
    cout << queue.enQueue(1) << endl;  // true
    cout << queue.enQueue(2) << endl;  // true
    cout << queue.enQueue(3) << endl;  // true
    cout << queue.enQueue(4) << endl;  // false，因为队列已满

    // 获取队头和队尾元素
    cout << queue.Front() << endl;  // 1
    cout << queue.Rear() << endl;   // 3

    // 出队操作
    cout << queue.deQueue() << endl;  // true
    cout << queue.Front() << endl;    // 2

    // 再次入队
    cout << queue.enQueue(4) << endl;  // true

    // 获取队头和队尾元素
    cout << queue.Front() << endl;  // 2
    cout << queue.Rear() << endl;   // 4

    return 0;
}

5. 代码解析

构造函数：我们用一个数组 queue 来存储队列元素，front 和 rear 分别表示队头和队尾的索引，size 用来表示队列中当前的元素个数。
enQueue：如果队列没有满，首先检查队列是否为空，如果为空，front 设置为 0；然后更新 rear 指针，插入元素并增加队列大小。
deQueue：如果队列不为空，更新 front 指针并减少队列大小。如果队列空了，需要将 front 和 rear 重置为 -1。
Front 和 Rear：如果队列不为空，返回队头和队尾的元素；否则返回 -1。
isEmpty 和 isFull：分别判断队列是否为空和是否已满。