一个用单链表组成的循环队列只设一个尾指针不设头指针,请编写向循环队列中插入一个元素为x的结点和从循环队列中删除一个结点
时间: 2024-05-12 07:16:22 浏览: 26
插入结点操作:
1. 新建一个结点,将元素值 x 存入结点。
2. 判断队列是否已满,如果尾指针指向的结点的下一个结点是头结点,则队列已满,不能插入新结点。
3. 将结点插入尾部,将尾指针指向新结点的下一个结点。
删除结点操作:
1. 判断队列是否为空,如果尾指针指向的结点是头结点,则队列为空,不能删除结点。
2. 获取头结点,并将其删除。
3. 将头指针指向头结点的下一个结点。
代码实现:
```
// 定义单链表结点
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
typedef struct {
ListNode* tail; // 尾指针
} MyCircularQueue;
/** 初始化队列 */
MyCircularQueue* myCircularQueueCreate() {
MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
q->tail = NULL;
return q;
}
/** 插入元素 */
bool myCircularQueueEnQueue(MyCircularQueue* obj, int x) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = x;
node->next = NULL;
if (obj->tail == NULL) { // 队列为空
obj->tail = node;
obj->tail->next = obj->tail; // 队列只有一个元素,需要让尾结点指向自己
return true;
}
if (obj->tail->next == obj->tail) { // 队列只有一个元素
obj->tail->next = node;
node->next = obj->tail;
obj->tail = node;
return true;
}
// 队列有两个及以上元素
ListNode* head = obj->tail->next;
if (obj->tail == head) { // 队列已满
return false;
}
obj->tail->next = node;
node->next = head;
obj->tail = node;
return true;
}
/** 删除元素 */
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (obj->tail == NULL) { // 队列为空
return false;
}
ListNode* head = obj->tail->next;
if (head == obj->tail) { // 队列只有一个元素
obj->tail = NULL;
free(head);
return true;
}
obj->tail->next = head->next;
free(head);
return true;
}
/** 判断队列是否为空 */
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->tail == NULL;
}
/** 判断队列是否已满 */
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if (obj->tail == NULL) {
return false;
}
return obj->tail->next == obj->tail;
}
/** 释放队列所占内存 */
void myCircularQueueFree(MyCircularQueue* obj) {
if (obj == NULL) {
return;
}
ListNode* p = obj->tail;
while (p != NULL) {
ListNode* q = p->next;
free(p);
p = q;
if (q == obj->tail) {
break;
}
}
free(obj);
}
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)