本关任务:实现 step1/SeqQueue.cpp 中的SQ_IsEmpty、SQ_IsFull、SQ_Length、SQ_In和SQ_Out五个操作函数,以实现判断队列是否为空、是否为满、求队列长度、队列元素入队和出队等功能。
时间: 2024-09-09 13:14:45 浏览: 172
data_structure2.rar_seqqueue
在 `step1/SeqQueue.cpp` 文件中,你需要为顺序队列(Sequential Queue)实现以下几个基本操作函数:
1. **SQ_IsEmpty()** - 这个函数用于检查队列是否为空。如果队列的头部指针等于尾部指针,说明队列为空。
```cpp
bool SQ_IsEmpty(SeqQueue &sq) {
return sq.head == sq.tail;
}
```
2. **SQ_IsFull()** - 队列是否已满取决于队列的容量(预先设定的最大元素数)和当前的元素个数。当尾部指针接近头指针,且两者相加接近队列容量时,表示队列已满。
```cpp
bool SQ_IsFull(SeqQueue &sq, int capacity) {
return (sq.tail + 1) % capacity == sq.head;
}
```
3. **SQ_Length()** - 返回队列中的元素个数,通过计算头尾指针的差值,并考虑到队列的循环特性(对于双端队列)。
```cpp
int SQ_Length(SeqQueue &sq) {
if (sq.head > sq.tail) {
return (sq.capacity - sq.tail + sq.head) % sq.capacity;
} else {
return sq.tail - 入队(SQ_In)操作通常会将元素添加到队尾,而出队(SQ_Out)则从队首取出元素并更新头指针。这里假设你已经有一个成员变量保存队列的容量,入队操作直接更新尾指针,出队操作在更新头指针前返回队首元素。
```cpp
void SQ_In(SeqQueue &sq, int value) {
if (!SQ_IsFull(sq, sq.capacity)) {
sq.tail = (sq.tail + 1) % sq.capacity; // 使用循环数组的概念
sq.queue[sq.tail] = value;
}
}
int SQ_Out(SeqQueue &sq) {
int result;
if (!SQ_IsEmpty(sq)) { // 如果非空
result = sq.queue[sq.head]; // 返回队首元素
sq.head = (sq.head + 1) % sq.capacity; // 更新头指针
}
return result;
}
```
阅读全文