要求循环队列不损失一个空间全部都能得到利用, 设置一个标志 tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满, 请编写与此相应的入队与出队算法。
时间: 2024-05-08 18:14:49 浏览: 75
入队算法:
1. 判断队列是否满,如果满了,则返回错误;
2. 将元素插入到队尾指针所指的位置;
3. 将队尾指针后移一位;
4. 如果队尾指针已经到达队列最后一个位置,则将其置为0,表示下一个元素将插入到队列的第一个位置;
5. 如果队列为空,则将tag置为1。
出队算法:
1. 判断队列是否为空,如果为空,则返回错误;
2. 将队头指针所指的元素取出;
3. 将队头指针后移一位;
4. 如果队头指针已经到达队列最后一个位置,则将其置为0,表示下一个元素将从队列的第一个位置取出;
5. 如果队列已经空了,则将tag置为0。
代码如下:
```c++
#define MAX_SIZE 10
typedef struct {
int data[MAX_SIZE];
int front, rear;
int tag;
} CircularQueue;
void InitQueue(CircularQueue &Q) {
Q.front = Q.rear = 0;
Q.tag = 1;
}
bool IsEmpty(CircularQueue Q) {
return (Q.front == Q.rear) && (Q.tag == 0);
}
bool IsFull(CircularQueue Q) {
return (Q.front == Q.rear) && (Q.tag == 1);
}
bool EnQueue(CircularQueue &Q, int x) {
if (IsFull(Q)) return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MAX_SIZE;
if (Q.rear == Q.front) Q.tag = 0;
return true;
}
bool DeQueue(CircularQueue &Q, int &x) {
if (IsEmpty(Q)) return false;
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MAX_SIZE;
if (Q.front == Q.rear) Q.tag = 1;
return true;
}
```
阅读全文