对于环形队列来说,已知队尾指针和队列中元素个数,给出该环形队列的类型声明,并设计出这种环形队列的初始化、入队、出队和判空算法。
时间: 2024-05-03 10:21:58 浏览: 78
环形队列的类型声明:
```c++
template<typename T>
class CircularQueue{
private:
T *data; // 存储队列元素的数组
int front; // 队头指针,指向队列第一个元素
int rear; // 队尾指针,指向队列最后一个元素的下一个位置
int maxSize; // 队列最大容量
int count; // 队列中元素个数
public:
CircularQueue(int size); // 构造函数
~CircularQueue(); // 析构函数
bool isEmpty(); // 判断队列是否为空
bool isFull(); // 判断队列是否已满
bool enqueue(T val); // 入队操作
bool dequeue(T &val); // 出队操作
};
```
环形队列的初始化:
```c++
template<typename T>
CircularQueue<T>::CircularQueue(int size){
maxSize = size;
data = new T[maxSize];
front = rear = count = 0;
}
template<typename T>
CircularQueue<T>::~CircularQueue(){
delete [] data;
}
```
环形队列的入队操作:
```c++
template<typename T>
bool CircularQueue<T>::enqueue(T val){
if(isFull()){ // 如果队列已满,无法入队
return false;
}
data[rear] = val; // 将元素插入到队尾
rear = (rear + 1) % maxSize; // 队尾指针后移一位,如果达到队列末尾则回到队列头部
count++; // 元素个数加1
return true;
}
```
环形队列的出队操作:
```c++
template<typename T>
bool CircularQueue<T>::dequeue(T &val){
if(isEmpty()){ // 如果队列为空,无法出队
return false;
}
val = data[front]; // 取出队头元素
front = (front + 1) % maxSize; // 队头指针后移一位,如果达到队列末尾则回到队列头部
count--; // 元素个数减1
return true;
}
```
环形队列的判空操作:
```c++
template<typename T>
bool CircularQueue<T>::isEmpty(){
return count == 0;
}
```
环形队列的判满操作:
```c++
template<typename T>
bool CircularQueue<T>::isFull(){
return count == maxSize;
}
```
阅读全文