2.2队列的实现
队列的实现也同样有两种选择：数组，链表。二者相比之下，链表更好些，因为链表的特点头删的效率很高。
数据入队，尾部插入
数据出队，头部删除
定义结构体和类型
为了方便数据的增删查改，这里定义队列的头尾指针
typedef int Queuedatatype; typedef struct Queuenode { struct Queuenode* next; Queuedatatype data; }QEnode; typedef struct Queue { QEnode* head;//队首指针 QEnode* tail;//队尾指针 int size;//用于记录队列中数据个数 }QE;
队列的初始化
//初始化队列 void QEinit(QE* p); void QEinit(QE* p) { assert(p); p->size = 0; p->head = p->tail = NULL; }
队列的销毁
//销毁队列 void QEdestory(QE* p); void QEdestory(QE* p) { assert(p); QEnode* cur = p->head; while (cur) { QEnode* del = cur; cur = cur->next; free(del); } p->head = p->tail = NULL; p->size = 0; }
数据从队尾插入队列
//数据插入队列 void QEpush(QE* p,Queuedatatype x); void QEpush(QE* p,Queuedatatype x) { assert(p); QEnode* newnode = (QEnode*)malloc(sizeof(QEnode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } else { newnode->data = x; newnode->next = NULL; } if (p->tail == NULL) { p->head = p->tail = newnode; } else { p->tail->next = newnode; p->tail = p->tail->next; } p->size++; }
将三个数据从队尾插入队列中，监视如下，此时size==3,表示队列中已经插入三个数据
读取队首数据
//读取队首数据 Queuedatatype QEfront(QE* p); Queuedatatype QEfront(QE* p) { assert(p); assert(!QEempty(p)); return p->head->data; }
读取队尾数据
//读取队尾数据 Queuedatatype QEback(QE* p); Queuedatatype QEback(QE* p) { assert(p); assert(!QEempty(p)); return p->tail->data; }
检查队列是否为空
//检查队列是否为空 bool QEempty(QE* p); bool QEempty(QE* p) { assert(p); return p->head == NULL && p->tail == NULL; }
数据从队首删除
//数据出队列 void QEpop(QE* p); void QEpop(QE* p) { assert(p); assert(!QEempty(p)); if (p->head->next == NULL) { free(p->head); p->head = p->tail = NULL; } else { QEnode* del = p->head; p->head = p->head->next; free(del); del = NULL; } p->size--; }
将一个数据从队首删去，此时队列中只剩余两个个数据，监视如下
计算队列中数据的个数
//计算队列中数据的个数 int QEsize(QE* p); int QEsize(QE* p) { assert(p); return p->size; }
2.3扩展
特殊的一种队列：循环队列
同样的道理循环队列的实现也有两种方式：数组，链表
空的环形队列
满的环形队列
既然说到环形队列，不如思考思考如何去实现？
首先实现方式有两种：数组，队列。
由于在读取队尾数据时，如果遇到如下情况，则不能进行读取数据
还需要定义一个位于 back 前一个位置的指针，比较麻烦。
所以采用数组实现环形队列
注意
采用数组实现环形队列，存在一个问题：队列空和队列满无法区分。
解放方法有两个：
创建结构体时，额外加一个用于记录数据个数的变量
额外增加一个空间，队列满时永远留一个空位置
定义结构体
typedef struct { int*a;//数组，用于存储数据 int front;//队头指针 int back;//队尾指针 int n;//环形队列中数据的总数 } MyCircularQueue;
初始化环形队列
MyCircularQueue* myCircularQueueCreate(int k) { //环形队列开辟空间 MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //数组开辟空间 obj->a=(int*)malloc(sizeof(int)*(k+1)); obj->front=obj->back=0; //环形队列的长度 obj->n=k+1; return obj; }
环形队列初始化
MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a=(int*)malloc(sizeof(int)*(k+1)); obj->front=obj->back=0; obj->n=k+1; return obj; }
front指向队头
back指向队尾的下一个位置
检查环形队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->back; }
检查环形队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->back+1)%obj->n==obj->front; }
数据入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) { return false; } obj->a[obj->back]=value; obj->back++; //防止back指针指向数组的最后 //再次++，导致数组越界 obj->back%=obj->n; return true; }
数据出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } obj->front++; obj->front%=obj->n; return true; }
读取队头
int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } else { return obj->a[obj->front]; } }
读取队尾
int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } else { //避免back指针指向队头，向前一个位置访问读取数据时 //导致数组越界 return obj->a[(obj->back-1+obj->n)%(obj->n)]; } }
销毁环形队列
void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
