C语言笔记38 •数据结构--队列•

数据结构--队列

1.队列的定义

2.队列的实现 

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

//队列本质就是一个链表

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 PrintQueue(Queue* pq);//打印队列数据

QNode* Buynode(QDataType x);//申请节点

void QueuePush(Queue* pq, QDataType x);//队尾插入数据（队尾进）

void QueuePop(Queue* pq);//队头删除数据（队头出）

bool QueueEmpty(Queue* pq);//判断队列是否为空

size_t QueueSize(Queue* pq);//队列的长度

QDataType QueueFront(Queue* pq);//输出队头的数据值

QDataType QueueBack(Queue* pq);//输出队尾的数据值

//队列的基本实现#pragma once
#include <stdio.h> 
#include <stdlib.h> 
#include <assert.h> 
#include <stdbool.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 PrintQueue(Queue* pq);//打印队列数据QNode* Buynode(QDataType x);//申请节点void QueuePush(Queue* pq, QDataType x);//队尾插入数据（队尾进）void QueuePop(Queue* pq);//队头删除数据（队头出）bool QueueEmpty(Queue* pq);//判断队列是否为空size_t QueueSize(Queue* pq);//队列的长度QDataType QueueFront(Queue* pq);//输出队头的数据值QDataType QueueBack(Queue* pq);//输出队尾的数据值//接口函数的实现void QueueInit(Queue* pq)//初始化队列
{assert(pq);pq->head = pq->tail = NULL;
}void QueueDestory(Queue* pq)//销毁队列
{assert(pq);QNode *cur= pq->head;while (cur){QNode* temp = cur->next;free(cur);cur = temp;}pq->head = pq->tail = NULL;
}void PrintQueue(Queue* pq)//打印队列数据
{assert(pq);QNode* cur = pq->head;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
QNode* Buynode(QDataType x)//申请节点
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;
}void QueuePush(Queue* pq, QDataType x)//队尾插入数据（队尾进）
{assert(pq);if (pq->head == NULL){pq->head = pq->tail = Buynode(x);}else{pq->tail->next = Buynode(x);pq->tail = pq->tail->next;}
}
void QueuePop(Queue* pq)//队头删除数据（队头出）
{assert(pq);if (pq->head == pq->tail){free(pq->head);pq->head = pq->tail=NULL;}else{QNode* temp = pq->head->next;free(pq->head);pq->head = temp;}
}
bool QueueEmpty(Queue* pq)//判断队列是否为空
{assert(pq);return pq->head == NULL;
}
size_t QueueSize(Queue* pq)//队列的长度
{assert(pq);size_t size = 0;QNode* cur = pq->head;while (cur){size++;cur = cur->next;}return size;
}
QDataType QueueFront(Queue* pq)//输出队头的数据值
{assert(pq);assert(pq->head);return pq->head->data;
}QDataType QueueBack(Queue* pq)//输出队尾的数据值
{assert(pq);assert(pq->tail);return pq->tail->data;
}//队列接口函数的测试void queue_test()
{Queue q;QueueInit(&q);//初始化队列QueuePush(&q, 1);//队尾插入数据（队尾进）进1QueuePush(&q, 2);//队尾插入数据（队尾进）进2QueuePush(&q, 3);//队尾插入数据（队尾进）进3PrintQueue(&q);//打印队列数据  1 2 3printf("队头值:%d\n", QueueFront(&q)); //输出队头的数据值printf("队尾值:%d\n", QueueBack(&q)); //输出队尾的数据值printf("队列的长度:%d\n", QueueSize(&q)); //队列的长度printf("队列状态：%s\n", QueueEmpty(&q) ? "True" : "False");//判断队列是否为空printf("=======================================\n");QueuePop(&q);//队头删除数据（队头出）出1PrintQueue(&q);//打印队列数据 2 3printf("队头值:%d\n", QueueFront(&q)); //输出队头的数据值printf("队尾值:%d\n", QueueBack(&q)); //输出队尾的数据值printf("队列的长度:%d\n", QueueSize(&q)); //队列的长度printf("队列状态：%s\n", QueueEmpty(&q) ? "True" : "False");//判断队列是否为空printf("=======================================\n");QueuePop(&q);//队头删除数据（队头出）出2PrintQueue(&q);//打印队列数据3printf("队头值:%d\n", QueueFront(&q)); //输出队头的数据值printf("队尾值:%d\n", QueueBack(&q)); //输出队尾的数据值printf("队列的长度:%d\n", QueueSize(&q)); //队列的长度printf("队列状态：%s\n", QueueEmpty(&q) ? "True" : "False");//判断队列是否为空printf("=======================================\n");QueuePop(&q);//队头删除数据（队头出）出3PrintQueue(&q);//打印队列数据 无数据printf("队列的长度:%d\n", QueueSize(&q)); //队列的长度printf("队列状态：%s\n", QueueEmpty(&q) ? "True" : "False");//判断队列是否为空QueueDestory(&q);//销毁队列
}int main()
{queue_test();return 0;
}