前言

我们在用电脑的时候，肯定会经历过电脑处于疑似死机的状态，无论你怎么操作都没有反应。就在当你无计可施，打算直接关闭电源键的时候，电脑突然恢复正常，并且将你刚刚进行的操作全部按顺序执行了一遍。这是因为操作系统在当时可能CPU忙不过来，等前面的事情忙完之后，后面多个指令需要通过一个通道输出，按先后次序排队执行造成的结果。

在操作系统中，它应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。

一、队列的定义

队列：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1,a2,-----an)，那么a1就是队头元素，an就是队尾元素。这样我们就可以删除总是从a1开始，而插入时，列在最后。这也比较符合我们通常生活的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

二、队列的顺序储存结构

2.1 顺序储存结构的不足之处

我们假设一个队列有n个元素，则顺序储存的队列需建立一个大于n的数组，并把队列的所有元素储存在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要任何的移动，时间复杂度为O(1)。

但是，和栈不同的地方就在于，队列的出队操作是在队头。这就意味着，在队列的所有元素都必须向前移动一步，以保证数组下标为0的位置也就是队头不为空，时间复杂度为O(n)。

这里的缺陷就在于，出队操作为什么一定要移动所有元素呢，这其实是增加了时间复杂度。要解决这个问题，我们引入了循环队列的概念。

2.2 循环队列

front：指针指向队头元素。

rear：指针指向队尾元素的下一个位置。（当front等于rear时，队列为空）

循环队列：当rear指针超出数组的范围，即将产生越界错误时。rear指针重新指向数组的开头，我们把队列这种头尾相接的顺序储存结构称为循环队列。

ps：上面我们提到如果front=rear时，我们认为队列为空。但是如果按照队列循环的定义，当储存队列的数组被填满时，front也等于rear。对于这个问题，这里给出两种解决方案：

设置一个标志性变量flag，当front=rear，且flag=0时队列空，当front=rear，且flag=1时为队列满。
当队列空时，条件就是front=rear，当队列满时，我们修改其条件，保留一个空间元素。也就是说，当队列满时，数组中还有一个空闲单元。

有了这些讲解之后，实现代码就不难了，循环队列的顺序存储结构代码如下：

typedef struct{
	
	int data[maxsize];
	int front;      //队头指针
	int rear;       //队尾指针，若队尾不空则指向队尾元素的下一个位置
	 
}squeue;

//循环队列的初始化
status initqueue(squeue *a)
{
	a.front=0;
	a.rear=0;
	
	return ok;
	
}

循环队列的入队列操作代码如下：

status enqueue(squeue *a,int e)
{
	if((a.rear+1)%maxsize==a.front)  //队列满的判断 
	{
		return error;
	}
	a.data[a.rear]=e;             //将元素e赋值给队尾 
	a.rear=(a.rear+1)%maxsize;    //rear指针向后移一位
	                              //若到最后则转到数组头部
	return ok;							   
}

循环队列的出队列操作代码如下：

status dequeue(squeue *a,int *e)
{
	if(a.front==a.rear)    //队列空的判断 
	{
		return error;
	}
	*e=a.data[a.front];     //将队头元素赋值给e 
   	a.front=(a.front+1)%maxsize;    //front指针向后移一位 
	                                //若到最后则转到数组头部 
	return ok;
}

三、队列的链式储存结构及实现

根据我们多年的经验，顺序结构最大的问题往往就是需要考虑是否会溢出的问题。而链式储存结构往往就能很好的解决这个问题。

队列的链式储存结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。空队列时，front和rear都指向头结点。

链队列的结构代码如下：

typedef struct qnode{    //结构结点 
	
	int data;
	struct qnode *next;
}qnode,*queueptr;

typedef struct{          //队列的链表结构 
	
	queueptr front,rear;  //队头、队尾指针 
}linkqueue;

入队操作的代码实现如下：

status enqueue(linkqueue *a,int e)
{
	queueptr s=(queueptr)malloc(sizeof(qnode));   //建立新的结点 
	if(!s)        //储存分配失败 
	{
		exit(0);
	}
	s.data=e;      //将新元素的值赋值给新结点 
	s.next=NULL;
	a.rear.next=s;      //把拥有元素e的新结点s赋值给原队尾结点的后继 
	a.rear=s;           //把当前的s设置为队尾结点，rear指向s 
	
	return ok;
}

出队操作的代码实现如下：

status dequeue(linkqueue *a,int *e)
{
	queueptr p;
	if(a.front==a.rear)
	{
		return error;
	}
	p=a.front.next;     //将欲删除的队头结点暂存给p 
	*e=p.data;          //将欲删除的队头结点的值赋值给e 
	a.front.next=p.next; //将原队头结点的后继p.next赋值给头结点后继 
	if(a.rear==p)        //若队头就是队尾，则删除后将rear指向头结点 
	{
		a.rear=a.front;
	}
	free(p);
	
	return ok;
}

总结

总的来说，在可以确定队列长度最大值的情况下，建议使用循环队列，如果你无法预测队列的长度，则用链队列。

原文链接：https://blog.csdn.net/xzt12138/article/details/126124370