循环队列

求解报数问题

设有n个人占成一排，从左向右的编号分别为1~n，现在从左往右报数“1，2，1，2……”，数到“1”的人出列，数到“2”的人站到队列的最右端。报数过程反复进行，直到n个人都出队列为止。要求给出他们的出列顺序。
例如，当n=8时的初始序列为：
1 2 3 4 5 6 7 8
则出列顺序：
1 3 5 7 2 6 4 8

• 算法思想
  采用环形队列，做如下操作：
  1.出队一个元素(报数为1的人)，输出其编号
  2.若队列不空，出队一个元素(报数为2的人)，再让其入队

循环队列创建

typedef struct queue Queue;
struct queue
{
	int data[Maxsize];
	int front;
	int rear;
};
bool Full(Queue *L)            //判满
{
	return ((L->rear+1)%Maxsize == L->front);
}
bool Empty(Queue *L)           //判空
{
	return (L->front == L->rear);
}
void Enqueue(Queue *L, int e)   //入队
{
	if(!Full(L))
	{
		L->rear = (L->rear+1)%Maxsize;
		L->data[L->rear] = e;
	}
	else
		exit(0);
}
void Dequeue(Queue *L,int *e)   //出队
{
	L->front = (L->front+1)%Maxsize;
	*e = L->data[L->front];
}

主函数输出队列

int main()
{
	Queue *L = (Queue *)malloc(sizeof(Queue));
	L->front = L->rear = 0;
	int a[] = {1, 2, 3, 4, 5, 6, 7, 8}, e;
	for(int i=0; i<8; i++)
		Enqueue(L,a[i]);
	while(!Empty(L))        //报数为1的人出队
	{
		Dequeue(L,&e);
		printf("%d ",e);
		if(!Empty(L))   //非空，报数为2的人出队再入队
		{
			Dequeue(L,&e);
			Enqueue(L, e);
		}
	}
    return 0;
}

——————运行结果——————

---

起初以为报数问题就是日常的报数，1~n报完后就结束，误认为输出队列顺序是：
1 3 5 7 2 4 6 8

• 错解
  创建长度为N(N=9)的循环队列，使队列已满。
  1~n报完即（L->rear==N/2-1）成立，再出队直至队列为空

while(!Empty(L))
{
	if(L->rear == (Maxsize)/2-1)
	{
		Dequeue(L,&e);
		printf("\n%d ", e);
	}
	else
	{
		printf("%d ", e);
		if(!Empty(L))
		{
			Dequeue(L, &e);
			Enqueue(L, e);	
		}	
	}	
}