队列的实现（C语言）

只看该作者 · 2025-2-20 19:37

1.结构体设计
结构说明：使用单链表作为基础的数据结构链表结点存储数据和下一个结点地址

但是队列要可以访问队头和队尾函数需要传两个指针参数所以单独设计一个结构体存储这两个结点指针front和rear

再创建一个size记录队列结点个数

typedef int QueueNodeDataType;
typedef struct QListNode
{
struct QListNode* _pNext;
QueueNodeDataType _data;
}QNode;

typedef struct Queue
{
QNode* _front;
QNode* _rear;
int _size;
}Queue;
2.功能设计
2.1 初始化：将队列的front和rear都置为空队列内有效元素置为0
void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
q->_size = 0;
}
2.2 插入元素设计队尾入队列：判断front为不为空
1.为空则说明front和rear都要置为newNode

2.不为空则说明只需要改变rear即可申请新节点链接到链表中改变rear

void QueuePush(Queue* q, QueueNodeDataType val)
{
assert(q);
QNode* newNode = (QNode*)malloc(sizeof(QNode));
assert(newNode);
newNode->_data = val;
newNode->_pNext = NULL;
if (q->_front == NULL)//队列没有结点
{
q->_front = q->_rear = newNode;
}
else
{
q->_rear->_pNext = newNode;
q->_rear = newNode;
}
q->_size++;
}
2.3 队头出队列：
判断队列为不为空为空则返回不为空分两种情况

1.只有一个结点将front和rear都置为NULL

2.多个结点只将front指向它的下一个结点即可

void QueuePop(Queue* q)
{
assert(q);
if (q->_front == NULL)
{
return;
}
else
{
if (q->_front == q->_rear)//说明只有一个结点
{
free(q->_front);
q->_front = q->_rear = NULL;
}
else
{
QNode* cur = q->_front->_pNext;
free(q->_front);
q->_front = cur;
}
}
q->_size--;
}
2.4 判空：为空返回true 不为空返回false
bool QueueEmpty(Queue* q)
{
assert(q);
return q->_front == NULL;
}
2.5 取队列头元素和取队列尾部元素：判断队列为空的情况
QueueNodeDataType QueueFront(Queue* q)
{
assert(q);
assert(q->_front);
return q->_front->_data;
}
QueueNodeDataType Queuerear(Queue* q)
{
assert(q);
assert(q->_rear);
return q->_rear->_data;
}
2.6 返回队列有效元素个数：返回size
int QueueSize(Queue* q)
{
assert(q);
return q->_size;
}
2.7 销毁队列：遍历队列销毁结点
void QueueDestory(Queue* q)
{
assert(q);
QNode* cur = q->_front;
while (cur)
{
QNode* tmp = cur;
cur = cur->_pNext;
free(tmp);
}
q->_front = q->_rear = NULL;

}
整体代码
Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include<stdbool.h>

typedef int QueueNodeDataType;
typedef struct QListNode
{
struct QListNode* _pNext;
QueueNodeDataType _data;
}QNode;

typedef struct Queue
{
QNode* _front;
QNode* _rear;
int _size;
}Queue;

void QueueInit(Queue* q);
void QueuePush(Queue* q, QueueNodeDataType val);
void QueuePop(Queue* q);
bool QueueEmpty(Queue* q);
int QueueSize(Queue* q);
QueueNodeDataType QueueFront(Queue* q);
QueueNodeDataType Queuerear(Queue* q);
void QueueDestory(Queue* q);
Queue.c
#include"queue.h"
void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
q->_size = 0;
}
void QueuePush(Queue* q, QueueNodeDataType val)
{
assert(q);
QNode* newNode = (QNode*)malloc(sizeof(QNode));
assert(newNode);
newNode->_data = val;
newNode->_pNext = NULL;
if (q->_front == NULL)//队列没有结点
{