设计一个循环队列QUEUE<T>,用data[0..MaxSize-1]存放队列元素,用front和rear分别作为队头和队尾指针,并用一个标志tag队列可能空(false)或可能满((true),要求设计队列的相关基本运算算法
时间: 2023-05-27 20:02:35 浏览: 230
以下是循环队列QUEUE<T>的基本运算算法:
1. 构造函数:用于初始化循环队列。在构造函数中设置队头和队尾指针front和rear均为0,标志tag为false,表示队列为空。
2. 入队操作enqueue(T item):向队列尾部插入元素item。如果队列已满,则抛出队满异常。如果队列非满,则将元素item插入队尾,并将rear指针向后移动一位。
3. 出队操作dequeue():从队列头部取出一个元素并将其删除。如果队列非空,则返回被删除元素的值,并将front指针向后移动一位。如果队列已空,则抛出队空异常。
4. 获取队头元素getFront():返回循环队列的队头元素,并不删除队头元素。如果队列为空,则抛出队空异常。
5. 获取队列中元素个数getSize():返回循环队列中元素的个数。
6. 判断队列是否为空isEmpty():如果队列为空,则返回true,否则返回false。
7. 判断队列是否已满isFull():如果队列已满,则返回true,否则返回false。
下面是循环队列QUEUE<T>的代码实现:
```
template <typename T>
class QUEUE {
private:
T* data;
int front, rear;
int capacity;
bool tag; // 解决队列满和空的标志
public:
// 构造函数
QUEUE(int cap) : front(0), rear(0), capacity(cap + 1), tag(false) {
data = new T[capacity];
}
// 入队操作
void enqueue(T item) {
if (isFull()) throw("Queue is full.");
data[rear] = item;
rear = (rear + 1) % capacity;
if (rear == front) tag = true;
}
// 出队操作
T dequeue() {
if (isEmpty()) throw("Queue is empty.");
T item = data[front];
front = (front + 1) % capacity;
if (rear == front) tag = false;
return item;
}
// 获取队头元素
T getFront() {
if (isEmpty()) throw("Queue is empty.");
return data[front];
}
// 获取队列中元素个数
int getSize() {
if (tag) return capacity - 1;
else return (rear - front + capacity) % capacity;
}
// 判断队列是否为空
bool isEmpty() {
return front == rear && !tag;
}
// 判断队列是否已满
bool isFull() {
return front == rear && tag;
}
// 析构函数
~QUEUE() {
delete[] data;
}
};
```
阅读全文