数据结构（C语言） 循环队列的表示和实现

循环队列

当队列不可再继续插入新的队尾元素（数组越界），此事又不宜进行存储再分配扩大数组空间，队列实际空间未占满，巧妙的办法就是将顺序队列臆造为一个环状的空间。

循环队列的存储结构

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

基本操作的函数原型说明

Status InitQueue(SqQueue& Q); //构造一个空队列Q int QueueLength(SqQueue Q); //返回Q的元素个数，即队列的长度 Status EnQueue(SqQueue& Q, QElemType e); //插入元素e为Q的新的队尾元素 Status DeQueue(SqQueue& Q, QElemType& e); //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR void PrintQueue(SqQueue Q); //打印队列

基本操作的函数原型说明

//----基本操作的函数原型说明---- Status InitQueue(SqQueue& Q); //构造一个空队列Q int QueueLength(SqQueue Q); //返回Q的元素个数，即队列的长度 Status EnQueue(SqQueue& Q, QElemType e); //插入元素e为Q的新的队尾元素 Status DeQueue(SqQueue& Q, QElemType& e); //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR void PrintQueue(SqQueue Q); //打印队列 //----基本操作的算法描述---- Status InitQueue(SqQueue& Q) { Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType)); if (!Q.base) exit(OVERFLOW);//存储分配失败 Q.front = Q.rear = 0; return OK; } int QueueLength(SqQueue Q) { return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; } Status EnQueue(SqQueue& Q, QElemType e) { if ((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE; return OK; } Status DeQueue(SqQueue& Q, QElemType& e) { if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE; return OK; } void PrintQueue(SqQueue Q) { printf("队列为："); int n = Q.front; for (int i = 0; i < QueueLength(Q); i++)//循环次数 { printf("%d ", Q.base[n++ % MAXQSIZE]); } printf("\n"); }

完整代码

#include<stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define MAXQSIZE 3 //Status是函数的类型，其值是函数结果状态代码 typedef int Status; typedef int QElemType; //----循环队列---- typedef struct { QElemType* base;//初始化的动态分配存储空间 int front;//头指针，若队列不空，指向队列头元素 int rear;//尾指针，若队列不空，指向队列尾元素的下一个位置 }SqQueue; //----基本操作的函数原型说明---- Status InitQueue(SqQueue& Q); //构造一个空队列Q int QueueLength(SqQueue Q); //返回Q的元素个数，即队列的长度 Status EnQueue(SqQueue& Q, QElemType e); //插入元素e为Q的新的队尾元素 Status DeQueue(SqQueue& Q, QElemType& e); //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR void PrintQueue(SqQueue Q); //打印队列 //----基本操作的算法描述---- Status InitQueue(SqQueue& Q) { Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType)); if (!Q.base) exit(OVERFLOW);//存储分配失败 Q.front = Q.rear = 0; return OK; } int QueueLength(SqQueue Q) { return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; } Status EnQueue(SqQueue& Q, QElemType e) { if ((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE; return OK; } Status DeQueue(SqQueue& Q, QElemType& e) { if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE; return OK; } void PrintQueue(SqQueue Q) { printf("队列为："); int n = Q.front; for (int i = 0; i < QueueLength(Q); i++)//循环次数 { printf("%d ", Q.base[n++ % MAXQSIZE]); } printf("\n"); } int main() { SqQueue Q; InitQueue(Q); EnQueue(Q, 1); EnQueue(Q, 2); int n; DeQueue(Q, n); EnQueue(Q, 5); printf("Q.front=%d Q.rear=%d\n", Q.front,Q.rear); PrintQueue(Q); return 0; }