信产部网站备案,保定软件开发网站制作,建立网站站点,网站的策划和建设目录
引言
队列的概念与结构
队列的实现
定义
初始化
销毁
入队
判断队列是否为空
出队
获取队头元素
获取队尾元素
检测队列中有效元素个数
元素访问
源代码
queue.h
queue.c
test.c 引言 数据结构之路经过栈后#xff0c;就来到了与栈联系紧密的兄弟—…目录
引言
队列的概念与结构
队列的实现
定义
初始化
销毁
入队
判断队列是否为空
出队
获取队头元素
获取队尾元素
检测队列中有效元素个数
元素访问
源代码
queue.h
queue.c
test.c 引言 数据结构之路经过栈后就来到了与栈联系紧密的兄弟——队列Queue 队列的概念与结构 队列 只允许在一端进行插入数据操作在另一端进行删除数据操作 的特殊线性表队列具有 先进先出 FIFO(First In First Out) 入队列 进行插入操作的一端称为 队尾 出队列 进行删除操作的一端称为 队头 队列的实现 队列 也可以 数组和链表的结构 实现 使用 链表的结构实现更优 一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 定义 队列的实现需要定义两个结构体一个代表节点的信息另一个代表队列的信息因为队列的特性要在一端入另一端出所以要记录头尾指针要不然找尾效率太低了 而size代表当前队列元素个数可加可不加加上更好 初始化 头尾指针置为NULLsize置为0 销毁 队列的销毁本质上就是链表的销毁 创建cur变量循环释放每一个节点直到cur为空最后再将头尾指针置为NULLsize置为0 入队 入队时 先生成新节点因为这里只有入队用到生成新节点所以不用抽离成函数再要分空链表和非空链表进行讨论 空链表判断时加入assert断言防止外部操作错误造成头指针不为空尾指针为空 链表为空时则头尾指针都指向新节点链表不为空时则正常尾插 判断队列是否为空 专门写一个函数判断增强复用性和可读性 。如果size为0则队列为空返回真反之则不为空返回假 出队 出队时先判断队列是否为空保证phead不为NULL防止为空指针的解引用再分单个节点和多个节点来讨论 单个节点则释放头指针指向的节点后头尾指针置为NULL多个节点则正常头删 获取队头元素 获取队尾元素 检测队列中有效元素个数 这里很多函数实现都很简单有些操作直接外部对结构体都可以直接实现但最后还是写成函数封装防止别人使用时对该数据结构不够熟悉导致使用错误 元素访问 队列中元素访问打印不是用函数实现。因为它的特殊结构决定了它的元素不能从任意位置访问 必须符合先进先出原则才可以。所以我们通常用循环的方式进行访问同时每访问一个元素就将它弹出队列再进行下一个元素的访问。 运行结果 队列与栈有所不同因为它先进先出的特性导致顺序只能是1 2 3 4 这样我们就实现了队列的增删等功能 源代码
queue.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
//检测队列中有效元素个数
int QueueSize(Queue* pq);
//检测队列是否为空
bool QueueEmpty(Queue* pq);
queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#includequeue.hvoid QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-data x;newnode-next NULL;if (pq-ptail NULL){assert(pq-phead NULL);pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);return pq-phead-data;
}QDataType QueueBack(Queue* pq)
{assert(pq);return pq-ptail-data;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includequeue.hvoid TestQueue1()
{Queue q;//初始化QueueInit(q);//入队QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);//打印while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}//销毁QueueDestroy(q);
}int main()
{TestQueue1();return 0;
}
