题目

   Qestion： 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点 (注意不设头指针) ，试编写相应的置空队、判队空、入队和出队等算法。

核心思路

  该队列的特殊之处：

• 用链表来表示队列
• 该链表为带头节点的链表
• 该队列无头指针，只有尾指针

  解决本题的思路：

• 使用Q.rear->next来表达头节点
• 使用Q.rear->next->next来表示首元结点

  需要注意的点：

• 出队的时候需要进行判断，出队的结点是否为最后一个结点。

1. 入队的结点从队尾进入，也就是Q.rear所指的结点，出队的结点从队头出队，也就是头节点的next，用尾指针来表示就是Q.rear->next->next；
2. 队空的条件是队列中只含一个结点，也就是头节点，或者用Q.length == 0 来判断也可以；
3. 置队空的方式为判断队伍是否为空，若为false则进行出队操作，直到该队列只剩下一个头节点。
4. 入队的流程大致为：先创建一个新的结点newNode并且将其接到队伍的最后面（保持整个链不断），再将Q的尾指针Q.rear指向新结点，最后让Q.length++；
5. 出队的大致流程为：先创建一个临时指针指向首元结点（即将出队的结点），根据其是否为最后一个结点进行分别的删除操作，释放首元结点的空间，使Q.length--;

核心代码

图解

enQueue（入队）算法

deQueue（出队）算法

全部代码（可运行文件）

/*
3、算法设计：假设以带头结点的循环链表表示队列，
并且只设一个指针指向队尾元素结点(注意不设头指针) ，
试编写相应的置空队、判队空 、入队和出队等算法。出队入队顺序：队尾进入，队头出
队头出队，队尾入队
*/#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
struct LNode
{int data;LNode *next;
};typedef struct
{LNode *rear;int length;
} Queue;// 初始化
void InitQueue(Queue &Q)
{LNode *head = new LNode;head->next = head; // 头节点的next指向自己（循环）head->data = 999;Q.rear = head; // 尾指针指向头指针Q.length = 0;
}
// 入队
void enQueue(int x, Queue &Q)
{LNode *newNode = new LNode;if (!newNode){return;}else{newNode->data = x;newNode->next = Q.rear->next; // 新节点的next指向头节点Q.rear->next = newNode;Q.rear = newNode; // 尾指针指向新节点Q.length++;		  // 队长+1}
}// 出队
void deQueue(Queue &Q)
{LNode *tmp = Q.rear->next->next; // 使用一个临时指针tmp，用于指向首元节点if (Q.length > 1){Q.rear->next->next = tmp->next; //  头节点的next连接到首元节点的next节点，也就是把首元节点与整个链表的联系断了}else{Q.rear = Q.rear->next;Q.rear->next = Q.rear;}free(tmp);	// 释放首元节点（队头元素）Q.length--; // 队长-1
}// 打印当前列表的情况
void PrintQueue(Queue Q)
{LNode *tmp = Q.rear->next->next;while (tmp != Q.rear->next){printf("%d\\n", tmp->data);tmp = tmp->next;}
}
// 判断队空
bool IsQueueEmpty(Queue Q)
{if (Q.rear->next->next == Q.rear->next) // 头节点的next指向它自己return true;elsereturn false;
}// 置队空
void SetQueueEmpty(Queue &Q)
{while (!IsQueueEmpty(Q)){deQueue(Q);}printf("当前队列已经置空");
}int main()
{Queue Q;InitQueue(Q);if (IsQueueEmpty(Q)){printf("queue is empty\\n");}else{printf("queue isn't empty\\n");}enQueue(1, Q);SetQueueEmpty(Q);enQueue(2, Q);enQueue(3, Q);enQueue(4, Q);SetQueueEmpty(Q);if (IsQueueEmpty(Q) == true){printf("queue is empty\\n");}else{printf("queue isn't empty\\n");}PrintQueue(Q);return 0;
}

结束语

   因为是算法小菜，所以提供的方法和思路可能不是很好，请多多包涵~如果有疑问欢迎大家留言讨论，你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗？我们之间的交流是我最大的动力！