【数据结构：队列】——队列的实现（C语言）

1、什么是队列？

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列和出队列。 队尾：进行插入操作的一端 队头：进行删除操作的一端 详细了解：队列的详解

2、队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

数组结构： 链表结构：

3、代码实现

Queue.h文件

#include<stdio.h> #include<windows.h> #include<assert.h> #include<malloc.h> typedef char QUDataType; typedef struct QueueNode { struct QueueNode* _next; QUDataType _data; }QueueNode; typedef struct Queue { QueueNode* _front; QueueNode* _tail; }Queue; void QueueInit(Queue* pq);//初始化 void QueueDestory(Queue* pq);//销毁 QueueNode* BuyQueueNode(QUDataType x);//创建一个节点 void QueuePush(Queue* pq,QUDataType x);//尾插 void QueuePop(Queue* pq);//头删 QUDataType QueueFront(Queue* pq);//取出当前头部元素 QUDataType QueueBack(Queue* pq);//取出当前尾部元素 int QueueEmpty(Queue* pq);//判断队列是否为空 int QueueSize(Queue* pq);//计算当前队列元素 void QueuePirnt(Queue* pq);//依次取出队列元素

Queue.c文件

void QueueInit(Queue* pq)//初始化 { assert(pq); pq->_front = pq->_tail = (QueueNode*)malloc(sizeof(QueueNode)); assert(pq->_front); pq->_front->_next = NULL; pq->_front->_data = 0; } void QueueDestory(Queue* pq)//销毁 { assert(pq); QueueNode *cur = pq->_front; while (cur) { QueueNode *next = cur->_next; free(cur); cur = next; } pq->_front = pq->_tail = NULL; } QueueNode* BuyQueueNode(QUDataType x)//创建一个节点 { QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); assert(newnode); newnode->_data = x; newnode->_next = NULL; return newnode; } void QueuePush(Queue* pq, QUDataType x)//尾插 { assert(pq); QueueNode* newnode = BuyQueueNode(x); assert(newnode);//判断申请空间是否成功 pq->_tail->_next = newnode; pq->_tail = newnode; } void QueuePop(Queue* pq)//头删 { assert(pq && pq->_front->_next != NULL); QueueNode* next = pq->_front->_next;//保存对头第一个元素 if (pq->_tail == next) { pq->_tail = pq->_front; } pq->_front->_next = next->_next; free(next); next = NULL; } QUDataType QueueFront(Queue* pq)//取出当前头部元素 { assert(pq); return pq->_front->_next->_data;; } QUDataType QueueBack(Queue* pq)//取出当前尾部元素 { assert(pq); return pq->_tail->_data; } int QueueEmpty(Queue* pq)//判断队列是否为空 { assert(pq); return pq->_front == pq->_tail ? 0 : 1; } int QueueSize(Queue* pq)//计算当前队列元素 { assert(pq); QueueNode* cur = pq->_front->_next; int count = 0; if (QueueEmpty == 0) { return 0; } else { while (cur) { ++count; cur = cur->_next; } } return count; } void QueuePirnt(Queue* pq)//依次取出队列元素 { assert(pq); QueueNode* cur = pq->_front->_next; while (cur) { printf("%d->", cur->_data); cur = cur->_next; } printf("NULL\n"); }

main.c文件

#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" int main() { Test(); system("pause"); return 0; }

运行截图