一.队列的概念
队列（Queue）是一种非常常见的数据结构，它的操作方式与现实生活中的排队场景非常相似。在队列中，元素按照先进先出（FIFO, First In First Out）的顺序被访问，即先进入队列的元素先被移除，后进入的元素后移除
二.队列的结构
入队列：进行插入数据操作的一端称为队尾。
出队列：进行删除数据操作的一端称为队头。
三.队列的实现
顺序队列
函数接口
voidQueueInit(Queue*pq);voidQueueDestroy(Queue*pq);voidQueuePush(Queue*pq,QDataType x);voidQueuePop(Queue*pq);boolQueueEmpty(Queue*pq);boolQueueFull(Queue*pq);intQueueSize(Queue*pq);QDataTypeQueueFront(Queue*pq);QDataTypeQueueBack(Queue*pq);队列元素
typedefintQDataType;typedefstructQueue{QDataType data[MAX_SIZE];intfront;intrear;}Queue;初始化
// 初始化队列voidQueueInit(Queue*pq){assert(pq);pq->front=pq->rear=0;}销毁
// 销毁队列voidQueueDestroy(Queue*pq){assert(pq);}判断是否为空
// 判断队列是否为空boolQueueEmpty(Queue*pq){assert(pq);returnpq->front==pq->rear;}判断是否满了
// 判断队列是否满boolQueueFull(Queue*pq){assert(pq);return(pq->rear+1)%MAX_SIZE==pq->front;}入队
// 入队操作voidQueuePush(Queue*pq,QDataType x){assert(pq);if(QueueFull(pq)){printf("Queue is full!\n");return;}pq->data[pq->rear]=x;pq->rear=(pq->rear+1)%MAX_SIZE;}出队
// 出队操作voidQueuePop(Queue*pq){assert(pq);if(QueueEmpty(pq)){printf("Queue is empty!\n");return;}pq->front=(pq->front+1)%MAX_SIZE;}队列大小
// 获取队列大小intQueueSize(Queue*pq){assert(pq);return(pq->rear-pq->front+MAX_SIZE)%MAX_SIZE;}队首元素
// 查看队列头部元素QDataTypeQueueFront(Queue*pq){assert(pq);if(QueueEmpty(pq)){printf("Queue is empty!\n");return-1;}returnpq->data[pq->front];}队尾元素
// 查看队列尾部元素QDataTypeQueueBack(Queue*pq){assert(pq);if(QueueEmpty(pq)){printf("Queue is empty!\n");return-1;}returnpq->data[(pq->rear-1+MAX_SIZE)%MAX_SIZE];}链式队列
函数接口
voidQueueInit(Queue*pq);voidQueueDestroy(Queue*pq);voidQueuePush(Queue*pq,QDataType);voidQueuePop(Queue*pq);intQueueSize(Queue*pq);boolQueueEmpty(Queue*pq);QDataTypeQueueFront(Queue*pq);QDataTypeQueueBack(Queue*pq);队列的元素
typedefintQDataType;typedefstructQueueNode{QDataType data;structQueueNode*next;}QNode;typedefstructQueue{QNode*head;QNode*tail;intsize;}Queue;初始化
voidQueueInit(Queue*pq){assert(pq);pq->head=pq->tail=NULL;pq->size=0;}销毁
voidQueueDestroy(Queue*pq){assert(pq);QNode*cur=pq->head;while(cur){QNode*next=cur->next;free(cur);cur=next;}pq->head=pq->tail=NULL;pq->size=0;}插入
voidQueuePush(Queue*pq,QDataType x){QNode*newNode=(QNode*)malloc(sizeof(QNode));if(newNode==NULL){perror("malloc failed");return;}newNode->data=x;newNode->next=NULL;if(pq->head==NULL){assert(pq->tail==NULL);pq->head=pq->tail=newNode;}else{pq->tail->next=newNode;pq->tail=newNode;}pq->size++;}删除
voidQueuePop(Queue*pq){assert(pq);assert(pq->head!=NULL);// QNode* next = pq->head->next;// free(pq->head);// pq->head = next;// if(pq->head == NULL)// pq->tail = NULL;if(pq->head->next==NULL){free(pq->head);pq->head=pq->tail=NULL;}else{QNode*next=pq->head->next;free(pq->head);pq->head=next;}pq->size--;}队列的大小
intQueueSize(Queue*pq){assert(pq);returnpq->size;}判断是否为空
boolQueueEmpty(Queue*pq){assert(pq);returnpq->size==0;}队首元素
QDataTypeQueueFront(Queue*pq){assert(pq);assert(!QueueEmpty(pq));returnpq->head->data;}队尾元素
QDataTypeQueueBack(Queue*pq){assert(pq);assert(!QueueEmpty(pq));returnpq->tail->data;}双端队列
双端队列是一种允许在队列的两端进行插入和删除操作的队列类型。与普通队列（只能在一端入队，另一端出队）不同，双端队列可以在队头和队尾两端进行操作
双端队列还有两种受限的情况：
- 输入受限的双端队列：只许一端插入，两端删除
- 输出受限的双端队列：只许一端删除，两端插入
在这里就不做详细解释了，大家有兴趣的可以自己下去实现一下
函数接口
voidDequeInit(Deque*pdq);队列的元素
typedefintQDataType;typedefstructDequeNode{QDataType data;structDequeNode*prev;// 指向前一个节点structDequeNode*next;// 指向下一个节点}DequeNode;typedefstructDeque{DequeNode*head;DequeNode*tail;intsize;}Deque;初始化
voidDequeInit(Deque*pdq){assert(pdq);pdq->head=pdq->tail=NULL;pdq->size=0;}销毁
voidDequeDestroy(Deque*pdq){assert(pdq);DequeNode*cur=pdq->head;while(cur){DequeNode*next=cur->next;free(cur);cur=next;}pdq->head=pdq->tail=NULL;pdq->size=0;}从队头进出
//从队头进voidDequePushFront(Deque*pdq,QDataType x){assert(pdq);DequeNode*newNode=(DequeNode*)malloc(sizeof(DequeNode));if(newNode==NULL){perror("malloc failed");return;}newNode->data=x;newNode->prev=NULL;newNode->next=pdq->head;if(pdq->head){pdq->head->prev=newNode;}pdq->head=newNode;if(pdq->tail==NULL){pdq->tail=newNode;}pdq->size++;}//从队头出voidDequePopFront(Deque*pdq){assert(pdq);if(pdq->head==NULL){printf("Deque is empty!\n");return;}DequeNode*toDelete=pdq->head;pdq->head=pdq->head->next;if(pdq->head){pdq->head->prev=NULL;}else{pdq->tail=NULL;}free(toDelete);pdq->size--;}从队尾进出
//从队尾进voidDequePushBack(Deque*pdq,QDataType x){assert(pdq);DequeNode*newNode=(DequeNode*)malloc(sizeof(DequeNode));if(newNode==NULL){perror("malloc failed");return;}newNode->data=x;newNode->prev=pdq->tail;newNode->next=NULL;if(pdq->tail){pdq->tail->next=newNode;}pdq->tail=newNode;if(pdq->head==NULL){pdq->head=newNode;}pdq->size++;}//从队尾出voidDequePopBack(Deque*pdq){assert(pdq);if(pdq->tail==NULL){printf("Deque is empty!\n");return;}DequeNode*toDelete=pdq->tail;pdq->tail=pdq->tail->prev;if(pdq->tail){pdq->tail->next=NULL;}else{pdq->head=NULL;}free(toDelete);pdq->size--;}队列的大小
intDequeSize(Deque*pdq){assert(pdq);returnpdq->size;}队头/队尾的元素
QDataTypeDequeFront(Deque*pdq){assert(pdq);assert(pdq->head!=NULL);returnpdq->head->data;}QDataTypeDequeBack(Deque*pdq){assert(pdq);assert(pdq->tail!=NULL);returnpdq->tail->data;}其他特殊队列
在这里呢，我们只作简单介绍。
- 阻塞队列：是一种特殊的队列，它的主要特性是能够在队列为空时阻塞消费者线程，或者在队列满时阻塞生产者线程，直到队列状态发生变化。阻塞队列通常用于多线程编程中的生产者-消费者问题，能够有效避免多线程环境中的资源竞争和浪费。
首次了解队列，可能有不足的地方，欢迎大家评论指出问题。
我们一起学习一起进步。
