数据结构之——队列详解

目录

前言：

一、什么是队列

二、队列的实现

        2.1 队列结构

        2.2 队列初始化

        2.3 队列销毁

        2.4 入队列

        2.5 出队列

        2.6 获取队列头部元素 

        2.7  获取队列尾部元素 

        2.8 获取队列中有效元素个数 

        2.9 检测队列是否为空

三、 代码总览

        Queue.h

        Queue.c

        test.c

四、例题

---

前言：

        我们前面已经学习了栈，今天我们来学习队列，队列和栈一样，相对来说比较简单，随后，会为大家准备OJ练习题，敬请期待！

一、什么是队列

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

        入队列：进行插入操作的一端称为队尾

        出队列：进行删除操作的一 端称为队头

        这里简单给大家解释一下：

        大家肯定都排过队（别说没有，我不信），大家在排好队先前前进时，是不是先站到队伍里的先走。队列的原理何其类似。因为，你可以猜一猜它为什么叫队列。可用下面图片帮助大家理解。 

         明白了，基础知识，那就一起来实现一下队列吧。

二、队列的实现

        2.1 队列结构

                和栈一样，我们队列的结构该如何设计呢？

                队列一共有两种结构，分为：顺序结构和链式结构

• 队列的顺序结构

入队，不需要移动任何元素，时间复杂度为O(1)

出队，所有元素需要往前移动，时间复杂度为O(N)

• 队列的链式结构

首先我们定义两个指针，队头指针指向第一个节点，队尾指针指向尾节点

入队（尾插），时间复杂度为O(1)

出队（头删），时间复杂度为O(1)

                这里，我们将采取链式结构，如若对顺序结构感兴趣可结合之前的栈进行实现。

                我们要采用链式难道要用二级指针吗？一级已经够麻烦了，使用二级会更晕。所以，为了避免这种轻快，我们可采取结构体，如下代码：

typedef int QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;
 
// 队列的结构 
typedef struct Queue
{
	QNode* phead;
	QNode* ptatil;
	int size;
}Queue;

                这样即可避免二级指针。

        2.2 队列初始化

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->phead = q->ptatil = NULL;
	q->size = 0;
}

                初始化只用将头和尾置为空即可。队列还未建立，所以，先不管。

        2.3 队列销毁

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->phead = q->ptatil = NULL;
	q->size = 0;
}

                销毁时我们要释放的是指针所指向开辟空间，而不是指针本身。所以，使用一个while循来释放。

        2.4 入队列

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->data = data;
	if (q->phead == NULL)//这里使用头节点，尾节点判断均可
	{
		q->phead = q->ptatil = newnode;
	}
	else
	{
		q->ptatil->next = newnode;//记住这里是尾节点，不是头节点！！！
		q->ptatil = newnode;
	}
	q->size++;
}

                入队列时，我们要为其开辟一块空间也就是QNode，这就是队列的元素。要分为两种情况讨论，队列为空和队列不为空。

        2.5 出队列

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->size != 0);
	if (q->phead->next == NULL)
	{
		q->phead = q->ptatil = NULL;
	}
	else
	{
		QNode* next = q->phead->next;
		free(q->phead);
		q->phead = next;
	}
	q->size--;
}

                要注意：分两种情况进行讨论。

        2.6 获取队列头部元素 

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->phead);
	return q->phead->data;
}

                这里，直接用头指针返回值即可。

        2.7  获取队列尾部元素 

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->ptatil);
	return q->ptatil->data;
}

                和上面一样，运用指针获取值即可。

        2.8 获取队列中有效元素个数 

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

        2.9 检测队列是否为空

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}

三、 代码总览

        Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
typedef int QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;
 
// 队列的结构 
typedef struct Queue
{
	QNode* phead;
	QNode* ptatil;
	int size;
}Queue;
 
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
 

        Queue.c

#include"Queue.h"
 
// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->phead = q->ptatil = NULL;
	q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->data = data;
	if (q->phead == NULL)
	{
		q->phead = q->ptatil = newnode;
	}
	else
	{
		q->ptatil->next = newnode;//记住这里是尾节点，不是头节点！！！
		q->ptatil = newnode;
	}
	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->size != 0);
	if (q->phead->next == NULL)
	{
		q->phead = q->ptatil = NULL;
	}
	else
	{
		QNode* next = q->phead->next;
		free(q->phead);
		q->phead = next;
	}
	q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->phead);
	return q->phead->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->ptatil);
	return q->ptatil->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->phead = q->ptatil = NULL;
	q->size = 0;
}

        test.c

#include"Queue.h"
 
int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(& q);
	}
	printf("\n");
	QueueDestroy(&q);
	return 0;
}

四、例题

        来一道例题来练一练吧！

        现有队列Q与栈S，初始时Q中的元素依次是 1,2,3,4,5,6(1在队头)，S 为空。若仅允许下列3种操作:①出队并输出出队元素;②出队并将出队元素入栈;③出栈并输出出栈元素，则不能得到的输出序列是()。

                       A. 1,2,5,6,4,3                                        B.  2,3,4,5,6,1                                        C. 3,4,5,6,1,2                                         D.  6.5.4.3.2.1

        

        可得：答案为：C。

        如果还有什么问题，可以私信也可在评论区留言！

        栈和队列经典习题：CSDN

完！