> 文档中心 > 数据结构之队列的实现(含全部代码)

数据结构之队列的实现(含全部代码)


队列的实现(单链表)

以下是有链表模拟队列
如果出现错误以及可优化的部分欢迎留言指教。
实现队列所需要的头文件

#pragma once#include#include#include#include

定义数据类型以及创建队列的结点

typedef int QDataType;typedef struct QueueNode{QDataType data;struct QueueNode* next;}QNode;

创建队列(含队列的头和尾)

typedef struct Queue{QNode* head;QNode* tail;}Queue;

队列所需要实现的函数接口

//初始化void QueueInit(Queue* pq);//销毁void QueueDestory(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);

函数的实现

#include"Queue.h"//初始化void QueueInit(Queue* pq){assert(pq);pq->head = NULL;pq->tail = NULL;}//销毁void QueueDestory(Queue* pq){assert(pq);QNode* cur = pq->head;while(cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}//队头入void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QDataType*)malloc(sizeof(QDataType));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}//队尾出void QueuePop(Queue* pq){assert(pq);assert(pq->head);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}}//取队头的元素QDataType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->data;}//取对尾的元素QDataType QueueBack(Queue* pq){assert(pq);assert(pq->head);return pq->tail->data;}//计算元素个数int QueueSize(Queue* pq){assert(pq);int size = 0;QNode* cur = pq->head;while (cur != NULL){size++;cur = cur->next;}}//判断队列是否为空bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}