C++如何使用数组实现队列数据结构-C++-PHP中文网

因为front == rear既表示空也表示满，存在状态歧义；必须牺牲一个存储单元，使实际容量为n-1，空队列时front == rear，满队列时(rear + 1) % n == front。

c++如何使用数组实现队列数据结构

用固定大小数组模拟队列时，为什么 front 和 rear 不能直接用下标相等判断空？

因为队列空和满在朴素实现里都会出现 front == rear，无法区分。必须预留一个“空位”或额外维护长度/标志位。

推荐做法是牺牲一个元素空间：数组容量为 N，实际最多存 N-1 个元素。此时：

空队列：front == rear
满队列：(rear + 1) % N == front

这样仅靠两个指针就能无歧义判断状态，无需额外变量。

如何写一个线程不安全但简洁可用的循环数组队列？

适合教学、单线程嵌入式或竞赛场景。关键在于取模运算和边界检查的顺序。

class ArrayQueue {
    int* data;
    int front, rear, capacity;
public:
    ArrayQueue(int k) : capacity(k + 1), front(0), rear(0) {
        data = new int[capacity];
    }
    bool enQueue(int value) {
        if (isFull()) return false;
        data[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }
    bool deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        return true;
    }
    int Front() { return isEmpty() ? -1 : data[front]; }
    int Rear() { return isEmpty() ? -1 : data[(rear - 1 + capacity) % capacity]; }
    bool isEmpty() { return front == rear; }
    bool isFull() { return (rear + 1) % capacity == front; }
};

注意：Rear() 中 (rear - 1 + capacity) % capacity 是为避免负数取模未定义行为（尤其在 C++98/03 中）。