对于队列的学习

一.队列的概念

队列（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;}

其他特殊队列

在这里呢，我们只作简单介绍。

• 阻塞队列：是一种特殊的队列，它的主要特性是能够在队列为空时阻塞消费者线程，或者在队列满时阻塞生产者线程，直到队列状态发生变化。阻塞队列通常用于多线程编程中的生产者-消费者问题，能够有效避免多线程环境中的资源竞争和浪费。

首次了解队列，可能有不足的地方，欢迎大家评论指出问题。
我们一起学习一起进步。