数据结构 ——— 队列oj题：设计循环队列

目次
标题要求
代码思路
代码实现

---

标题要求

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则而且队尾被毗连在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，纵然在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
  
• Front: 从队首获取元素。如果队列为空，返回 -1 。
  
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
  
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  
• isEmpty(): 检查循环队列是否为空。
  

---

代码思路

定义一个 front 和 rear 指针；front 指针用来指向队头，rear 指针用来指向队尾
定义一个整型变量 k ，用来记录队列的长度
利用序次表的结构实现循环队列
要包管留一个空间置空，不存储数据，用来判断队列是否是满的
当 rear + 1 == front 时，队列就是满的，但是 rear + 1 可能会导致下标越界
以是可以根据 (rear + 1)% (k + 1) == front 判断是否满
队头出数据时，就将 front++ 即可

---

代码实现

1. typedef int QDataType;
3. typedef struct
4. {
5.         int front; //指向队头的下标
7.         int rear; //指向队尾的下标
9.         int k; //队列有效数据个数（除去多开的一个空间）
11.         QDataType* a; //指向队列空间的指针
13. } MyCircularQueue;
15. // 初始化
16. MyCircularQueue* myCircularQueueCreate(int k)
17. {
18.         MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
20.         // 判断是否开辟成功
21.         if (obj == NULL)
22.         {
23.                 perror("malloc fail");
24.                 return NULL;
25.         }
27.         // 多开一个空间，用来判空和判满
28.         obj->a = (QDataType*)malloc(sizeof(QDataType) * (k + 1));
30.         // 判断是否开辟成功
31.         if (obj->a == NULL)
32.         {
33.                 perror("malloc fail");
34.                 return NULL;
35.         }
37.         obj->front = 0;
38.         obj->rear = 0;
39.         obj->k = k;
41.         return obj;
42. }
44. // 插入数据
45. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
46. {
47.         // 先判满
48.         if (myCircularQueueIsFull(obj))
49.                 return false;
51.         // 插入数据
52.         obj->a[obj->rear] = value;
53.         obj->rear++;
55.         // 防止 rear 越界
56.         if (obj->rear == obj->k + 1)
57.         {
58.                 obj->rear = 0;
59.         }
61.         return true;
62. }
64. // 删除数据
65. bool myCircularQueueDeQueue(MyCircularQueue* obj)
66. {
67.         // 先判空
68.         if (myCircularQueueIsEmpty(obj))
69.                 return false;
71.         // 删除数据
72.         obj->front++;
74.         // 防止 front 越界
75.         if (obj->front == obj->k + 1)
76.         {
77.                 obj->front = 0;
78.         }
80.         return true;
81. }
83. // 访问队头数据
84. int myCircularQueueFront(MyCircularQueue* obj)
85. {
86.         // 先判空
87.         if (myCircularQueueIsEmpty(obj))
88.                 return -1;
90.         return obj->a[obj->front];
91. }
93. // 访问队尾数据
94. int myCircularQueueRear(MyCircularQueue* obj)
95. {
96.         // 先判空
97.         if (myCircularQueueIsEmpty(obj))
98.                 return -1;
100.         if (obj->rear == 0)
101.         {
102.                 return obj->a[obj->k];
103.         }
104.         else
105.         {
106.                 return obj->a[obj->rear - 1];
107.         }
108. }
110. // 判空
111. bool myCircularQueueIsEmpty(MyCircularQueue* obj)
112. {
113.         return obj->front == obj->rear;
114. }
116. // 判满
117. bool myCircularQueueIsFull(MyCircularQueue* obj)
118. {
119.         return (obj->rear + 1) % (obj->k + 1) == obj->front;
120. }
122. // 释放
123. void myCircularQueueFree(MyCircularQueue* obj)
124. {
125.         free(obj->a);
126.         free(obj);
127. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。