189 8069 5689
这篇文章主要介绍“队列的基本原理和操作方法”，在日常操作中，相信很多人在队列的基本原理和操作方法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”队列的基本原理和操作方法”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
10年积累的网站设计制作、成都网站设计经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先建设网站后付款的网站建设流程，更有凤泉免费网站建设让你可以放心的选择与我们合作。
提要钩玄：本文主要介绍队列的结构、基本原理及操作，涉及到两种实现：顺序队列和链队列。
先举一个日常例子，排队买饭。
排队买饭
大家按先来后到的顺序，在窗口前排队买饭，先到先得，买完之后走开，轮到下一位买，新来的人排在队尾，不能插队。
可见，上面的“队”的特点是只允许从一端进入，从另一端离开。
这样的一个队，放在数据结构中就是“队列”。
首先，队列是一个线性表，所以它具有线性表的基本特点。
其次，队列是一个受限的线性表，受限之处为：只允许从一端进入队列，从另一端离开。
根据以上特点，可以画出示意图：
出队元素 1，入队元素 4 之后：
下面是几个相关名词：
入队：进入队列，即向队列中插入元素
出队：离开队列，即从队列中删除元素
队头：允许出队(删除)的一端
队尾：允许入队(插入)的一端
队头元素：队列中最先入栈的元素
队尾元素：队列中最后入栈的元素
我们可以直接将队头元素看作队头，队尾元素看作队尾。(这些名词概念，有所理解即可，不必细究)
队列的重要特性是在队尾进行入队操作，在队头进行出队操作，所以上图元素的入队顺序为：1、2、3，出队顺序为：1、2、3，也即，先入队的先出队(First In First Out, FIFO)，后入队的后出队(Last In Last Out, LILO).
总结一下，队列是一种只允许在一端进行插入操作，在另一端进行删除操作的先入先出的受限的线性表。
和栈一样，队列也可以有两种实现方式：数组实现的顺序队列和链表实现的链队列。
一个用数组实现的顺序队列如下图所示：
顺序队列
可以看到，要实现一个顺序队列，我们需要以下结构：
存储数据的数组 —— data[]
表示队列的最大容量的值 —— MAXSIZE
标识队头端的队头下标 —— front
标识队尾端的队尾下标 —— rear
front 和 rear 会随着入队和出队操作而变化，为了方便起见，我们规定在非空队列中，队尾下标是队尾元素的下一个元素的下标。
了解了结构之后，我们可以很容易使用 C 语言的结构体实现它：
#define MAXSIZE 5 //顺序队列的最大存储容量 /*顺序队列的结构体*/ typedef struct { int data[MAXSIZE]; int front; //队头下标 int rear; //队尾下标 } QueueArray;我们使用带头节点的单链表来实现队列，如下图所示：
链队列
可以看到，要实现一个链队列，需要以下结构：
1.单链表的基本单元结点 —— QueueNode
存储数据的数据域 —— data
指向下一个结点的指针域 —— next
2.指向链表的头指针 —— head
3.标识队头端的队头指针 —— front
4.标识队尾端的队尾指针 —— rear
其中，头指针 head 和队头指针 front 都指向了单链表的第一个结点，所以这个指针可以合二为一，队头指针即头指针。
如此一来，我们可以借助链表的尾插法实现队列的入队操作，借助链表的头删法实现队列的出队操作。
搞清了结构，用结构体实现如下：
/*单链表的结点的结构体*/ typedef struct QueueNode { int data; //数据域 struct QueueNode *next; //指针域 } QueueNode; /*链队列的结构体*/ typedef struct { QueueNode *front; //队头指针 QueueNode *rear; //队尾指针 } QueueLink;【空队列】：空队列中没有元素，此时，队头下标和队尾下标均为 0，即front = rear = 0：
空队列
【非空非满队列】：队列不是空队列且有剩余空间：
非空非满队列
【满队列】：顺序队列分配的固定空间用尽，没有多余空间，不能再插入元素，此时 front = 0，rear = MAXSIZE：
满队列
从上图中可以看出，非空队列的队尾下标 rear 始终是队尾元素的下一个元素的下标。
以上是用数组实现的顺序队列的三种状态，但上图中三种队列是存在问题的，那就是队列的存储问题!
先再次明确队列的两条重要特性：
队列只允许在队头删除元素，在队尾插入元素
我们规定：front 是队头元素的下标，rear 是队尾元素的下标，二者会随着出队和入队操作而变化
由于上面的三幅图中 front 都在下标 0 处，所以不容易看出问题，请看下面的过程图：
入队出队过程图
简单用文字描述以下上述过程：
图1：空队列
图2：进队 3 个元素：1、2、3
图3：出队 2 个元素：1、2
图4：入队 2 个元素：4、5
到此为止，一切正常。
图5：入队 1 个元素，但在图4中 rear = 5已经超出数组的最大范围，所以图5入队一个元素会报错，这个队列不能再插入元素了。
图5的队列满了吗?没满!能继续插入元素吗?不能!有剩余空间却不能用，这就好比有空房的酒店不让客户入住，这叫不会做生意。
满队列的是空间用尽，不能再插入元素的队列，虽然图5的队列也不能继续插入元素了，但它还有剩余空间，所以这样的队列还不能称之为满队列，可称之为假满队列。
之所以假满队列存在问题，是因为顺序队列的空间是有限的，通过若干入队操作之后，我们的 rear “跑”到数组外从而导致越界了。
假满队列
明明才存储了一个元素，却因为假满，整个队列不能再存储了。这样的队列肯定不是合格的数据结构。
怎么解决呢?报错是 rear 越界导致，而队列的前大部分都是空闲的，所以当 rear 越界时，我们可不可以将其移动到下标 0 处呢?
显然是可以的，这样就构成了一个“循环”，我们称这种 front 和 rear可以循环利用的队列为循环队列。
为了突出“循环”二字，我们将这种顺序队列画成一个圆：
循环队列
循环队列的 rear 和 front 能够在队列中一圈一圈地转，像钟表的时针和分针一样。不会再出现不能利用的空间了。
顺序队列的形式从“直的”变成这种可循环的之后，对于状态的判断也改变了。
【空队列】：队列中没有元素，如上图。
请注意，空队列的条件并不是 front = rear = 0，比如一个空队列经过 3 次入队和 3 次出队操作后仍为空队列：
空队列
所以，循环队列为空队列时，条件应该为 front = rear
【满队列】：队列中没有空闲空间
满队列
上图是一个最大容量为 8 的空队列，入队 7 个元素后，队列中还剩 1 个空闲位置，如果此时我们再入队 1 个元素：
是满队列吗?
此时队列中确实没有空闲空间了，但注意，此时队列满足了 rear = front ，但满足 rear = front的队列不应该是空队列吗?
这就产生误会了。
不如我们退一步海阔天空，少用一个元素，借此来消除误会。如下图，规定这样是一个满队列。
满队列
我们规定，front 出现在 rear 的下一个位置时，队列为满队列。
比如在上图的满队列中， front = 3 在 rear = 2 的下一个位置。
所以队列为满队列的判定条件为：rear + 1 = front，但这的条件是不准确的。
因为循环队列中的 front 和 rear 都是循环使用的，就像钟表的时针一样，所以我们仅根据下标的大小来判断位置是不合理的。下面两个均是满队列，右图不满足rear + 1 = front：
就像钟表的时针满 12 归零一样，front 和 rear 也应该满某个数后归零，这个数就是 MAXSIZE。
比如 rear = 7 时，如果按平常做法来 ，下一步应该是 rear = 8，但在这里，我们让其归零，所以下一步应该是 rear = 0。
用数学公式来表示上面的归零过程就是：rear % MAXSIZE
所以满队列的判断条件应该为：(rear + 1) % MAXSIZE = front。
【非空非满队列】：很好理解，不再赘述。
我们使用带头结点的单链表来实现链队列。
【空队列】：即一个空链表，此时队头指针(兼链表头指针)和队尾指针均指向头结点。
空队列
【非空队列】：不像顺序队列那样有空间的限制，链队列的空间是不受限制的(只要你的内存足够大)，所以自然不存在“满队列”“循环队列”的概念。
在进行队列的操作前，应该先将其初始化出来，即初始化一个空队列出来。
将队列的队头下标和队尾下标置为 0 即可。
/** * 初始化顺序队列：将队头下标和队尾下标置为0 * queue: 指向队列的指针 */ void init(QueueArray *queue) { queue->front = 0; queue->rear = 0; }创造出头结点，然后将队头指针和队尾指针均指向头结点即可。
/** * 初始化链队列：将队头指针和队尾指针指向头结点 */ void init(QueueLink *queue) { //创造头结点 QueueNode *head_node = create_node(0); //队头指针 队尾指针指向头结点 queue->front = head_node; queue->rear = head_node; }入队操作只允许元素从队尾进。
前面我们规定，顺序队列的队尾下标为队尾元素的下一个元素，所以直接将待入队元素放入队尾下标处，然后队尾下标“加一”。(注意：循环队列中的加一要对 MAXSIZE 取模)
入队过程
/** * 入队操作 * queue: 指向队列的指针 * elem: 入队的数据 * return: 0失败，1成功 */ int en_queue(QueueArray *queue, int elem) { //判断队列是否已满 if ((queue->rear + 1) % MAXSIZE == queue->front) { printf("队列已满，无法继续入队。\n"); return 0; } //元素入队 queue->data[queue->rear] = elem; //队尾下标加一 queue->rear = (queue->rear + 1) % MAXSIZE; return 1; }链队列的入队操作本质是单链表的尾插法：
/** * 入队操作 * queue: 指向队列的指针 * elem: 入队的数据 */ void en_queue(QueueLink *queue, int elem) { //创造新结点 QueueNode *new = create_node(elem); //入队（尾插法） queue->rear->next = new; queue->rear = new; }出队操作只允许元素从队头出。
将队头下标处的元素出队，然后将队头下标“加一”(对 MAXSIZE 取模)。
出队过程
/** * 出队操作 * queue: 指向队列的指针 * elem: 指向保存出队数据的变量 * return: 0失败，1成功 */ int de_queue(QueueArray *queue, int *elem) { //判读队列是否为空 if (queue->front == queue->rear) { printf("队列空，无元素可出。\n"); return 0; } //元素出队 *elem = queue->data[queue->front]; //队头下标加一 queue->front = (queue->front + 1) % MAXSIZE; return 1; }链队列的出队操作本质上是单链表的头删法。注意，如果出队的是队列中最后一个元素，需要在出队后，将队尾指针重新指向头结点，重新形成空队列。
/** * 出队操作 * queue: 指向队列的指针 * elem: 指向保存变量的指针 * return: 0失败，1成功 */ int de_queue(QueueLink *queue, int *elem) { //判读队列是否为空 if (queue->front == queue->rear) { printf("队列空，无元素可出。\n"); return 0; } QueueNode *front_node = queue->front->next; //队头元素 //保存数据 *elem = front_node->data; //队头元素出队（头删法） queue->front->next = front_node->next; //如果元素出完，队尾指针重新指向头结点 if (front_node == queue->rear) queue->rear = queue->front; free(front_node); }这里以打印整个队列为例，介绍如何遍历队列。
顺序队列有队头下标和队尾下标，链队列有队头指针和队尾指针，我们要做的就是借助一个临时变量，从队头下标逐个遍历到队尾下标即可。
借助临时变量 i，从队头下标开始逐个“加一”直到队尾下标结束。
开始标志为：i = front
加一操作为：i = (i + 1) % MAXSIZE
结束标志为：i % MAXSIZE = rear
/** * 打印队列 */ void output(QueueArray queue) { int i = queue.front; while (i % MAXSIZE != queue.rear) { printf("%d ", queue.data[i]); i = (i + 1) % MAXSIZE; } printf("\n"); }如何计算顺序队列的长度?当然你可以遍历队列然后借助计数变量来存储长度，这样比较麻烦。因为顺序队列是使用数组实现的，所以顺序队列的长度我们可以直接根据下标计算出来。
如果是一个非循环队列，那很简单，直接 rear - front 就是队列的长度了。
但循环队列不能这样直接减了，因为 rear 和 front 之间的位置关系是不确定的。
左图 rear < front，我们可以将其长度看成两部分组成：
下标 0 到 rear，长度为 rear - 0
下标 MAXSIZE - 1 到 rear，长度为 MAXSIZE - front
所以长度为 rear - front + MAXSIZE
为了满足右图 rear > front 的情况，如果按照上式，则此时多加了一个 MAXSIZE，所以需要对其再对 MAXIZE 取余。
所以循环队列的长度为 (rear - front + MAXSIZE) % MAXSIZE(空队列也满足)。
借助指针 p 从队头元素遍历至队尾元素即可。
/** * 打印队列 */ void output(QueueLink *queue) { QueueNode *p = queue->front->next; //p指向队头元素 while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); }到此，关于“队列的基本原理和操作方法”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！