作者：解学武

队列用来存储逻辑关系为“一对一”的数据，是一种“特殊”的线性存储结构。

和顺序表、链表相比，队列的特殊性体现在以下两个方面：
1、元素只能从队列的一端进入，从另一端出去，如下图所示：


通常，我们将元素进入队列的一端称为“队尾”，进入队列的过程称为“入队”；将元素从队列中出去的一端称为“队头”，出队列的过程称为“出队”。

2、队列中各个元素的进出必须遵循“先进先出”的原则，即最先入队的元素必须最先出队。

以图 1 所示的队列为例，从各个元素在队列中的存储状态不难判定，元素 1 最先入队，然后是元素 2 入队，最后是元素 3 入队。如果此时想将元素 3 出队，根据“先进先出”原则，必须先将元素 1 和 2  依次出队，最后才能轮到元素 3 出队。

强调：栈和队列不要混淆，栈是一端开口、另一端封口，元素入栈和出栈遵循“先进后出”原则；队列是两端都开口，但元素只能从一端进，从另一端出，且进出队列遵循“先进先出”的原则。

队列的实际应用

队列在操作系统中应用的十分广泛，比如用它解决 CPU 资源的竞争问题。

对于一台计算机来说，CPU 通常只有 1 个，是非常重要的资源。如果在很短的时间内，有多个程序向操作系统申请使用 CPU，就会出现竞争 CPU 资源的现象。不同的操作系统，解决这一问题的方法是不一样的，有一种方法就用到了队列这种存储结构。

假设在某段时间里，有 A、B、C 三个程序向操作系统申请 CPU 资源，操作系统会根据它们的申请次序，将它们排成一个队列。根据“先进先出”原则，最先进队列的程序出队列，并获得 CPU 的使用权。待该程序执行完或者使用 CPU 一段时间后，操作系统会将 CPU 资源分配给下一个出队的程序，以此类推。如果该程序在获得 CPU 资源的时间段内没有执行完，则只能重新入队，等待操作系统再次将 CPU 资源分配给它。
 
队列还可以用来解决一些实际问题，比如实现一个简单的停车场管理系统、实现一个推小车卡牌游戏等，后续会做详细讲解。

队列的具体实现

和栈的实现方案一样，队列的实现也有两种方式，分别是：

• 顺序队列：用顺序表模拟实现队列存储结构；
• 链队列：用链表模拟实现队列存储结构。

两者的区别仅是顺序表和链表的区别，即顺序队列集中存储数据，而链队列分散存储数据，元素之间的逻辑关系靠指针维系。