基于容纳MaxSize-1个元素的环状队列表示法,用C++实现返回队列元素个数的函数。
时间: 2024-10-10 17:05:21 浏览: 19
C++实现循环队列
在基于环状队列(Circular Queue)的实现中,由于队列的两端分别是队头和队尾,当队列满了(MaxSize-1个元素),新加入的元素会覆盖掉队头元素,形成一种“循环”的效果。我们可以利用两个指针front和rear分别指向队首和队尾,来跟踪队列的状态。以下是一个C++的简单实现,包括一个计算队列元素个数的函数`queueSize()`:
```cpp
#include <iostream>
template <typename T>
class CircularQueue {
private:
T* queueData;
int front;
int rear;
int maxSize;
public:
CircularQueue(int max_size) : queueData(new T[max_size]), front(0), rear(0), maxSize(max_size) {}
~CircularQueue() {
delete[] queueData;
}
bool isEmpty() const {
return front == rear;
}
bool isFull() const {
return (rear + 1) % maxSize == front;
}
void enqueue(T element) {
if (isFull()) {
std::cout << "Queue is full, cannot enqueue.\n";
return;
}
queueData[rear] = element;
rear = (rear + 1) % maxSize; // 队尾后移
}
T dequeue() {
if (isEmpty()) {
std::cout << "Queue is empty, cannot dequeue.\n";
return T();
}
T removedValue = queueData[front];
front = (front + 1) % maxSize; // 队头后移
return removedValue;
}
int queueSize() const {
if (isEmpty()) {
return 0;
} else if (front <= rear) {
return rear - front + 1; // 正常情况,直接计算差值
} else {
return maxSize - front + rear; // 队头超过队尾,需要考虑“循环”
}
}
// 其他函数...
};
int main() {
CircularQueue<int> cq(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
std::cout << "Queue size: " << cq.queueSize() << std::endl;
return 0;
}
```
在上述代码中,`queueSize()`函数首先检查队列是否为空,然后判断是否发生了“循环”。如果是正常情况(front <= rear),则直接计算队尾减去队头加一;如果是循环情况(front > rear),则计算maxSize减去front加上rear。
阅读全文