队列的概念及结构（内有成型代码可供CV工程师参考）

刺骨的言语ヽ痛彻心扉 2023-09-27 23:51 38阅读 0赞

**目录**

前言以及队列全部代码（CV工程师点这里）

一、队列的概念

二、队列的实现

三、代码实现以及详细解释

1. 初步介绍

2. 定义结构体，以及栈内数据类型

3. 初始化队列

4.队列的销毁

5. 队列插入元素（尾插）

6.删除队头元素

7.返回队头元素

8. 返回队尾元素

9.求队列的长度

10. 判断是否为空

--------------------

## 前言以及队列全部代码（CV工程师点这里） ##

前言：前面我们学习了链表以及栈的知识，他们都是数据结构中的重要知识点，接下来我们来学习一下队列有关的知识。还是老套路二话不说，先上代码

#include<stdlib.h>
    #include<assert.h>
    #include<stdbool.h>
    
    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);
    void QueuePop(Queue* pq);
    QDataType QueueFront(Queue* pq);
    QDataType QueueBack(Queue* pq);
    int QueueSize(Queue* pq);
    bool QueueEmpty(Queue* pq);
    
    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++;
    }
    
    void QueuePop(Queue* pq)
    {
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	if (pq->phead->next ==NULL)
    	{
    		QNode* head = pq->phead;
    		free(head);
    		pq->phead = pq->ptail = NULL;
    		pq->size = 0;
    	}
    	else
    	{
    		QNode* head = pq->phead;
    		pq->phead = pq->phead->next;
    		free(head);
    		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;
    }
    bool QueueEmpty(Queue* pq)
    {
    	assert(pq);
    	return pq->size == 0;
    }

## 一、队列的概念 ##

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有**先进先出**FIFO(First In First Out)

> 入队列：进行插入操作的一端称为**队尾**
> 
> 出队列：进行删除操作的一端称为**队头**

![0160d52a940b406abd7d7805f0264c03.png][]

## 二、队列的实现 ##

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

![6878cb6c4bfe48798d1091bd22aa1184.png][]

![051df0b8baef1f790dbfde1a4b6aa4e4.jpeg][]

![defd26e59e604734a6f5d377bfee9272.png][]

## 三、代码实现以及详细解释 ##

### 1. 初步介绍 ###

> 1. 初始化队列 void QueueInit(Queue\* pq);  
> 2. 队列的销毁 void QueueDestroy(Queue\* pq);  
> 3. 队列插入元素（尾插） void QueuePush(Queue\* pq, QDataType x);  
> 4. 删除队头元素 void QueuePop(Queue\* pq);  
> 5. 返回队头元素 QDataType QueueFront(Queue\* pq);  
> 6. 返回队尾元素 QDataType QueueBack(Queue\* pq);  
> 7. 求队列的长度 int QueueSize(Queue\* pq);  
> 8. 判断是否为空 bool QueueEmpty(Queue\* pq);

--------------------

### 2. 定义结构体，以及栈内数据类型 ###

代码：

### 3. 初始化队列 ###

**代码：**

void QueueInit(Queue* pq)
    {
    	assert(pq);
    	pq->phead = NULL;
    	pq->ptail = NULL;
    	pq->size = 0;
    }

### 4.队列的销毁 ###

**代码：**

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;
    }

### 5. 队列插入元素（尾插） ###

**代码：**

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++;
    }

### 6.删除队头元素 ###

**代码：**

void QueuePop(Queue* pq)
    {
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	if (pq->phead->next ==NULL)
    	{
    		QNode* head = pq->phead;
    		free(head);
    		pq->phead = pq->ptail = NULL;
    		pq->size = 0;
    	}
    	else
    	{
    		QNode* head = pq->phead;
    		pq->phead = pq->phead->next;
    		free(head);
    		pq->size--;
    	}
    }

### 7.返回队头元素 ###

**代码：**

QDataType QueueFront(Queue* pq)
    {
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	return(pq->phead->data);
    }

### 8. 返回队尾元素 ###

**代码：**

QDataType QueueBack(Queue* pq)
    {
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	return pq->ptail->data;
    }

### 9.求队列的长度 ###

**代码：**

int QueueSize(Queue* pq)
    {
    	assert(pq);
    	return pq->size;
    }

### 10. 判断是否为空 ###

**代码：**

bool QueueEmpty(Queue* pq)
    {
    	assert(pq);
    	return pq->size == 0;
    }

[0160d52a940b406abd7d7805f0264c03.png]: https://img-blog.csdnimg.cn/0160d52a940b406abd7d7805f0264c03.png
[6878cb6c4bfe48798d1091bd22aa1184.png]: https://img-blog.csdnimg.cn/6878cb6c4bfe48798d1091bd22aa1184.png
[051df0b8baef1f790dbfde1a4b6aa4e4.jpeg]: https://img-blog.csdnimg.cn/img_convert/051df0b8baef1f790dbfde1a4b6aa4e4.jpeg
[defd26e59e604734a6f5d377bfee9272.png]: https://img-blog.csdnimg.cn/defd26e59e604734a6f5d377bfee9272.png