/* 1、队列:一端进,另一端出;队列由两个参数决定,front(头),rear(尾); 头指针指向头一个元素,尾指针指向指向最后一个元素的下一存储单元;若数组长度为n,当元素个数为n-1时就认为队列已满。r指向最后一个空的元素空间。 出队:头指针往上移动, 入队:尾指针向上移动,故:静态队列只能是循环队列,不然出队的元素占用的空间 永远无法重复利用。 1):队列的初始化:front,rear的值都是零、 2):队列非空:front代表的是队列的第一个元素,rear代表的是队列的最后一个元素的下个存储单元 3) :队列空:front和rear的值相等,但不一定是零 4):动态队列:链表实现 静态队列:数组实现 2、循环队列: 出队:f = (f+1) % 数组长度 入队:r = (r+1) % 数组长度 +++++++++++++++++++++ + + + +<----r + + +++++++++++++++++++++ + + + c + + + +++++++++++++++++++++ + + + b + + + +++++++++++++++++++++ + + f --->+ a + + + +++++++++++++++++++++ 如何判断循环队列是否为空: 如果f == r 就一定为空 如何判断队列已满: 1)增加一个标志n记录队列元素的个数,当n = 数组长度-1时,就满了。 2)if((r+1)%arr.length == f){ 队列已满 } 通常使用第二种 队列的具体应用: 所有和时间有关的操作都有队列的影子。 */ #include#include //静态循环队列(数组实现)程序演示 typedef struct Queue { int length; int *pBase; int front; int rear; }QUEUE,* PQUEUE; //初始化队列 void init(PQUEUE pQ,int length); //判断队列是否已满 bool is_full(PQUEUE pQ); //判断队列是否为空 bool is_empty(PQUEUE pQ); //遍历 void traverse(PQUEUE pQ); //入队 r = (r+1) % 数组长度 bool en_queue(PQUEUE pQ,int val); //出队 f = (f+1) % 数组长度 bool de_queue(PQUEUE pQ,int * val); int main(void) { QUEUE q; init(&q,6); en_queue(&q,1); en_queue(&q,2); en_queue(&q,3); en_queue(&q,4); en_queue(&q,5); traverse(&q); int a = 0; de_queue(&q,&a); printf("出队的元素是:%d\n",a); traverse(&q); getchar(); return 0; } //初始化队列 void init(PQUEUE pQ,int length) { //分配内存 pQ->pBase =(int *) malloc(sizeof(int) * length); pQ->length = length; pQ->front = 0; pQ->rear = 0; //下标的都是0 } //判断队列是否已满 bool is_full(PQUEUE pQ) { if((pQ->rear + 1) % (pQ->length) == pQ->front) { return true; } else { return false; } } //判断队列是否为空 bool is_empty(PQUEUE pQ) { if(pQ->front == pQ->rear) { return true; }else { return false; } } //入队 bool en_queue(PQUEUE pQ,int val) { if(is_full(pQ)) { printf("队列已满\n"); return false; } pQ->pBase[pQ->rear] = val; //入队,尾角标增加 pQ->rear = (pQ->rear+1)%(pQ->length); return true; } //出队 bool de_queue(PQUEUE pQ,int * val) { if(is_empty(pQ)){ printf("队列已空"); return false; } *val = pQ->pBase[pQ->front]; pQ->front = (pQ->front + 1) % (pQ->length); return true; } //遍历 void traverse(PQUEUE pQ) { int i = pQ->front; while(i !=pQ->rear) { printf("%d\t",pQ->pBase[i]); i = (i + 1) % (pQ->length); } }