一个队列的入队序列为1234，则序列可能的输出序列是（ ）。
流918
题目答案为B.
分析：这是个典型的入队出队的题，因为队列的特性是先进先出，故1234,无论如何1都会先出，同理2排第2，...。
补充：可能你会想，如果出现，1进1出，2进3进2出3出，4进4出等等特殊情况，但是分析可以发现，无论进队出队是何种顺序，都将是1234的出队顺序。
编辑于 2019-04-23 14:34:52
回复(0)
选 B
队列是一种可以实现“先进先出”的存储结构。
队列通常可以分为两种类型：
一、顺序队列，采用顺序存储，当长度确定时使用。 顺序队列又有两种情况：
①使用数组存储队列的称为静态顺序队列。
②使用动态分配的指针的称为动态顺序队列。
二、链式队列，采用链式存储，长度不确定时使用（由链表实现）。
由于链式队列跟链表差不多，所以在这里只针对循环(环形)队列来说明并实践。
循环队列的两个参数：
①front,front指向队列的第一个元素。(front==head)
②rear,rear指向队列的最后一个有效元素的下一元素。(rear==tail)
队列的两个基本操作：出队和入队。
二、队列的结构
下面是一个循环队列（基于数组实现）的结构图：
三、队列的操作
入队（尾部入队）
①将值存入rear所代表的位置。
②rear = (rear+1)%数组的长度。
出队（头部出队）
front = (front+1)%数组的长度。
队列是否为空
front和rear的值相等，则该队列就一定为空。
队列是否已满
在循环队列中,“队满”和“队空”的条件有可能是相同的，都是front ==rear，这种情况下，无法区别是“队满”还是“队空”。
针对这个问题，有3种可能的处理方法： 【这里采用了第3种处理方法】
- （1）另设一个标志以区别是“队满”还是“队空”。（即入队/出队前检查是否“队满”/“队空”）
- （2）设一个计数器，此时甚至还可以省去一个指针。
- （3）少用一个元素空间，即约定队头指针在队尾指针的下一位置时就作为“队满”的标志，即“队满”条件为：(pQueue->rear+1)%MAX_SIZE == pQueue->front。
四、队列的一些问题以及解决办法
从上图可以看出，随着入队、出队的进行，会使整个队列整体向后移动，就会出现上图中的现象：队尾指针已经移到了最后，即队尾出现溢出，无法再进行入队操作，然而实际上，此时队列中还有空闲空间，这种现象称为“假溢出”。
解决“假溢出”的三种办法：
- 方法一：每次删除队头元素后，把整个队列向前移动一个位置，这样可保证队头元素在存储空间的最前面。但每次删除元素时，都要把表中所有元素向前移动，效率太低。
- 方法二：当队尾指针出现溢出时，判断队头指针位置，如果前部有空闲空间，则把当前队列整体前移到最前方。这种方法移动元素的次数大为减少。
- 方法三：将队列看成头尾相接的循环结构，当队尾指针到队尾后，再从队头开始向后指，这样就不需要移动队列元素了，显然，第三种方法最经济、应用最多，这种顺序队列被称为“循环队列”或“环形队列”。
采用了这种头尾相接的循环队列后，入队的队尾指针加1操作及出队的队头指针加1操作必须做相应的修改，以确保下标范围为0~Max_Size-1。对指针进行取模运算，就能使指针到达最大下标位置后回到0，符合“循环”队列的特点。
因此入队时队尾指针加1操作改为： pQueue->tail = (pQueue->tail+1) % MAX_SIZE;
入队时队尾指针加1操作改为： pQueue->head = (pQueue->head+1) % MAX_SIZE;
发表于 2019-04-22 15:41:14
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
