数据结构之队列的实现
- 队列的实现(单链表)
队列的实现(单链表)
以下是有链表模拟队列
如果出现错误以及可优化的部分欢迎留言指教。
实现队列所需要的头文件
#pragma once #include<stdio.h> #include<stdbool.h> #include<stdlib.h> #include<assert.h>
定义数据类型以及创建队列的结点
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; }