【数据结构】队列简单介绍及C语言实现链式队列

目录一、队列简单介绍二、队列的实现C语言代码Queue.h引入头文件、定义队列的结构、声明队列的方法Queue.c1.初始化2.销毁3.队尾插入4.队头删除5.取队头数据6.取队尾数据7.返回队列元素个数8.判空9.输出队列全部元素10.完整代码三、循环队列1.循环队列介绍2.C语言实现循环队列(数组)一、队列简单介绍队列是只允许在一端进行插入操作在另一端进行删除操作的特殊线性表。队列中的数据元素遵循先进先出FIFO(First In first Out)的原则。入队列进行插入操作的一段称为队尾出队列进行删除操作的一段称为队头二、队列的实现队列可以使用数组或链表的结构实现。使用链表的结构更优一些。如果使用数组结构出队列在数组头上出数据效率会比较低。如果使用链表结构入队列即为尾插出队列即为头删。C语言代码Queue.h引入头文件、定义队列的结构、声明队列的方法#pragma once #include stdio.h #include stdlib.h #include stdbool.h #include assert.h typedef int QDataType; typedef struct QueueNode { QDataType val; 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.c1.初始化将队列大小置为0并把队头和队尾指针置为空。// 初始化 void QueueInit(Queue* pq) { assert(pq); pq-phead NULL; pq-ptail NULL; pq-size 0; }2.销毁定义一个pcur代表当前节点从队头开始。当pcur不为空时将pcur指向的空间释放再将pcur指向下一个结点。当pcur为空时退出循环并将队列的头节点尾节点置空队列大小置为0。// 销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* pcur pq-phead; while (pcur) { QNode* next pcur-next; free(pcur); pcur next; } pq-phead pq-ptail NULL; pq-size 0; }3.队尾插入先申请一个新节点的空间将新节点的val值赋值为x新节点的next指向NULL然后将新节点插入到队尾。此时有两种情况队列为空和队列不为空。当队列为空时直接将队列的头指针和尾指针指向新节点即可。当队列不为空时将尾节点的next指向新节点再将尾节点指向新节点。最后将队列中数据个数1。// 队尾插入 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newNode (QNode*)malloc(sizeof(QNode)); if (newNode NULL) { perror(malloc fail); return; } newNode-next NULL; newNode-val x; if (pq-ptail NULL) { pq-phead pq-ptail newNode; } else { pq-ptail-next newNode; pq-ptail pq-ptail-next; } pq-size; }4.队头删除先判断队列是否为空。如果队列不为空删除队头元素此时分为两种情况。当队列中只有一个结点时直接释放头指针指向的空间再将头指针尾指针置为空。当队列中有多个结点时释放头指针指向的空间再将头指针指向下一个结点即可。最后队列元素个数-1。// 队头删除 void QueuePop(Queue* pq) { assert(pq); assert(pq-size ! 0); if (pq-phead pq-ptail) { // 只有一个节点 free(pq-phead); pq-phead pq-ptail NULL; } else { // 有多个节点 QNode* next pq-phead-next; free(pq-phead); pq-phead next; } pq-size--; }5.取队头数据返回头指针指向的结点的val值// 取队头数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq-phead); return pq-phead-val; }6.取队尾数据返回尾指针指向的结点的val值// 取队尾数据 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq-ptail); return pq-ptail-val; }7.返回队列元素个数因为定义队列结构时定义了size所以直接返回size// 返回队列元素个数 int QueueSize(Queue* pq) { assert(pq); return pq-size; }8.判空队列的元素个数不等于0时返回true// 判空 bool QueueEmpty(Queue* pq) { assert(pq); return (pq-size 0); }9.输出队列全部元素队列不为空时获取队头元素并输出再将队头元素删除循环直到队列为空。while (!QueueEmpty(q)) { printf(%d , QueueFront(q)); QueuePop(q); } printf(\n);10.完整代码#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* pcur pq-phead; while (pcur) { QNode* next pcur-next; free(pcur); pcur 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-next NULL; newNode-val x; if (pq-ptail NULL) { pq-phead pq-ptail newNode; } else { pq-ptail-next newNode; pq-ptail pq-ptail-next; } pq-size; } // 队头删除 void QueuePop(Queue* pq) { assert(pq); assert(pq-size ! 0); if (pq-phead pq-ptail) { // 只有一个节点 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); assert(pq-phead); return pq-phead-val; } // 取队尾数据 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq-ptail); return pq-ptail-val; } // 返回队列元素个数 int QueueSize(Queue* pq) { assert(pq); return pq-size; } // 判空 bool QueueEmpty(Queue* pq) { assert(pq); return (pq-size 0); }三、循环队列1.循环队列介绍使用数组实现队列会出现假溢出现象可以使用循环队列避免假溢出。循环队列有一个头指针一个尾指针。头指针指向循环队列的队头元素尾指针指向队尾元素的下一个位置。通常情况下循环队列大小为N时可以存储N-1个数据尾指针指向的位置不存放数据。所以当循环队列的头指针和尾指针指向同一个位置时循环队列为空当尾指针的next和头指针指向同一个位置时循环队列为满。使用数组存放时判断循环队列满的条件是(tail 1) % (k 1) head。其中tail表示队尾的下一个位置下标值head表示队头的下标值k表示队列中能存储的最大元素个数。2.C语言实现循环队列(数组)typedef struct { int* a; int head; int tail; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj - a malloc(sizeof(int)*(k1)); obj - head 0; obj - tail 0; obj - k k; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if((obj-tail 1)%(obj-k1) obj-head){ return false; } obj-a[obj-tail] value; obj-tail; obj-tail % (obj-k1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(obj-head obj-tail){ return false; } obj-head; obj-head % (obj-k1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(obj-head obj-tail){ return -1; }else{ return obj-a[obj-head]; } } int myCircularQueueRear(MyCircularQueue* obj) { if(obj-head obj-tail){ return -1; }else{ return obj-a[(obj-tail-1obj-k1)%(obj-k1)]; } } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj-head obj-tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return ((obj-tail 1)%(obj-k1) obj-head); } void myCircularQueueFree(MyCircularQueue* obj) { free(obj-a); free(obj); }完