1. 队列的概念和定义

队列是一般定义是：在表尾进行插入，在表头进行删除操作==的线性表。

队列的特点先入先出，FIFO。

我们学习栈的时候，说过栈是后入先出 （ FILO ），打了一个比喻，就是一个箱子，我们往里面放书和取书。

2. 用简单的例子理解队列

现在学习队列，我们也要打一个比喻帮助理解。这次就不是箱子了，而是有一个雪糕店，做的雪糕很好吃。很多顾客慕名前来，生意太好了，所以雪糕店排起了长长的队伍。

2.1. 入队

现在又新来了一个顾客小明，小明来了只能排到队尾啊，插队是会被人骂的。

2.2 出队

队伍的最前面是王大妈，她排了整整 20 分钟的队，终于轮到她了。她给了钱，买了单，服务员给她一个芒果雪糕，然后，她就走了。

2.3. 队空

到了晚上 10 点半，没有新的顾客来买雪糕了，这时候没有人排队了。

3 基于数组实现队列问题

我们把队列的内容放进数组，并且，用变量 head 记录队头位置，用变量 tail 记录队尾的位置，这就是一个简单的队列结构。

3.1 左闭右开原则

比较正规的方法，队列下标采用左闭右开原则，如果我们用 for 语句来理解，是下面的这个代码段:

for(int i=head;i<tail;i++)
{
	int t = q[i];
	//这里是队列元素的处理语句，略
}

这个写法是大多数教科书教的写法，考试的填空题选择题一般会按照这个写法来考。

3.2 空队列判断

当什么队列里面什么都没有，就称为空队列。

因为是左闭右开的原则，所以，空队列的时候，head = tail 。这是计算机考试理论考试的高频考点。

套到上面的那段程序里看，当 tail == head 的时候，压根就没有进入循环，直接跳出了。

3.3 当队列里面有 1 个元素的时候

tail == head+1

3.4 计算队列里有多少个元素

队列中元素的个数也叫队列长度：tail-head

3.5 队列满

队列其实就是顺序表，可以简单理解为数组。数组的大小总是有限的，所以队列的大小也是有限的。如果数据太多，不断的进入队列，那么队列就满了，这叫溢出。判断出队列已经满了，是保证程序输出正确结果的重要内容，我们也是要学的。

如果队列数组定义的 n 大小，当 tail==n 的时候表示队列满了（数组定义了 n 大小，数组下标只能用 0 ~ n-1）。

3.6 新元素入队列

void push(int t)
{
	q[tail] = t; // t 入队列
	tail++;
}

或者简化成

void push(int t)
{
	q[tail++] = t; // t 入队列
}

3.7 弹出队首元素

一般来说，先把队首的数据拷贝出来，按照题目进行相应的运算，然后让 head 指针加 1 。虽然原来的数据还在数组里面，但是 head 指针已经指向新的位置，所以被删的数据不会被再访问的了。

int pop()
{
	int ret = q[head];
	head++;
	return ret;
}

或者简化成

int pop()
{
	int ret = q[head++];
	return ret;
}

3.8 循环队列

循环队列是指队列的尾指针到达 n 之后，从新变成 0 ，让数组的内存被反复使用。打个比方，你开了个卖雪糕的店，顾客门口排长队，你只要保证每一个时刻不超过 1000 人，你的店就能维持正常营业。但是，一天下来，你可能卖出了 10 万个雪糕，你定义的数组不需要是 10 万那么大，只需要 1000 就够了。

在上图中，无论队头的 head 指针还是队尾的 tail 指针，都是绕着圆圈格子转的。圆圈格子可以理解为数组。

对于循环队列，有几个要记忆的：

队列空： tail==head (跟普通队列一样)

队列满: (tail+1)%n==head ,简单来说，就是 tail 已经快追上 head 了，两个格子是挨着的。

队列中元素的个数 (tail-head+n)%n

上述内容为高频考点

const int n=1000;
int q[n],tail,head;

void push(int t) //把 t 放入队列
{
	if( (head+1)%n==tail ) printf("错误，队列已满\n)";
	else
	{
		q[tail] = t;
		tail++;
		if(tail==n) tail = 0; //循环队列，指针要循环处理
	}
}

int pop() //队首出队列
{
	if(head==tail)
	{
		printf("错误，队列已空\n)";
		return -1; //返回 -1 表示错误
	}
	else
	{
		int ret = q[head];
		head++;
		if(head==n) head = 0;//循环队列，，指针要循环处理
		return ret;
	}
}

4.相关术语

队列的头： head 或者 front

队列的尾： tail 后者 rear （汽车的倒后镜叫 rear mirror）

入队列： push (就推、挤压的意思，你想象一下有一个子弹夹，你把子弹一颗颗压进弹夹就是用 push 这个单词)

出队列： pop （就是跳的意思，把所以出队列也叫 弹出 ）