队列采用如下图所示的循环单链表表示，图（a）表示队列为空，图（b）为e1、e2、e3依次..

免费智能真题库 > 历年试卷 > 程序员 > 2016年上半年程序员上午试卷综合知识

第36题

知识点：队列指针

关键词：队列链表指针章/节：常用数据结构

队列采用如下图所示的循环单链表表示，图（a）表示队列为空，图（b）为e1、e2、e3依次入队列后的状态，其中，rear指针指向队尾元素所在结点，size为队列长度。以下叙述中，正确的是（36）。

A. 入队列时需要从头至尾遍历链表，而出队列不需要

B. 出队列时需要从头至尾遍历链表，而入队列不需要

C. 新元素加入队列以及队头元素出队列都需要遍历链表

D. 入队列和出队列操作都不需要遍历链表

相关试题：队列、栈

更多>

第37题 2014年上半年

35%

以下关于栈和队列的叙述中，错误的是（37）。

第37题 2010年上半年

25%

队列是一种按“先进先出”原则进行插入和删除操作的数据结构。若初始队列为空，输入序列为abede，则可得到的输出序列为..

第35题 2016年上半年

35%

设有初始为空的栈S，对于入桟序列a、b、c、d，经由一个合法的进桟和出栈操作序列后（每个元素进栈、出栈各1次），以c作为第一个出..


知识点讲解
· 队列 · 指针

队列

队列的定义

队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头（front）。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。

由队列的定义可知，队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（First In First Out, FIFO）的原则组织数据的，因此，队列也被称为"先进先出"表。

下图是一个队列的进出示意图，通常用指针front指示队头的位置，用指针rear指向队尾的位置。

队列的进出示意图

队列的基本操作

队列的基本操作主要有以下6种。

.InitQueue（&Q）：初始化操作，构造一个队列Q。

.QueueEmpty（Q）：若栈Q为空队列，返回1，否则返回0。

.EQueue（&Q, e）：插入元素e到队列Q的尾部。

.OQueue（&Q,&e）：删除Q的队首元素，并用e返回其值。

.GetQhead（Q,&e）：用e返回Q的队首元素。

.ClearQueue（&Q）：将Q清空为空队。

队列的顺序存储结构

顺序存储结构采用一维数组（向量）实现，设队列头指针front和队列尾指针rear，并且假设front指向队头元素的前一位置，rear指向队尾元素。若不考虑队满，则入队操作语句为Q[rear++]=x；若不考虑队空，则出队操作语句为x=Q[++front]。当然，出队时，并不一定需要队头元素（与退栈类似）。

按上述的做法，有可能出现假溢出，即队尾已到达一维数组的高端，不能再入队，但因为连续出队，队列中元素个数并未达到最大值。解决这种问题，可用循环队列。在循环队列中，需要区分队空和队满：仍用front=rear表示队列空，在牺牲一个单元的前提下，用front==（rear+1）% MAX表示队列满。在这种约定下，入队操作的语句为：rear=（rear+1）%MAX, MAX, Q[rear]=x；出队操作语句为：front=（front+1）% MAX。

顺序队列的类型定义如下：

顺序队列定义为一个结构类型，该类型变量有3个数据域：data、front、rear。其中data为存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，取值范围是0~QueueSize-1。约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位置的前一个位置，这种顺序队列说明如下。

.初始化时，设置SQ.front=SQ.rear=0。

.队头指针的引用为SQ.front，队尾指针的引用为SQ.rear。

.队空的条件为SQ.front==SQ.rear；队满的条件为SQ.front=（SQ.rear+1）% QueueSize。

.入队操作：在队列未满时，队尾指针先加1（要取模），再送值到队尾指针指向的空闲元素。出队操作：在队列非空时，队头指针先加1（要取模），再从队头指针指向的队头元素处取值。

.队列长度为（SQ.rear+QueueSize-SQ.front）% QueueSize。

特别应注意的是：在循环队列的操作中队头指针、队尾指针加1时，都要取模，以保持其值不出界。

在循环队列上队列的实现基本操作的函数如下。

1）初始化initqueue（SQueue *SQ）

2）判空QueueEmpty（SQueue SQ）

3）入队EQueue（SQueue *SQ, ElemType e）

4）出队OQueue（SQueue *SQ, ElemType *e）

5）取队首元素GetQhead（SQueue *SQ, ElemType *e）

6）清队列ClearQueue（SQueue *SQ）

队列的链式存储结构

队列的链接实现称为链队，链队实际上是一个同时带有头指针和尾指针的单链表。头指针指向队头节点，尾指针指向队尾节点即单链表的最后一个节点。为了简便，链队设计成一个带头节点的单链表。

