文章目录

• 一：循环队列
• 二：实现
• • （1）结构体定义
  • （2）初始化
  • （3）入队
  • （4）出队
  • （5）返回队头和队尾
• 三：代码

一：循环队列

实现队列要么使用数组，要么使用链表，但由于数组对于出队和入队这样的操作效率不高，所以实现队列一般使用链表。如果现在要求你使用顺序表（也就是顺序队）来实现队列，在不考虑操作的复杂性的情况下肯定是可以实现的，但是这会存在一个致命的问题——“假溢出”。如下，经过一系列入队出队操作，某一刻出现越界。

一旦出现越界，这个队列就等于“报废”了

而解决这个问题可以用到循环队列，循环队列从感觉上讲不是一个直链，而是一个圆环，在某一刻队满时，此时还要入队的话，队头指针便指向第一个元素，重复利用之前的空间

对于普通的顺序队，其判断队满的条件为容量满，对于循环队来说，其判断队空和队满的条件有点不同
首先，队空时自然rear=front，也即下图

而后进队两个元素，进队时arr[rear]=x，然后rear+1如下图

继续入队，入到不能再入为止，此时rear=front，但是前面队空时也有rear=front。

所以为了区分队空和队满，必须牺牲掉一个元素的位置（图中a8）这也就是为什么在申请空间时需要多申请一个原因。如下当元素到达a7时，即为设定的队满状态。此时front=rear+1

在这样一个循环队列中，队列空间为8个，下标范围[0-7]，当rear=7时队满。如果继续入队，rear就不能直接+1了，否则会越界。而要使得rear从rear=7跳到rear=0，可以rear=(rear+1)%8，因为任何一个数对8取余，其结果都会被映射在[0-7]内。同时为了统一操作，将所有的rear=rear+1均改为rear=(rear+1)%8。

所以说队空rear=front；队满front=(rear+1)%MaxSize;移动指针rear=(rear+1)%MaxSize和front=(front+1)%MaxSize;

二：实现

（1）结构体定义

（2）初始化

（3）入队

（4）出队

（5）返回队头和队尾

三：代码

CircularQueue.h

#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h>typedef int DataType;typedef struct CircularQueue {int _front;int _rear;DataType* _arr;}CircularQueue;void CircularQueueInit(CircularQueue* pq);//初始化 void CircularQueuePush(CircularQueue* pq, DataType x);//入队 void CircularQueuePop(CircularQueue* pq);//删除 DataType CircularQueueHead(CircularQueue* pq);//队头 DataType CircularQueueTail(CircularQueue* pq);//队头

CircularQueue.c

#include "CircularQueue.h"void CircularQueueInit(CircularQueue* pq) {pq->_front = 0;pq->_rear = 0;pq->_arr = (DataType*)malloc(sizeof(DataType)*(8+1)); }void print(CircularQueue* pq) {assert(pq);int cur = pq->_front;while (cur != pq->_rear){printf("%d ", pq->_arr[cur]);cur = (cur + 1) % 9;}}void CircularQueuePush(CircularQueue* pq, DataType x) {assert(pq);if ((pq->_rear + 1) % 9 == pq->_front)return;pq->_arr[pq->_rear] = x;pq->_rear = (pq->_rear + 1) % 9; } void CircularQueuePop(CircularQueue* pq) {assert(pq);if (pq->_rear == pq->_front)return;pq->_front=(pq->_front + 1) % 9; } DataType CircularQueueHead(CircularQueue* pq) {assert(pq);if (pq->_rear == pq->_front)exit(-1);return pq->_arr[pq->_front];} DataType CircularQueueTail(CircularQueue* pq) {assert(pq);if (pq->_rear == pq->_front)exit(-1);else{int cur = pq->_front;while ((cur + 1) % 9 != pq->_rear)cur = cur++;return pq->_arr[cur];}}

test.c

#include "CircularQueue.h"void test() {CircularQueue CQ;CircularQueueInit(&CQ);CircularQueuePush(&CQ, 1);CircularQueuePush(&CQ, 2);CircularQueuePush(&CQ, 3);CircularQueuePush(&CQ, 4);print(&CQ);printf("\n");CircularQueuePop(&CQ);print(&CQ);printf("\n");printf("队头元素是%d \n", CircularQueueHead(&CQ));printf("队尾元素是%d \n", CircularQueueTail(&CQ));} int main() {test(); }

总结

以上是生活随笔为你收集整理的数据结构-线性表之循环队列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。