C语言循环队列实现：利用Tag域解决队空队满判断冲突

核心原理

传统的循环队列通过取模运算实现空间的循环利用，但当 front == rear 时存在歧义：
- 初始或全部元素被删除后为“空”。
- 填满所有剩余插槽后为“满”。

引入 tag 变量可以消除这种不确定性：

• tag = 0：表示队列为空。
  
• tag = 1：表示队列为满（或最后一次操作是入队）。

准备工作

在编写算法前，需要定义队列的结构体及基础常量。假设最大容量为 MaxSize，数据类型为 ElemType。

// 定义队列结构体
typedef struct {
    ElemType data[MaxSize]; // 数据存储区
    int front;              // 队头指针
    int rear;               // 队尾指针
    int tag;                // 状态标志域
} SqQueue;

第1步：实现入队算法 (EnQueue)

目的

将新元素插入队列尾部，同时更新指针并修改 tag 状态。

关键逻辑

1. 检查队满：如果 front == rear 且 tag == 1，说明队列已满，拒绝插入。
2. 存入数据：将元素赋值给 data[rear]。
3. 更新尾指针：使用取模运算移动尾指针，rear = (rear + 1) % MaxSize。
4. 标记状态：因为成功执行了插入操作，必须将 tag 置为 1。

代码实现

int EnQueue(SqQueue &Q, ElemType x) {
    // 若队头等于队尾且tag为1，则队满
    if (Q.front == Q.rear && Q.tag == 1)
        return 0; // 返回0表示失败

    Q.data[Q.rear] = x;             // 1. 插入新元素
    Q.rear = (Q.rear + 1) % MaxSize; // 2. 尾指针后移
    Q.tag = 1;                       // 3. 标记最后操作为入队

    return 1; // 返回1表示成功
}

第2步：实现出队算法 (DeQueue)

目的

从队列头部取出元素，更新头指针并修正 tag 状态。

关键逻辑

1. 检查队空：如果 front == rear 且 tag == 0，说明队列为空，无法读取。
2. 读取数据：将 data[front] 的值赋给传出参数 x。
3. 更新头指针：使用取模运算移动头指针，front = (front + 1) % MaxSize。
4. 标记状态：因为执行了删除操作，将 tag 置为 0。

代码实现

int DeQueue(SqQueue &Q, ElemType &x) {
    // 若队头等于队尾且tag为0，则队空
    if (Q.front == Q.rear && Q.tag == 0)
        return 0; // 返回0表示失败

    x = Q.data[Q.front];                // 1. 获取队头元素
    Q.front = (Q.front + 1) % MaxSize;   // 2. 头指针后移
    Q.tag = 0;                           // 3. 标记最后操作为出队

    return 1; // 返回1表示成功
}

关于重置指针的补充说明

原文中提到“当删除之后链表为空时，还需增加一步，将尾指针指向头结点”。在实际的 SqQueue 标准实现中，仅依靠 tag 的变化已足够区分状态，无需额外移动 rear 指针。但如果您希望在对列清空后保持指针位置一致或进行特定复位，可以在出队函数中添加如下判断：

// 可选的清空重置逻辑
if (Q.front == Q.rear && Q.tag == 0) {
    // 此时队列为空，可根据需要选择是否重置 rear
    // Q.rear = Q.front; 
}

以上就是利用 Tag 标志域解决 C 语言循环队列判空判满问题的详细内容，更多关于 C 语言数据结构队列算法的资料请关注本站其它相关文章！