C++ 队列详解_c++队列

C++ 队列详解

一、队列的基本概念

队列（Queue）是一种线性数据结构，它遵循先进先出（First In First Out，简称FIFO）的原则。在队列中，新元素总是被添加到队尾，而旧元素则从队首移除。队列的实现通常使用两个指针，一个指向队首，另一个指向队尾。当队尾指针到达数组的末尾时，它将回到数组的开头，形成一个循环。

二、C++ 队列的实现原理

1. 初始化队列

为了实现队列，我们需要定义一个队列类，包含以下成员变量：

• queue：存储队列元素的数组；
• front：指向队首元素的指针；
• rear：指向队尾元素的指针。

初始化队列时，需要将 front 和 rear 指针都指向数组的第一个元素。

class Queue {
   
public:
    int *queue;
    int front, rear;
    int size;
};
1
2
3
4
5
6
7

2. 入队操作

入队操作是指将元素添加到队列的尾部。首先，我们需要检查队列是否已满（即 size 是否等于队列的最大容量）。如果队列未满，我们可以将新元素添加到队尾，并更新 rear 指针。如果队列已满，我们需要将队尾元素移除，以便为新元素腾出空间。

void enqueue(Queue &q, int item) {
   
    if (q.size == q.queueSize) {
    // 如果队列已满，移除队尾元素
        q.dequeue();
    }
    q.queue[q.rear] = item; // 添加新元素到队尾
    q.rear = (q.rear + 1) % q.queueSize; // 更新队尾指针
    q.size++; // 更新队列大小
}
1
2
3
4
5
6
7
8
9
10

3. 出队操作