题目:
假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(dlqueue)元素的操作。
解决方式:
循环队列是一种利用固定大小的数组来模拟队列操作的数据结构,它可以在不进行数据移动的情况下实现队列的循环使用。在循环队列中,队头和队尾是连续的位置,当指针移至数组末尾时会循环到数组开头。以下是循环队列的队空条件和队满条件的定义,以及插入和删除元素的操作。
队空条件:当队头指针(假设为front)和队尾指针(假设为rear)相等时,队列为空。 队满条件:当队头指针和队尾指针之差(取模运算)等于队列长度(假设为length)减一时,队列已满。
插入元素(enqueue)的操作:
1.如果队满,则拒绝插入。
2.否则,将队尾指针(rear)后移(取模运算以实现循环)。
3.将新元素存储在队尾指针指向的位置。
4.如果队头指针等于队尾指针,说明队列在插入前为空,需要将队头指针也后移。
5.增加队列长度(length)。
删除元素(dequeue)的操作:
1.如果队空,则拒绝删除。
2.否则,将队头指针(front)后移(取模运算以实现循环)。
3.减少队列长度(length)。
以下是具体的代码实现:
#include <iostream>
#define MAX_SIZE 100 // 定义队列的最大容量
typedef struct {
int Q[MAX_SIZE];
int front; // 队头指针
int rear; // 队尾指针
int length; // 队列长度
} CircularQueue;
// 初始化队列
void initQueue(CircularQueue &queue) {
queue.front = queue.rear = queue.length = 0;
}
// 判断队列是否为空
bool isEmpty(CircularQueue queue) {
return queue.front == queue.rear;
}
// 判断队列是否已满
bool isFull(CircularQueue queue) {
return (queue.rear - queue.front + MAX_SIZE) % MAX_SIZE == 1;
}
// 插入元素
bool enqueue(CircularQueue &queue, int value) {
if (isFull(queue)) {
std::cout << "Queue is full, cannot enqueue." << std::endl;
return false;
}
queue.Q[queue.rear] = value;
queue.rear = (queue.rear + 1) % MAX_SIZE;
queue.length++;
if (queue.front == queue.rear) {
queue.front++;
}
return true;
}
// 删除元素
bool dequeue(CircularQueue &queue, int &value) {
if (isEmpty(queue)) {
std::cout << "Queue is empty, cannot dequeue." << std::endl;
return false;
}
value = queue.Q[queue.front];
queue.front = (queue.front + 1) % MAX_SIZE;
queue.length--;
return true;
}
int main() {
CircularQueue queue;
initQueue(queue);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
int value;
if (dequeue(queue, value)) {
std::cout << "Dequeued value: " << value << std::endl;
}
return 0;
}
在这个实现中,我们使用了取模运算来处理队列的循环。当队列不为空时,front指针指向队列的第一个元素,rear指针指向队列的最后一个元素的下一个位置。每次插入操作都会增加length,而每次删除操作都会减少length。队空和队满的条件检查是为了避免在队列已满时尝试插入元素,或在队空时尝试删除元素。