Question

数据结构，队列，入队代码有一句不懂。

void EnQueue(QUEUE *Q,Elemtype elem){
s=(LINKLIST *)malloc(sizeof(LINKLIZT));
if(!s) exit(ERROR);
s->elem=elem;
s->next=NULL;
Q->rear->next=s;
Q->rear=s;
}
上面的代码中，第4行（ s->elem=elem;）是什么意思啊？为啥要有这一句啊？

Answer 1

当然是把要入队的元素elem赋值给新分配空间s的数据域鸭

Answer 2

一个简单方法就是模拟一下入队1个，2个，……，size个元素时各参数的变化
这里没有贴该队列的数据结构，偶只能靠自己的推测做如下说明

分配空间是room[0]～room[size-1]，而room[size]是不存在的
从代码上看，该数据结构应该是想把room[0]作为room[size]来用
也就是说，第k个入队元素存储在room[k]的位置

这样就会产生如下的问题
初始状态：rear=0,front=0
当入队size-1个以后，rear=size-1,front=0
若再入一个，rear和front就会都为0，但此时并非初始状态

怎样才能区分这两种状态？光靠len是不行的

事实上，该程序是想让front指向队首的上一个位置，而非队首
即整个队列是存放在room[front+1]～room[rear]的循环空间中
这样，当front=rear的时候就意味着队列为空

（偶以前学的是严蔚敏的C版数据结构，上面处理循环队列的方法类似，是将front指向队首，而rear指向队尾的下一个位置）

如此以来，队列的最大容量实际上只有size-1
（为了判别队列状态而牺牲了一个元素空间room[front]）

1. 分配空间：if(len>=size-1)
当容量超过size-1，就要重新分配空间

2. 入队：rear++; if(rear>=size)rear=0; room[rear]=elem;
其实关于这个都无需想太多，无非是轮到了size就变成0

3. 出队：front++; if(front>=size)front=0; return room[front];
设size=5，那么最多只能进4个
连续进队4个后，len=4,rear=4,front=0
再出队4个，len=0,rear=0,front=0，为空
为空的条件前面if(len<=0)已经检测过了，会抛出异常

4. 取队首：return room[(front+1)%size];
这个就很容易解释了，front+1才是指向队首的位置
而这段代码没有给出队列为空的条件判断，必需要加上
用if(len<=0)或if(front==rear)都可以

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
关于补充：

1. 这个我仔细想了一下，用len来判断是可以的
那么当front＝rear时，需要考察len才能确定队列的状态
事实上，用于状态的信息表达总需要牺牲掉一个空间
最简便的方法就是牺牲数组空间
（以前学的C版数据结构就是如此，该队列没有len）
若用len的话，的确可以不用牺牲数组空间

2.
该程序用front指向队首上一个是有道理的
若用front指向队首，rear指向队尾
那么只能借助len判断状态
也就是if((len！=1)&&(front=rear))
这种做法并不是很方便，起码理解起来并不是很直观
试想，入队一个元素后，front和rear与空队列没有变化
若再出队一个元素，front和rear也不应该有变化
这样出队和入队就需要针对len＝1和0单独考虑
增加了程序的复杂度

3.
我想你的意思应该是front初值设为-1
（实际上也可以设为size-1）
然后room[0]就可以用来放队首
这样同1效果是一样的，只不过入队次序从room[0]开始
而且也会出项某两个状态需要根据len来区别

按照上面的讨论，其实是可以节约1个空间的
1个空间不会增加算法的空间复杂度
但是，要实现则需要重写代码
比如，ResizeRoom()方法就需要重写
同时，还需要保证各方法的时间复杂度

首先要肯定你是一个很有头脑的人
其实这只是一个小问题，何必想那么多呢？
写这个容器的人已经写下了这样的数据结构
只要这个数据结构没有太大的缺陷
我们弄明白，照搬就是了
一个数据结构的实现方式有很多种
java语言最关键的是api，也就是其功能
而要彻底的研究算法的效率，还得用C或者汇编
对一个高级语言的使用者，就不用在这个问题上想得太复杂了