链队的类型定义如下：

链队列的说明如下。

.队列以链表形式出现，链首节点为队头，链尾节点为队尾。

.队头指针为LQ→front，队尾指针为LQ→rear，队头元素的引用为Q→front→data，队尾元素的引用为LQ→rear→data。

.初始化时，设置LQ→front=LQ→rear=NULL。

.进队操作与链表中链尾插入操作一样；出队操作与链表中链首删除操作一样。

.队空的条件为LQ→front==NULL。理论上，只要系统内存足够大，链队是不会满的。

在链队上实现队列基本操作的函数如下。

1）队列初始化InitQueue（LQueue *LQ）

2）入队EQueue（LQueue *LQ, ElemType e）

3）出队OQueue（LQueue *LQ, ElemType *e）

4）判空QueueEmpty（LQueue *LQ）

5）取队首元素GetQhead（LQueue *LQ, ElemType *e）

6）清队列ClearQueue（LQueue *LQ）

循环队列中的边界条件判别准则

判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一个布尔变量来区别队列的空和满；二是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满；三是设置一个计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

双端队列的作用

双端队列是限定插入和删除操作在线性表的两端进行，可将其看成是栈底连在一起的两个栈，但其与两个栈共享存储空间是不同的。共享存储空间中的两个栈的栈顶指针是向两端扩展的，因而每个栈只需一个指针；而双端队列允许两端进行插入和删除元素，因而每个端点必须设立两个指针，如下图所示。

双端队列的示意图

在实际应用中，可对双端队列的输出进行限制（即一个端点允许插入和删除，另一个端点只允许插入），也可对双端队列的输入进行限制（即一个端点允许插入和删除，另一个端点只允许删除）。可见，采用双端队列可增加应用中的灵活性。

指针

简单来说，指针是内存单元的地址，它可能是变量的地址、数组空间的地址，或者是函数的入口地址。存储地址的变量称为指针变量，简称为指针。指针是C语言中最有力的武器，能够为程序员提供极大的编程灵活性。

指针的定义

指针类型的变量是用来存放内存地址的，下面是两个指针变量的定义：

变量ptr1和ptr2都是指针类型的变量，ptr1用于保存一个整型变量的地址（称ptr1指向一个整型变量），ptr2用于保存一个字符型变量的地址（称ptr2指向一个字符变量）。

使用指针时需明确两个概念：指针对象和指针指向的对象。指针对象是明确命名的指针变量，如上例中的ptr1、ptr2；指针指向的对象是另一个变量，用“*”和指针变量联合表示，如上例中的整型变量*ptr1和字符变量*ptr2，由于上面的定义中未对ptr1和ptr2进行初始化，它们的初始值是随机的，也就是*ptr1和*ptr2可视为并不存在。

借助指针变量可以针对指定的地址进行操作，例如，设置地址为0x1234开始的存储空间存放一个整型变量的值0x5678，代码如下。

定义指针变量时需要在每个变量名前加“*”，如下：

指针的加减运算

对指针变量进行加减运算时，是以指针所指向的数据类型存储宽度为单位计算的。

例如，下面的指针p和s在进行加1运算时有不同的结果。

p+1实际上是按照公式p+1*sizeof（int）来计算的，s+1则是按照s+1*sizeof（char）进行计算。

空指针

标准预处理宏NULL（它的值为0，称为空指针常量）常用来表示指针不指向任何内存单元，可以把NULL赋给任意类型的指针变量，以初始化指针变量。例如：

需要注意：全局指针变量会被自动初始化为NULL，局部指针变量的初始值是随机的。编程时常见的一个错误是没有给指针变量赋初值。未初始化的指针变量可能表示了一个非法的地址，导致程序运行时出现内存访问错误，从而使程序异常终止。

“&”和“*”

“&”称为地址运算符，其作用是获取变量的地址。“*”称为间接运算符，其作用是获取指针所指向的变量。

例如，下面的语句“pa=&b；”执行后，变量pa就得到了b的地址（称为指针pa指向b），*pa表示pa指向的变量（也就是变量b）。

例如：

在上面的例子中，通过指针pa修改了变量b的值，本质上是对b的间接访问。在程序中通过指针访问数据对象或函数对象，提供了运算处理上的灵活性。

如果指针变量的值是空指针或者是随机的，通过指针来访问数据就是一种错误（在编译时报错，或者在运行时发生异常），下面的语句会产生一个运行时错误（vp可能表示了一个非法的地址，因此它所指向的对象*vp也是非法的）。

void*类型可以与任意的数据类型匹配。void指针在被使用之前，必须转换为明确的类型。例如：

