用链表实现循环队列（c语言版本）
·
1.1基本思路
用链表实现定义一个结构体，存放head，tail，size，capacity
其中size的目的是为了统计节点的个数，方便判断循环队列是否满或者空
push走tail，pop走head
1.2实现各个函数
下边是各个函数的声明
// 创建新节点
Node* createNode(QDataType data);
// 创建循环队列，初始化容量为 k
MyCircularQueue* myCircularQueueCreate(int k);
// 向队列插入元素，成功返回 true，失败（队列满）返回 false
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);
// 从队列删除元素，成功返回 true，失败（队列空）返回 false
bool myCircularQueueDeQueue(MyCircularQueue* obj);
// 获取队头元素，队列为空返回 -1
int myCircularQueueHead(MyCircularQueue* obj);
// 获取队尾元素，队列为空返回 -1
int myCircularQueueTail(MyCircularQueue* obj);
// 判断队列是否为空，空返回 true，否则返回 false
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
// 判断队列是否已满，满返回 true，否则返回 false
bool myCircularQueueIsFull(MyCircularQueue* obj);
// 释放队列占用的内存
void myCircularQueueFree(MyCircularQueue* obj);
1.2.1创建并且初始化
一开始是将创建节点和创建循环队列需要的变量放在一个结构体中，方便后边传参
typedef int QDataType;
//创建节点的结构体
typedef struct Node {
QDataType data; // 存储数据
struct Node* next; // 指向下一个节点的指针
} Node;
// 循环队列结构体定义
typedef struct {
Node* head; // 放头位置
Node* tail; // 放尾位置
int size; // 统计节点的个数
int capacity;
} MyCircularQueue;
接着是创建节点和初始化节点的函数
Node* createNode(QDataType data)// 创建一个新节点
{
Node* newnode = (Node*)malloc(sizeof(Node));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = data;
newnode->next = NULL;
return newnode;
}
再然后是创建循环队列和初始化的函数
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
if (obj == NULL)
{
perror("malloc fail");
return NULL;
}
obj->capacity = k;
obj->size = 0;
obj->head = obj->tail = NULL;
return obj;
}
1.2.2插入元素
一开始一定要判断是否传入的空，还有此循环链表是否已满（这是插入元素的前提条件）
如果再插入元素之前是空队列，则插入newnode等于head等于tail，然后自己形成循环
如果不为空，就于原本的链表连接在一起，并且tail移动到newnode上
最后别忘记让size+1
下边是插入元素的完整函数代码
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
assert(obj);
if (myCircularQueueIsFull(obj))
{
return false;
}
Node* newnode = createNode(value);
if (myCircularQueueIsEmpty(obj)) // 如果原本是空链表 则创建的节点自己形成循环
{
newnode->next = newnode;
obj->tail = obj->head = newnode;
}
else
{
newnode->next = obj->tail->next;
obj->tail->next = newnode;
obj->tail = newnode;//更新未节点
}
obj->size++;
return true;
}
1.2.3删除元素
前提条件：传入的不为空，循环队列不为空
思路：如果只有一个元素，则直接删除释放
如果不止一个元素，就删除head所在位置的元素，并且更新head的值，指向下一个节点
记得要对size - 1
下边是删除元素的完整代码
bool myCircularQueueDeQueue(MyCircularQueue* obj)// 这里的出队就相当于删除了这个节点
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
{
return false;
}
//如果只有一个节点那就直接释放
if (obj->size == 1)
{
free(obj->tail);
obj->tail = NULL;
}
else
{
Node* current = obj->head;
obj->tail->next = obj->head->next;
obj->head = obj->head->next;//这里是更新这个头节点
free(current);//一定要记得释放 不然开辟的空间多了会出错
}
obj->size--;
return true;
}
1.2.4返回头元素
这里的思路简单，就是如果循环队列为空，就不存在头元素，则输出false
如果不为空，就直接返回head位置放的data
int myCircularQueueHead(MyCircularQueue* obj)
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->head->data;
}
1.2.5返回尾元素
与返回头元素的思路基本相似，就是返回的是tail位置放的data
int myCircularQueueTail(MyCircularQueue* obj)
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->tail->data;
}
1.2.6判断是否为空
这里就发挥了size的作用，如果size为0，就返回true，则就是空
反之返回false，则不为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
assert(obj);
return obj->size == 0;
}
1.2.7判断是否已满
与判断是否为空思路相似
就是判断size与capacity是否相等
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
assert(obj);
return obj->size == obj->capacity;
}
1.2.8销毁循环队列
这里的销毁不能直接释放obj，还得将节点一个一个释放，防止内存泄露
void myCircularQueueFree(MyCircularQueue* obj)
{
assert(obj);
// 空队列直接释放结构体
if (obj->head == NULL)
{
free(obj);
return;
}
// 循环释放所有节点（从头部开始，直到回到起点）
Node* current = obj->head;
while (current->next != obj->head)
{
Node* next = current->next;
free(current);
current = next;// 这里就的物理意义就是实现++
}
free(current);
free(obj);
}
1.3完整代码和测试用例代码
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int QDataType;
//创建节点的结构体
typedef struct Node {
QDataType data; // 存储数据
struct Node* next; // 指向下一个节点的指针
} Node;
// 循环队列结构体定义
typedef struct {
Node* head;
Node* tail;
int size;
int capacity;
} MyCircularQueue;
// 创建新节点
Node* createNode(QDataType data);
// 创建循环队列，初始化容量为 k
MyCircularQueue* myCircularQueueCreate(int k);
// 向队列插入元素，成功返回 true，失败（队列满）返回 false
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);
// 从队列删除元素，成功返回 true，失败（队列空）返回 false
bool myCircularQueueDeQueue(MyCircularQueue* obj);
// 获取队头元素，队列为空返回 -1
int myCircularQueueHead(MyCircularQueue* obj);
// 获取队尾元素，队列为空返回 -1
int myCircularQueueTail(MyCircularQueue* obj);
// 判断队列是否为空，空返回 true，否则返回 false
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
// 判断队列是否已满，满返回 true，否则返回 false
bool myCircularQueueIsFull(MyCircularQueue* obj);
// 释放队列占用的内存
void myCircularQueueFree(MyCircularQueue* obj);
Node* createNode(QDataType data)// 创建一个新节点
{
Node* newnode = (Node*)malloc(sizeof(Node));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = data;
newnode->next = NULL;
return newnode;
}
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
if (obj == NULL)
{
perror("malloc fail");
return NULL;
}
obj->capacity = k;
obj->size = 0;
obj->head = obj->tail = NULL;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
assert(obj);
if (myCircularQueueIsFull(obj))
{
return false;
}
Node* newnode = createNode(value);
if (myCircularQueueIsEmpty(obj)) // 如果原本是空链表 则创建的节点自己形成循环
{
newnode->next = newnode;
obj->tail = obj->head = newnode;
}
else
{
newnode->next = obj->tail->next;
obj->tail->next = newnode;
obj->tail = newnode;//更新未节点
}
obj->size++;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)// 这里的出队就相当于删除了这个节点
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
{
return false;
}
//如果只有一个节点那就直接释放
if (obj->size == 1)
{
free(obj->tail);
obj->tail = NULL;
}
else
{
Node* current = obj->head;
obj->tail->next = obj->head->next;
obj->head = obj->head->next;//这里是更新这个头节点
free(current);//一定要记得释放 不然开辟的空间多了会出错
}
obj->size--;
return true;
}
int myCircularQueueHead(MyCircularQueue* obj)
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->head->data;
}
int myCircularQueueTail(MyCircularQueue* obj)
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->tail->data;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
assert(obj);
return obj->size == 0;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
assert(obj);
return obj->size == obj->capacity;
}
void myCircularQueueFree(MyCircularQueue* obj)
{
assert(obj);
// 空队列直接释放结构体
if (obj->head == NULL)
{
free(obj);
return;
}
// 循环释放所有节点（从头部开始，直到回到起点）
Node* current = obj->head;
while (current->next != obj->head)
{
Node* next = current->next;
free(current);
current = next;// 这里就的物理意义就是实现++
}
free(current);
free(obj);
}
// 示例用法
int main() {
MyCircularQueue* q = myCircularQueueCreate(3); // 创建容量为3的循环队列
myCircularQueueEnQueue(q, 1);
myCircularQueueEnQueue(q, 2);
myCircularQueueEnQueue(q, 3);
printf("队头: %d, 队尾: %d\n", myCircularQueueFront(q), myCircularQueueRear(q)); // 1, 3
myCircularQueueDeQueue(q);
myCircularQueueEnQueue(q, 4);
printf("队头: %d, 队尾: %d\n", myCircularQueueFront(q), myCircularQueueRear(q)); // 2, 4
myCircularQueueFree(q);
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
5
0- 0
已为社区贡献1条内容
所有评论(0)