轻应用网站模板,wordpress 小工具插件下载,东莞公司网站制作,稼禾建设集团网站前言 循环队列是队列的一种特殊的结构#xff0c;在生产者——消费者模型中常常使用它#xff0c; 它在逻辑上是一个环形的连续的结构。在物理可以使用数组来实现。
目录
1.循环队列的逻辑结构
2.空的循环队列和满的循环队列
3.循环队列插入和删除
4.代码实现 …前言 循环队列是队列的一种特殊的结构在生产者——消费者模型中常常使用它 它在逻辑上是一个环形的连续的结构。在物理可以使用数组来实现。
目录
1.循环队列的逻辑结构
2.空的循环队列和满的循环队列
3.循环队列插入和删除
4.代码实现 1.循环队列的逻辑结构 循环队列在逻辑上连续的。
2.空的循环队列和满的循环队列 因为是采用数组进行队列的实现的如果是存储N个数据的队列需要开辟N 1个空间当队头指针Front等于队尾指针rear时队列为空。当队尾指针 rear1%N 1 1等于队头指针时此时队列为满为什么队尾指针要对N 1进行取模运算呢因为数组是连续的当循环队列的尾指针走到数组的末尾时需要从数组下标为零的位置重新开始。不然数组的访问就会越界对于头指针来说也是一样的。如图 3.循环队列插入和删除 循环队列和队列一样也是在队头插入数据队尾删除数据。需要注意的是如果队头已经在数组的末尾了这时候删除掉队头的元素队头的指针要更新到数组下标为零的元素也就是frontfront1。那么下一次队列删除的就是数组的第一个元素如图 插入元素也是一样的如果rear超过了数组的长度以后要回到开始的位置。 为什么给数组开空间的时候要多开一个呢因为始终要留出一个空位来不然无法确定队列满的条件。
4.代码实现 typedef struct
{int* _array;int _front;int _rear;int _k;
} MyCircularQueue;bool myCircularQueueIsFull(MyCircularQueue* obj);//判断队列是否满了。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断队列是否为空MyCircularQueue* myCircularQueueCreate(int _k) {MyCircularQueue* qu (MyCircularQueue*)malloc(sizeof(MyCircularQueue));qu-_array (int*)malloc(sizeof(int) * (_k 1));//多开一个qu-_front qu-_rear 0;//初始化指针qu-_k _k 1;return qu;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//入数据
{if (obj NULL)return false;//队列为空直接返回//如果队列满了也就不能插入元素了if (myCircularQueueIsFull(obj)){return false;}else{//队尾入数据obj-_array[obj-_rear] value;(obj-_rear);obj-_rear obj-_rear % (obj-_k);//确保rear是在合适的位置return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* obj) //队头出数据
{if (obj NULL)return false;if (obj-_front obj-_rear)//队列为空时不能出数据return false;(obj-_front);obj-_front % (obj-_k);//确保front不会越界return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))//队列为空返回-1return -1;return obj-_array[obj-_front];
}
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))//队列为空返回-1return -1;int tail obj-_rear - 1;if (tail -1)//如果tail为-1说明这时候rear在数组的开头需要出队尾的元素在数组的末尾tail obj-_k - 1;return obj-_array[tail];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-_front obj-_rear;//rear等于front时队列为空
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return ((obj-_rear 1) % obj-_k obj-_front); //rear 1等于front说明队列满了
}void myCircularQueueFree(MyCircularQueue* obj) {if (obj NULL)return;//确保指针存在free(obj-_array);//先释放开辟的数组free(obj);
} 原题链接循环队列的实现 如果大家有兴趣的尝试一下。
