环形队列(图解) |
您所在的位置：网站首页 › 环形队列有什么应用场景和特点呢 › 环形队列(图解) |
环形队列(图解)
|
文章目录
环形队列概念:环形队列的实现：循环队列基本功能判满与判空入元素和出元素去除循环队列队头队尾元素
总代码增加size变量代码
环形队列概念:
队列的特性: 先进先出,环形队列也不例外,只不过这里的队尾指向队头,所以环形队列也叫"环形缓冲器",同时环形队列的大小是固定的,它可以重复利用某一位置。 环形队列的实现：环形队列分两种: 链表和数组,这里我们写的是数组的实现方法 我们定义两个变量front和rear,一个指向队头一个指向队尾,每次插入元素的时候rear就++指向下一个位置,这里跟我们顺序表的插入其实是一样的,只不过当rear == n(数组长度-这里我们循环队列的长度是固定的), rear == n的时候我们应该让rear返回到下标为0的位置,或者可以直接对数组长度取模。 循环队列基本功能 入元素(队尾)出元素(队头)判空判满返回队头元素返回队尾元素 判满与判空不过这样写的话会有个问题,就是判空和判满如何判断?,判空简单,判断front是否等于rear就可以了,但如果按照我们上面那个思路的话,当rear+1此时等于n再取模的时候变为0,但是此时数组元素是满的 如下图: 这里我们写第二种,第一种我放在文章末尾了 这里我们多开辟一个空间的目的就是防止判空与判满冲突,只要我们的rear+1再对数组长度+1取模等于我们的front就相当于满了,由于之前我们没有多开辟一个空间的时候是直接对数组长度取模,这里多开辟的一个就是对数组长度+1取模 入元素和出元素由于队列的特性是:队头入,队尾出。 队头出: 只要我们的front还小于数组长度+1(由于我们多开了一个空间,所以我们此时的长度为原数组长度+1),那我们就可以放心的直接front++,否则我们就要让front++的值对数组长度+1取模 队尾入也是一样的,只需要当rear等于数组+1的时候要对数组加一取模 动图演示: 取队头元素简单,直接取front位置的元素即可 重点是取队尾元素: 1.rear > 0 如果此时rear == 0,rear-1就为-1,这样就会导致数组越界,所以我们取(rear-1+SIZE+1）%(SIZE+1)位置的元素,此时即便rear = 0,那我们取得也是最后一个元素,同时rear > 0的时候也是满足条件的。 头文件 typedef int CDataType; //2.多开辟一个空间 typedef struct Cicle { CDataType* data; int K;//存储数组内的元素个数 int front; int rear; }Cicle; #define SIZE 4 //初始化循环队列 void CilcleInit(Cicle* pc); //入队列 void CiclePush(Cicle* pc,CDataType x); //队头出队列 void CiclePop(Cicle* pc); //判满 bool CicleEmpty(Cicle* pc); //判空 bool CicleIsFull(Cicle* pc); //返回队头元素 CDataType CicleFront(Cicle* pc); //销毁循环队列 CicleDesTory(Cicle* pc); //队列有效元素个数 int CicleSize(Cicle* pc); //返回队尾元素 CDataType CircleRear(Cicle* pc);源文件 //初始化循环队列 void CilcleInit(Cicle* pc) { pc->data = (CDataType*)calloc(SIZE+1, sizeof(CDataType)); pc->front = pc->rear = 0; pc->K = SIZE; } //判满 bool CicleIsFull(Cicle* pc) { return (pc->rear + 1)%(pc->K+1) == pc->front; } //判空 bool CicleEmpty(Cicle* pc) { return pc->front == pc->rear; } //队尾入队列 void CiclePush(Cicle* pc, CDataType x) { assert(pc && !CicleIsFull(pc));//没有满 pc->data[pc->rear] = x; pc->rear = (pc->rear + 1) % (pc->K+1); } //队头出队列 void CiclePop(Cicle* pc) { assert(pc && !CicleEmpty(pc)); pc->front = (pc->front + 1) % (pc->K + 1); } //返回队头元素 CDataType CicleFront(Cicle* pc) { assert(pc && !CicleEmpty(pc)); return pc->data[pc->front]; } //返回队列有效长度 int CicleSize(Cicle* pc) { assert(pc); //pc->k == SIZE 表示数组内的元素个数 //SIZE+1则为我们实际开辟的空间 return (pc->rear - pc->front + (pc->K + 1))%(pc->K+1); } //返回队尾元素 CDataType CircleRear(Cicle* pc) { assert(pc && !CicleEmpty(pc)); return pc->data[(pc->rear - 1 + (pc->K + 1)) % (pc->K + 1)]; } //销毁循环队列 CicleDesTory(Cicle* pc) { assert(pc); free(pc->data); pc->data = NULL; pc->front = pc->rear = pc->K = 0; } 增加size变量代码头文件 //1.增加size变量 typedef struct Cicle { CDataType* data; int size; int front; int rear; }Cicle; //2.多开辟一个空间 typedef struct Cicle { CDataType* data; int K;//存储数组内的元素个数 int front; int rear; }Cicle; #define SIZE 4 //初始化循环队列 void CilcleInit(Cicle* pc); //入队列 void CiclePush(Cicle* pc,CDataType x); //队头出队列 void CiclePop(Cicle* pc); //判满 bool CicleEmpty(Cicle* pc); //判空 bool CicleIsFull(Cicle* pc); //返回队头元素 CDataType CicleFront(Cicle* pc); //销毁循环队列 CicleDesTory(Cicle* pc); //队列有效元素个数 int CicleSize(Cicle* pc); //返回队尾元素 CDataType CircleRear(Cicle* pc);源文件 1.增加size变量 //初始化循环队列 void CilcleInit(Cicle* pc) { pc->data = (CDataType*)calloc(SIZE, sizeof(CDataType)); pc->front = pc->rear = pc->size = 0; } //判满 bool CicleIsFull(Cicle* pc) { return pc->size == SIZE; } //判空 bool CicleEmpty(Cicle* pc) { return pc->front == pc->rear; } //队尾入队列 void CiclePush(Cicle* pc, CDataType x) { assert(pc && !CicleIsFull(pc));//没有满 pc->data[pc->rear] = x; pc->rear = (pc->rear + 1) % SIZE; pc->size++; } //队头出队列 void CiclePop(Cicle* pc) { assert(pc && !CicleEmpty(pc)); pc->front = (pc->front + 1)%SIZE; pc->size--; } //返回队头元素 CDataType CicleFront(Cicle* pc) { assert(pc && !CicleEmpty(pc)); return pc->data[pc->front]; } //返回队列有效长度 int CicleSize(Cicle* pc) { assert(pc); return pc->size; } //返回队尾元素 CDataType CircleRear(Cicle* pc) { assert(pc && !CicleEmpty(pc)); return pc->data[(pc->rear - 1 + SIZE)%SIZE]; } //销毁循环队列 CicleDesTory(Cicle* pc) { assert(pc); free(pc->data); pc->data = NULL; pc->front = pc->rear = pc->size = 0; } |
这里有两种解决方案:
队尾入:
综上: 我们取队尾元素的时候可以都直接让rear-1再加上数组长度+1再对他取模(数组长度+1)就可以得到准确的位置了。【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |