『西工大-数据结构-NOJ』 009-循环队列(严3.30) 『西北工业大学』

解题思路：

这道题要求对一个循环队列，进行入队、出队和判满等操作，我们先了解一下比较常规的循环队列。

以下是一个常见的循环队列的宏定义：

typedef struct { int *base; // 初始化的动态分配存储空间 int front; // 头指针，若队列不空，指向队列头元素 int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置 } SqQueue;

然而，我们这道题要求的循环队列没有front成员，而是增加了length成员，这其实也无妨，我们能找到front与length之间的关系，来实现相互表示，其关系是:(front+length-1)%N==rear。 接下来，我们就按题目要求进行操作即可，注意两点，一是循环队列需要留出一个空储存单元用于判空，二是在进行成员的运算后要注意进行求余操作（最好理解一下）。 具体操作见代码，代码中有部分注释。

题解代码：

#include<stdio.h> #include<stdlib.h> typedef struct node{//定义一个循环队列，队列中要有一个空储存单元用于判空 int *data;//int型数组data int length; int rear;//由题意，本循环链表没有front，但rear和N是与front有联系的，其关系是:(front+length-1)%N==rear int N; }Queue; void CreatQueue(Queue *Q, int n){//N值不定，动态申请 Q->N = n+1; Q->data = (int*)malloc(sizeof(int)*(Q->N)); Q->length = Q->rear = 0; } void AddElem(Queue *Q, int num){//队列添加元素 if((Q->rear+1)%(Q->N)==(Q->rear-Q->length)%Q->N){//加减后要取mod return;//若判满，则无法添加元素 } else{ Q->rear = (Q->rear+1)%(Q->N); Q->data[Q->rear] = num; Q->length++; } } int DeleteFrontElem(Queue *Q){//删除队头元素,并弹出 Q->length--;//此操作就相当于front++ return Q->data[(Q->rear-Q->length)%(Q->N)]; } int PopFrontElem(Queue *Q){//弹出队头元素 return Q->data[Q->rear-Q->length+1]; } int main(){ int n,i,len,OutNum; int A[1000]; char yesOrNo[5]; scanf("%d",&n); Queue *Q; Q = (Queue*)malloc(sizeof(Queue)); CreatQueue(Q,n); for(i=0;;i++){//录入队列储存数组 scanf("%d",&A[i]); char c = getchar(); if(c=='\n'){ break; } } len = i+1; for(i=0;i<len&&i<n;i++){//长度允许时将数据入队 AddElem(Q,A[i]); } scanf("%s",&yesOrNo);//过滤掉yes和no，这根本用不到 scanf("%d",&OutNum);//输入要出队的元素 while(PopFrontElem(Q)!=OutNum){//弹出要出队元素 DeleteFrontElem(Q); } DeleteFrontElem(Q); int new_front = PopFrontElem(Q);//记录队头元素 while(Q->length!=0){//输出剩余元素 printf("%d ",DeleteFrontElem(Q)); } printf("\n%d",new_front); return 0; }