c++环形队列

环形队列是一种特殊的队列，其在实现上使用了循环数组来模拟队列的操作。以下是一个简单的C++环形队列示例代码：

#include <iostream>

class CircularQueue {
private:
    int* array;
    int front;
    int rear;
    int capacity;

public:
    CircularQueue(int size) {
        capacity = size + 1; // One extra space to differentiate between full and empty states
        array = new int[capacity];
        front = 0;
        rear = 0;
    }

    ~CircularQueue() {
        delete[] array;
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return (rear + 1) % capacity == front;
    }

    void enqueue(int value) {
        if (isFull()) {
            std::cout << "Queue is full. Cannot enqueue." << std::endl;
            return;
        }
        array[rear] = value;
        rear = (rear + 1) % capacity;
    }

    void dequeue() {
        if (isEmpty()) {
            std::cout << "Queue is empty. Cannot dequeue." << std::endl;
            return;
        }
        front = (front + 1) % capacity;
    }

    int getFront() {
        if (isEmpty()) {
            std::cout << "Queue is empty." << std::endl;
            return -1; // You can choose a different way to handle this case
        }
        return array[front];
    }
};

int main() {
    CircularQueue queue(3);

    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    std::cout << "Front element: " << queue.getFront() << std::endl;

    queue.dequeue();

    std::cout << "Front element after dequeue: " << queue.getFront() << std::endl;

    return 0;
}

这段代码创建了一个环形队列类 CircularQueue，它使用循环数组来模拟队列的操作。在循环数组中，数组的最后一个位置和第一个位置紧密相连，这就创建了环形的效果。在队列的 enqueue 操作中，rear 指针会在循环中移动。在队列的 dequeue 操作中，front 指针也会在循环中移动。这样可以很好地利用数组空间，并实现队列的循环使用。

可以使用结构体来实现环形队列。以下是使用结构体的C++环形队列示例代码：

#include <iostream>

struct CircularQueue {
    int* array;
    int front;
    int rear;
    int capacity;

    CircularQueue(int size) {
        capacity = size + 1; // One extra space to differentiate between full and empty states
        array = new int[capacity];
        front = 0;
        rear = 0;
    }

    ~CircularQueue() {
        delete[] array;
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return (rear + 1) % capacity == front;
    }

    void enqueue(int value) {
        if (isFull()) {
            std::cout << "Queue is full. Cannot enqueue." << std::endl;
            return;
        }
        array[rear] = value;
        rear = (rear + 1) % capacity;
    }

    void dequeue() {
        if (isEmpty()) {
            std::cout << "Queue is empty. Cannot dequeue." << std::endl;
            return;
        }
        front = (front + 1) % capacity;
    }

    int getFront() {
        if (isEmpty()) {
            std::cout << "Queue is empty." << std::endl;
            return -1; // You can choose a different way to handle this case
        }
        return array[front];
    }
};

int main() {
    CircularQueue queue(3);

    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    std::cout << "Front element: " << queue.getFront() << std::endl;

    queue.dequeue();

    std::cout << "Front element after dequeue: " << queue.getFront() << std::endl;

    return 0;
}

这段代码使用了 struct 关键字定义了一个名为 CircularQueue 的结构体，其中包含了队列所需的成员变量。其他部分与之前的示例相似，只是将类转换为了结构体的形式。