首页 > 代码库 > 数据结构(C实现)------- 顺序队列(循环队列之计数器实现)

数据结构(C实现)------- 顺序队列(循环队列之计数器实现)

        为了能充分的利用空间,解决顺序队列的“假溢出”问题,可以采用两种方法:一种是将数据向前移动,让空的存储单元留在队尾;另一种是将顺序队列构造成一个环状的空间,即将队列的数据区data[0....MAXSIZE-1]看成头尾相接的循环结构,使得data[0]接在data[MAXSIZE-1]之后,这就是循环队列。

        这节就来实现循环顺序队列。

       

        循环队列中的空闲的空间可以被利用,除非数组空间真的被队列元素全部占用,否则不会上溢。因此,队一此简单的应用外,真正实用的顺序队列是循环队列。

        入队时,队尾指针向前追赶队头指针;出队时,队头指针向前追赶队尾指针。因此队空和队满指针均等于队尾指针,无法通过Q->front == Q->rear来判断顺序队列是空还是满。
        为了解决这个问题,有3种方法,其一是设一个标识位,以区别顺序队列是空还是满;其二是使用一个计数器记录队列中元素的总数;其三是少用一个元素空间,约定入队前测试队尾指针在循环意义下加1是否等于队头指针,若相等,则认为是队满(注:rear所指的单元始终为空)。  

        这节,就先采用第二种方法,设一个计数器记录队列中元素的总数,用于判断队列空还是队列满。

顺序队列(循环队列)类型描述:

//顺序队列的类型描述(设立计数器)#define MAXSIZE 100typedef int ElemType;typedef struct{	ElemType *data;	int front,rear,count;}SqQueue;

基本操作:

         1. 初始化顺序队列(循环队列) Init_SqQueue(SqQueue* Q)

//初始化顺序队列void Init_SqQueue(SqQueue* Q){    Q->data = http://www.mamicode.com/(SqQueue*)malloc(sizeof(SqQueue) * MAXSIZE);>

        2. 销毁顺序队列(循环队列)Destroy_SqQueue(SqQueue* Q)

//销毁顺序队列void Destroy_SqQueue(SqQueue* Q){	if(Q->data){		free(Q->data);		Q->front = Q->rear = Q->count = 0;	}} 

       3. 清空顺序队列(循环队列)Clear_SqQueue(SqQueue* Q)

//清空顺序队列void Clear_SqQueue(SqQueue* Q){	Q->front = Q->rear = Q->count = 0;}

      4. 判断顺序队列(循环队列)是否为空IsEmpty_SqQueue(SqQueue* Q)

//判断顺序队列是否为空int IsEmpty_SqQueue(SqQueue* Q){	return (Q->count == 0);}

       5. 判断顺序队列(循环队列)是否已满 iSFull_SqQueue(SqQueue* Q)

//判断顺序队列是否已满int iSFull_SqQueue(SqQueue* Q){	return (Q->count == MAXSIZE);}


      6. 求得顺序队列(循环队列)的长度GetLength_SqQueue(SqQueue* Q)

//求得顺序队列的长度int GetLength_SqQueue(SqQueue* Q){	return Q->count;}

      7. 取得顺序队列(循环队列)的的队头GetHead_SqQueue(SqQueue* Q,ElemType *x)

//取得顺序队列的的队头void GetHead_SqQueue(SqQueue* Q,ElemType *x){	if(IsEmpty_SqQueue(Q)){		printf("顺序队列空!\n");		exit(0);	}	else{		*x = Q->data[Q->front];	}}

     8. 取得顺序队列(循环队列)的的队尾GetRear_SqQueue(SqQueue* Q,ElemType *x)

//取得顺序队列的的队尾void GetRear_SqQueue(SqQueue* Q,ElemType *x){	if(IsEmpty_SqQueue(Q)){		printf("顺序队列空!\n");		exit(0);	}	else{		*x = Q->data[Q->rear - 1];	}}

      9. 入顺序队列(循环队列)En_SqQueue(SqQueue* Q,ElemType x)

//入顺序队列void En_SqQueue(SqQueue* Q,ElemType x){	if(iSFull_SqQueue(Q)){		printf("顺序队列已满!\n");		exit(0);	}	else{		Q->data[Q->rear] = x;		Q->rear = (Q->rear + 1) % MAXSIZE;		Q->count++;	}	}

      10. 出顺序队列(循环队列)De_SqQueue(SqQueue* Q,ElemType *x)

//出顺序队列void De_SqQueue(SqQueue* Q,ElemType *x){	if(IsEmpty_SqQueue(Q)){		printf("顺序队列空!\n");		exit(0);	}	else{		*x = Q->data[Q->front];		Q->front = (Q->front + 1) % MAXSIZE;		Q->count--;	}	}

       11. 打印顺序队列(循环队列)Print_SqQueue(SqQueue* Q)

//打印顺序队列void Print_SqQueue(SqQueue* Q){	int i = 0;	int j = Q->front;	if(IsEmpty_SqQueue(Q)){		printf("顺序队列空!\n");		exit(0);	}	else{		while(i < Q->count){			printf("%d\t",Q->data[j]);			j = (j + 1) % MAXSIZE;			i++;		}		printf("\n");	}}


     以上,就是附设一个计数器指针来实现循环顺序队列。






 




 

       

 



 

数据结构(C实现)------- 顺序队列(循环队列之计数器实现)