目录
个人专栏持续更新:
有需要的看看,如果对你有帮助可以支持一波哦!!
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO (First In First Out)入队列:进行插入操作的一端称为队尾。出队列:进行删除操作的一端称为队头。
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,需要数据依次向后移动,效率会比较低。
我们需要两个结构体:
- 一个储存单个节点的信息(下一个节点的地址和数据),
- 另一个用于存储队列的信息(头节点和尾节点的地址)。
- typedef int QDataType;
- typedef struct QueueNode
- {
- struct QueueNode* next;
- QDataType data;
- }QNode;
-
- typedef struct Queue
- {
- QNode* phead;
- QNode* ptail;
- int size;
- }Queue;
QNode:节点结构体
Queue:队列结构体
- 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\n");
- 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++;
- }
- bool QueueEmpty(Queue* pq)
- {
- assert(pq);
- return pq->size == 0;
- }
- void QueuePop(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
-
- if (pq->phead->next == NULL) {
- 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(!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;
- }
- #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);
- bool QueueEmpty(Queue* pq);
- void QueuePop(Queue* pq);
- QDataType QueueFront(Queue* pq);
- QDataType QueueBack(Queue* pq);
- int QueueSize(Queue* pq);
- #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\n");
- 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++;
- }
-
- bool QueueEmpty(Queue* pq)
- {
- assert(pq);
- return pq->size == 0;
- }
-
- void QueuePop(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
-
- if (pq->phead->next == NULL) {
- free(pq->phead);
- pq->phead = pq->ptail = NULL;//防止使用ptail造成对野指针的访问
- }
- 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;
- }
- #include"Queue.h"
-
- void TestQueue()
- {
- Queue q;
- QueueInit(&q);
- QueuePush(&q, 1);
- QueuePush(&q, 2);
- QueuePush(&q, 3);
- //while (!QueueEmpty(&q)) {
- // printf("%d", QueueFront(&q));
- // QueuePop(&q);
- //}
- //printf("\n");
- printf("%d\n", QueueBack(&q));
- QueueDestroy(&q);
- }
-
- int main()
- {
- TestQueue();
-
- return 0;
- }