首页 > 代码库 > 数据结构(C实现)------- 顺序队列(循环队列之少用一个存储空间实现) .
数据结构(C实现)------- 顺序队列(循环队列之少用一个存储空间实现) .
上节已经提到有三种方法来实现循环顺序队列,其中第一种设立标识不常用,最常的就是后两种,上一节已经讨论了用计数器来实现循环顺序队列,这节就用第三种方法,也就是少用一个存储空间来实现循环顺序队列,其基本操作和用计数实现类同,下面是具体实现:
顺序队列(循环队列)类型描述:
//顺序队列的类型描述 #define MAXSIZE 5 typedef int ElemType; typedef struct{ ElemType *data; int front,rear; }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 = 0; } }
3. 清空顺序队列(循环队列)Clear_SqQueue(SqQueue* Q)
void Clear_SqQueue(SqQueue* Q){ Q->front = Q->rear = 0; }
4. 判断顺序队列(循环队列)是否为空IsEmpty_SqQueue(SqQueue* Q)
int IsEmpty_SqQueue(SqQueue* Q){ return (Q->rear == Q->front); }
5. 判断顺序队列(循环队列)是否已满 iSFull_SqQueue(SqQueue* Q)
int iSFull_SqQueue(SqQueue* Q){ return ((Q->rear + 1) % MAXSIZE == Q->front); }
6. 求得顺序队列(循环队列)的长度GetLength_SqQueue(SqQueue* Q)int GetLength_SqQueue(SqQueue* Q){ return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; }
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 + MAXSIZE) % MAXSIZE]; } }
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; } }
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; } }
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 < GetLength_SqQueue(Q)){ printf("%d\t",Q->data[j]); j = (j + 1) % MAXSIZE; i++; } printf("\n"); } }
以上,就是循环顺序队列的另一种实现方法,也就是通过少用一个存储空间,和用计数器实现循环顺序队列的主要区别在判断队列满上。
数据结构(C实现)------- 顺序队列(循环队列之少用一个存储空间实现) .