循环链表与循环队列的区分与对比

一、循环链表与循环队列的本质差异：存储结构不同

1. 循环链表（以循环链队为例）

• 结构特点：链表的尾节点 next 指针指向头节点，形成一个环形链表。
• 示意图：

  [头节点] <-> [节点1] <-> [节点2] <-> ... <-> [尾节点]↑                       ↓└──────────────────────┘
  

• 循环链队的实现：
  • 队头指针 front 指向头节点，队尾指针 rear 指向尾节点。
  • 入队时，新节点接在尾节点后，并让 rear 指向新节点；
    出队时，删除头节点的下一个节点，若队列为空则让 front 和 rear 都指向头节点。

2. 循环队列（基于数组）

• 结构特点：利用数组下标取模（%）实现逻辑上的循环，物理上仍是线性数组。
• 示意图（假设数组大小为 5）：

  plaintext

  数组下标：0  1  2  3  4
  存储数据：[3][4][空][1][2]↑       ↑front   rear
  

• 循环逻辑：
  当 rear 到达数组末尾（如 rear=4），下一次入队时 rear=(4+1)%5=0，回到数组开头。

二、循环链队与循环队列的判空 / 判满对比

1. 循环链队（以带头节点的循环链表为例）

• 判空条件：
  front == rear（头节点和尾节点指向同一个节点，链表中无数据节点）。
• 判满条件：
  通常不判满（链表可动态分配节点），除非内存不足；若要判满，需额外计数：
  节点数 == 最大容量（通过计数器 count 判断）。

2. 循环队列（基于数组）

• 判空条件：
  front == rear（队头和队尾索引相同，数组中无元素）。
• 判满条件：
  (rear + 1) % maxSize == front（队尾下一个位置等于队头，数组空间耗尽）。

三、用快递站点类比：理解 “循环” 的不同

1. 循环链队（链表循环）

• 类比：快递站点排成一个环，每个站点（节点）的下一个站点是环中的下一个位置，尾站点的下一个是头站点。
• 特点：
  • 站点数量可动态增加（新站点加入环中）；
  • 没有 “满” 的概念，除非所有地址都被占用。

2. 循环队列（数组循环）

• 类比：快递站点是一排固定窗口（数组下标），当最后一个窗口（如 4 号）用完后，下一个快递又回到 1 号窗口。
• 特点：
  • 窗口数量固定（数组大小固定）；
  • 当所有窗口都被占用时（(rear+1)%maxSize == front），无法再接收新快递（队满）。

四、代码对比：循环链队 vs 循环队列

1. 循环链队的入队（简化示例）

// 假设循环链队的front和rear指向头节点（循环链表）
void EnQueue(LinkQueue *Q, ElemType e) {QueuePtr newNode = malloc(sizeof(QNode));newNode->data = e;// 尾插法（循环链表）newNode->next = Q->front;         // 新节点指向头节点Q->rear->next = newNode;          // 原尾节点指向新节点Q->rear = newNode;                // 更新尾指针
}

2. 循环队列的入队

void EnQueue(SqQueue *Q, ElemType e) {if ((Q->rear + 1) % Q->maxSize == Q->front) {printf("队满，无法入队\n");return;}Q->data[Q->rear] = e;Q->rear = (Q->rear + 1) % Q->maxSize;  // 循环更新rear
}

五、总结：核心区别一句话

• 循环链队的 “循环” 是链表节点的物理连接形成环，依靠指针跳转；
• 循环队列的 “循环” 是数组下标的逻辑循环，依靠模运算实现位置复用。