一、队列的概念及结构： 队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，***队列具有先进先出FIFO(First In First Out)*** 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 二、队列实现的两种方式： 数组队列 链式队列 三、队列的实现： 3.1队列结构： 需要定义两个结构体，一个是整个队列中每个节点的结构一个是队头指针、队尾指针和数据个数 typedef int QDataType; typedef struct QUeueNode//每个节点的结构 { struct QueueNode* next; QDataType data; }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); 3.2初始化： void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } 3.3释放(类似单链表)： 3.3.1代码： 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; } 3.3.2流程图： 3.4入队(类似单链表尾插)： 3.4.1代码： 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++; } 3.4.2流程图： 3.5出队(类似单链表头删)： 3.5.1代码： void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//这里是判断pq->phead不为空 //一个队列 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = NULL; pq->ptail = NULL; } //多个队列 else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } 3.5.2流程图： 3.6队头数据： QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } 3.7队尾数据： QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } 3.8数据个数： int QueueSize(Queue* pq) { assert(pq); return pq->size; } 3.9判空： bool QueueEmpty(Queue* pq) { assert(pq); return pq->size==0; } 四、完整代码： //Queue.h #define _CRT_SECURE_NO_WARNINGS 1 #include #include #include #include typedef int QDataType; typedef struct QUeueNode//每个节点的结构 { struct QueueNode* next; QDataType data; }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 #include"Queue.h" void 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 = NULL; pq->ptail = NULL; } //多个队列 else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(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 #include"Queue.h" void TestQueue() { 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); } printf("\n"); QueueDestroy(&q); } int main() { TestQueue(); return 0; } 总结 Ending,今天的栈和队列(下)的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。