【数据结构从青铜到王者】第五篇:数据结构之队列

缺乏、安全感 2023-01-16 11:27 107阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]

# 系列文章目录 #

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

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、队列的概念及结构
 *   *   *  1.队列的概念
         *  2.队列的结构
 *  二、队列的实现
 *   *   *  1.定义用链表表示的队列struct QueueNode
         *  2.定义队列的队头、队尾指针struct Queue
         *  3.队列的初始化函数QueueInit
         *  4.队列的销毁函数QueueDestroy
         *  5.队列的队尾入数据函数QueuePush
         *  6.队列的队头出数据函数QueuePop
         *  7.队列的取出队头数据函数QueueFront
         *  8.队列的取出队尾数据函数QueueBack
         *  9.队列是否为空函数QueueEmpty
         *  10.队列的长度函数QueueSize
 *  总结

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

# 前言 #

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

![在这里插入图片描述][20210425211936122.png]

# 一、队列的概念及结构 #

### 1.队列的概念 ###

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

### 2.队列的结构 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]

# 二、队列的实现 #

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]

### 1.定义用链表表示的队列struct QueueNode ###

代码如下：

typedef int QDataType;
    struct QueueNode             //队列结构,用链表来表示
    { 
    	struct QueueNode* next;
    	QDataType data;
    };

### 2.定义队列的队头、队尾指针struct Queue ###

代码如下：

struct Queue                //队列头尾指针
    { 
    	struct QueueNode* head;
    	struct QueueNode* tail;
    };

### 3.队列的初始化函数QueueInit ###

代码如下：

void QueueInit(struct Queue* pq)
    { 
    	assert(pq);
    	pq->head = NULL;
    	pq->tail = NULL;
    }

### 4.队列的销毁函数QueueDestroy ###

遍历队列，记住free前先存储下一个节点的地址。  
代码如下：

void QueueDestroy(struct Queue* pq)
    { 
    	assert(pq);
    	struct QueueNode* cur = pq->head;
    	while (cur)
    	{ 
    		struct QueueNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	pq->head = pq->tail = NULL;
    }

### 5.队列的队尾入数据函数QueuePush ###

先开辟一个结点，在分两种情况，一种情况队列一个节点都没有，那可以直接当节点，第二种情况队列一开始有节点，尾插数据即可。  
代码如下：

void QueuePush(struct Queue* pq, QDataType x)   //队尾入数据
    { 
    	assert(pq);
    	struct QueueNode* newnode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    	if (newnode == NULL)
    	{ 
    		printf("开辟失败!\n");
    		exit(-1);
    	}
    	newnode->data = x;
    	newnode->next = NULL;
    	if (pq->tail == NULL)   //无节点
    	{ 
    		pq->head = pq->tail = newnode;
    	}
    	else
    	{ 
    		pq->tail->next = newnode;
    		pq->tail = newnode;
    	}
    }

### 6.队列的队头出数据函数QueuePop ###

代码如下：

void QueuePop(struct Queue* pq)
    { 
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	if (pq->head->next==NULL)  //只有一个节点
    	{ 
    		free(pq->head);
    		pq->head = pq->tail = NULL;
    	}
    	else
    	{ 
    		struct QueueNode* next = pq->head->next;
    		free(pq->head);
    		pq->head = next;
    	}
    }

### 7.队列的取出队头数据函数QueueFront ###

记住每次取数据前判断队列是否为空，不为空才进行下一步。  
代码如下：

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

### 8.队列的取出队尾数据函数QueueBack ###

记住每次取数据前判断队列是否为空，不为空才进行下一步。  
代码如下：

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

### 9.队列是否为空函数QueueEmpty ###

代码如下：

bool QueueEmpty(struct Queue* pq)
    { 
    	assert(pq);
    	return pq->head == NULL;
    }

### 10.队列的长度函数QueueSize ###

代码如下：

int QueueSize(struct Queue* pq)
    { 
    	int size = 0;
    	assert(pq);  
        struct QueueNode* cur = pq->head;
    	while (cur)
    	{ 
    		size++;
    		cur = cur->next;
    	}
    	return size;
    }

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

# 总结 #

以上就是今天要讲的内容，本文仅仅简单介绍了队列的使用，对于队列提供了一些简便方法帮助我们解题，能使我们快速便捷地处理数据的函数和方法。另外这个结构虽然相比链表更简单，使用代码实现起来更容易写，但我们也要认真学习，以后会发现队列结构会带来很多优势，我们务必掌握。另外，如果有需要源码的私信我即可。还有，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。  
![在这里插入图片描述][20210425210908673.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/87844d784c4649c4b83fb895b554b615.png
[20210425211936122.png]: /images/20221022/f0398593f62b48b3bba2c5be0b411aa8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221022/c240cd448ddc47d294f94734bb4b4899.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221022/0a7030bb35204289b5a88e4c0ff5ff49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221022/cdb8a5604d9848a3a08ae639630354f2.png
[20210425210908673.png_pic_center]: /images/20221022/095254fd3c594482ad5ca4288f4de6ad.png