Question

如果用一个循环单链表表示队列（称为循环队列），该队列只设一个尾指针rear，不设队首指针，编写程序。

Answer 1

你这是要用 C 语言实现吧？ 我很少用 C 语言，所以一下子也写不出程序给你。不过这个原理倒是不难。

单链表你会写吗？如果会，你把链表最后一项的尾指针指向第一个元素，就成了你说的循环链表了。

首元素和尾元素可能需要加个标志。

注意：
追加元素的时候，被追加元素的指针要指向首元素。
删除最后一个元素的时候，更新前一项的指针，使其指向首元素。

补充：
给你提供一个不考虑插入和删除中间元素的例子

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LENGTH 5

struct list {
int key;
char name[20];
struct list *next;
};

struct list *add_list(int key, char *name, struct list *parent);
void show_list(struct list *p);
void free_list(struct list *p);

struct list *first;

int main(void)
{
struct list *parent;
char name[20];
int key = 0;
parent = NULL;
int count = 0;
printf("Please input key and name (length < 20), END: CTRL+Z\n");
while (scanf("%d %s", &key, name) != EOF) {
parent = add_list(key, name, parent);
count++;
if(count == 1) first = parent;
if(count == MAX_LENGTH) break;
}

show_list(first);
free_list(first);

return 0;
}

/*** 追加队列成员 ***/
struct list *add_list(int key, char *name, struct list *parent)
{
struct list *p;

if ((p = (struct list *) malloc(sizeof(struct list))) == NULL) {
printf("malloc error\n");
exit(EXIT_FAILURE);
}

p->key = key;
strcpy(p->name, name);
if(parent == NULL) {
parent = p;
first = p;
} else {
parent->next = p;
p->next = first;
}

return p;
}

/*** 显示队列 ***/
void show_list(struct list *p)
{
while (p != NULL) {
printf("%3d %s\n", p->key, p->name);
p = p->next;
if(p->key == first->key) break;
}
}

/*** 清空队列 ***/
void free_list(struct list *p)
{
struct list *p2;

while (p != NULL) {
p2 = p->next;
free(p);
p = p2;
if(p->key == first->key) break;
}
}

运行结果：
输入

1 aa
2 bb
3 cc
4 dd
5 ee

输出
1 aa
2 bb
3 cc
4 dd
5 ee