指针与堆内存

在程序运行过程中，堆内存能够被动态地分配和释放，在C程序中通过malloc（或calloc、realloc）和free函数实现该处理要求。

例如：

在堆中分配的内存块的生存期是由程序员自己控制的，应在程序中显式地释放。例如：

注意：指针为空（指针值为0或NULL）时表示不指向任何内存单元，因此释放空指针没有意义。

因为内存资源是有限的，所以若申请的内存块不再需要就及时释放。如果程序中存在未被释放（由于丢失其地址在程序中也不能再访问）的内存块，则称为内存泄漏。持续的内存泄漏会导致程序性能降低，甚至崩溃。嵌入式系统存储空间非常有限，一般情况下应尽量采用静态存储分配策略。

指针与数组

通过指针访问数组元素

在C程序中，常利用指针访问数组元素，数组名表示数组在内存中的首地址，即数组中第一个元素的地址。可以通过下标访问数组元素，也可以通过指针访问数组元素。

例如：

数组arr的元素可以用*ptr、*（ptr+1）、*（ptr+2）、*（ptr+3）来引用。

数组名是常量指针，数组名的值不能改变，因此arr++是错误的，而ptr++是允许的。例如，下面的代码通过修改指针ptr来访问数组中的每个元素。

一般情况下，一个int型变量占用4个字节的内存空间，一个char型变量占用一个字节的空间，所以str是字符指针的话，str++就使str指向下一个字符；而整型指针ptr++则使ptr指向下一个int型整数，即指向数组的第二个元素。

可以用指针访问二维数组元素。例如，对于一个m行、n列的二维整型数组，其定义为

由于二维数组元素在内存中是以线性序列方式存储的，且按行存放，所以用指针访问二维数组的关键是如何计算出某个二维数组元素在内存中的地址。二维数组a的元素a[i][j]（ii][j]之前的元素所占空间形成的偏移量，概念上表示为a+（i×n+j）*sizeof（int），在程序中需要表示为（&a[0][0]+i×n+j）。

通过指针访问字符串常量

可将指针设置为指向字符串常量（存储在只读存储区域），通过指针读取字符串或其中的字符。例如，

不允许在程序运行过程中修改字符串常量。例如，下面代码试图通过修改字符串的第2个字符将“hello”改为“hallo”，程序运行时该操作会导致异常，原因是str指向的是字符串常量“hello”，该字符串在运行时不能被修改。

如果用const进行修饰，这个错误在编译阶段就能检查出来，修改如下：

指针数组

如果数组的元素类型是指针类型，则称之为指针数组。下面的ptrarr是一维数组，数组元素是指向整型变量的指针。

若需要动态生成二维整型数组，则传统的处理方式是先设置一个指针数组arr2，然后将其每个元素的值（指针）初始化为动态分配的“行”。

指针运算

在C程序中，对指针变量加一个整数或减一个整数的含义与指针指向的对象有关，也就是与指针所指向的变量所占用存储空间的大小有关。例如：

常量指针与指针常量

常量指针是指针变量指向的对象是常量，即指针变量可以修改，但是不能通过指针变量来修改其指向的对象。例如，

指针常量是指针本身是个常量，不能再指向其他对象。

在定义指针时，如果在指针变量前加一个const修饰符，就定义了一个指针常量，即指针值是不能修改的。

指针常量定义时被初始化为指向整型变量d。p本身不能修改（即p不能再指向其他对象），但它所指向变量的内容却可以修改，例如，*p=5（实际上是将d的值改为5）。

区分常量指针和指针常量的关键是“*”的位置，如果const在“*”的左边，则为常量指针，如果const在“*”的右边则为指针常量。如果将“*”读作“指针”，将const读作“常量”，内容正好符合。对于定义“int const *p；”p是常量指针，而定义“int* const p；”p是指针常量。

指针与函数

指针可以作为函数的参数或返回值。

指针作为函数参数

函数调用时，用指针作为函数的参数可以借助指针来改变调用函数中实参变量的值。以下面的swap函数为例进行说明，该函数的功能是交换两个整型变量的值。

若有函数调用swap（&x，&y），则swap函数执行后两个实参x和y的值被交换。函数中参与运算的值不是pa、pb本身，而是它们所指向的变量，也就是实参x、y（*pa与x、*pb与y所表示的对象相同）。在调用函数中，是把实参的地址传送给形参，即传送&x和&y，在swap函数中指针pa和pb并没有被修改。

如果在被调用函数中修改了指针参数的值，则不能实现对实参变量的修改。例如，下面函数get_str中的错误是将指针p指向的目标修改了，从而在main中调用get_str后，ptr的值仍然是NULL。