04. 【解答】
## 04. 【解答】 算法思想：使用栈来判断链表中的数据是否中心对称。让链表的前一半元素依次入栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，对两个元素进行比较，若相等，则将链表中的下一个元素与栈中再弹出的元素进行比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中的一个元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。 本题代码如下：本题的关键在于，两个栈入栈和出栈时的栈顶指针的计算。S1 栈是通常意义下的栈；而 S2 栈入栈操作时，其栈顶指针左移（减 1），出栈时，栈顶指针右移（加 1）。 此外，对于所有栈的操作，都要注意“入栈判满、出栈判空”的检查。 （1）入栈操作 代码如下：int dc(LinkList L,int n){ int i; char s[n/2]; //s字符栈 LNode *p=L-&gt;next; //工作指针p，指向待处理的当前元素 for(i=0;i<n 0;="" 1="" 2;="" i++){="" if(n%2="1)" if(n%2==1)="" int="" p="p-&gt;next;" p:="" {="" }="" }i="">&gt;next; while(p!=NULL&amp;&amp;s[i]==p-&gt;data){ //检测是否中心对称 i--; //i充当栈顶指针 p=p-&gt;next; } if(i==-1) //栈为空栈 return 1; //链表中心对称 else return 0; //链表中心不对称 }</n> <!-- page: 87 --> 第3章 栈、队列和数组 算法先将“链表的前一半”元素（字符）入栈。当 n 为偶数时，前一半和后一半的个数相同；当 n 为奇数时，链表中心结点字符不必比较，移动链表指针到下一字符开始比较。比较过程中遇到不相等时，立即退出 while 循环，不再进行比较。 本题也可以先将单链表中的元素全部入栈，然后扫描单链表 L 并比较，直到比较到单链表 L 尾为止，但算法需要两次扫描单链表 L，效率不及上述算法高。 ## 05. 【解答】 两个栈共享向量空间，将两个栈的栈底设在向量两端，初始时，S1 栈顶指针为 -1，S2 栈顶指针为 maxsize。两个栈顶指针相邻时为栈满。两个栈顶相向、迎面增长，栈顶指针指向栈顶元素。 本题代码如下： ```c #define maxsize 100 //两个栈共享顺序存储空间所能达到的最多元素数，//初始化为100 #define elemtp int //假设元素类型为整型 typedef struct{ elemtp stack[maxsize]; //栈空间 int top[2]; //top为两个栈顶指针 }stk; stk s; //s是如上定义的结构类型变量，为全局变量（2）出栈操作 代码如下：int Push(int i, elemtp x) { //入栈操作。i为栈号，i=0表示左边的S1栈，i=1表示右边的S2栈，x是入栈元素 //入栈成功返回1，否则返回0 if(i&lt;0||i&gt;1){ printf("栈号输入不对"); exit(0); } if(s.top[1]-s.top[0]==1){ printf("栈已满\n"); return 0; } switch(i){ case 0: s.stack[++s.top[0]]=x; return 1; break; case 1: s.stack[--s.top[1]]=x; return 1; } }## 3.2 队列 ### 3.2.1 队列的基本概念 #### 1. 队列的定义 队列（Queue）简称队，也是一种操作受限的线性表，仅允许在表的一端进行插入，而在另一端进行删除。向队列中插入元素称为入队（或进队），删除元素称为出队（或离队）。这一规则符合日常排队“先到先服务”的原则，因此队列的操作特性为先进先出（First In First Out，FIFO），如图 3.5 所示。elemtp Pop(int i) { //出栈算法。i代表栈号，i=0时为S1栈，i=1时为S2栈 //出栈成功返回出栈元素，否则返回-1 if(i&lt;0||i&gt;1){ printf("栈号输入错误\n"); exit(0); } switch(i){ case 0: if(s.top[0]==-1) { <!-- page: 88 --> 2027年数据结构考研复习指导 ```c printf("栈空\n"); return -1; } else return s.stack[s.top[0]--]; break; case 1: if (s.top[1] == maxsize) { printf("栈空\n"); return -1; } else return s.stack[s.top[1]++]; break; //switch
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 3.5 队列示意图 队头（Front）：允许删除的一端，也称队首。 队尾（Rear）：允许插入的一端。 空队列：不含任何元素的队列。 #### 2. 队列常见的基本操作 InitQueue(&Q)：初始化队列，构造一个空队列 Q。 QueueEmpty(Q)：判队列空；若队列 Q 为空，返回 true，否则返回 false。 EnQueue(&Q, x)：入队操作；若队列 Q 未满，将 x 加入队尾。 DeQueue(&Q, &x)：出队操作；若队列 Q 非空，删除队首元素，并通过 x 返回其值。 GetHead(Q, &x)：读队首元素但不出队；若队列 Q 非空，将队首元素赋值给 x。 需要注意的是，栈和队列均为操作受限的线性表，因此并非所有线性表的操作都适用于它们。例如，不允许直接访问或修改栈或队列中间的元素，这是由其逻辑特性所决定的。 ### 3.2.2 队列的顺序存储结构 #### 1. 队列的顺序存储 队列的顺序实现是指分配一块连续的存储单元存放队列元素，并附设两个指针：队首指针 front 指向队首元素，队尾指针 rear 指向队尾元素的下一个位置。不同教材对 front 和 rear 指针含义的约定可能不同（例如，rear 可能指向队尾元素或其下一位置），这会导致入队和出队操作的具体实现不同。本节后附有相关习题，建议读者结合练习深入理解。 <!-- page: 89 --> 第3章 栈、队列和数组 77 队列的顺序存储类型可定义为 初始状态：Q.front=Q.rear=0。 入队操作：当队列未满时，先将元素存入队尾，再将队尾指针加1。 出队操作：当队列非空时，先取出队首元素，再将队首指针加1。 如图3.6(a)所示，初始时空队列满足Q.front==Q.rear==0，该条件可作为判空依据。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 空队
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 5个元素入队
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 出队1次
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(d) 出队3次 图3.6 队列的操作 然而，能否以Q.rear==MaxSize作为队满条件呢？显然不能。如图3.6(d)所示，队列中仅剩一个元素，但rear已达MaxSize，若此时继续入队，则会出现“上溢”。但这种溢出并非真正溢出，实际上数组中仍有空闲单元，因此称此现象为假溢出。 ## 2. 循环队列 为了解决顺序队列的假溢出问题，引入循环队列：将顺序存储空间在逻辑上组织为环状结构。当指针到达数组末尾时，自动回到起始位置，这可通过取模运算（%）实现。 **特点指针** ⊞ 特定条件下循环队列队头/队尾指针的初值（2011） 初始状态：Q.front=Q.rear=0。 队首指针进1：Q.front=(Q.front+1)%MaxSize。 队尾指针进1：Q.rear=(Q.rear+1)%MaxSize。 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize。 出入队操作：指针均按顺时针方向移动（见图3.7）。 **特点指针** ⊞ 循环队列判空/满的条件（2014） 那么，循环队列判空和判满的条件是什么呢？队空条件显然为Q.front==Q.rear。但当入队速度远快于出队时，rear会追上front，此时同样满足Q.front==Q.rear，却表示队满。因此，仅凭front==rear无法区分队空与队满。循环队列出入队的示意图如图3.7所示。 为解决这一问题，常用以下三种方法： 1）牺牲一个存储单元：入队时少用一个存储单元，这是一种较为普遍的做法，约定以“队尾指针的下一位置为队首”作为队满标志，如图3.7(d2)所示。 队满条件：(Q.rear+1)%MaxSize==Q.front。 队空条件：Q.front==Q.rear。 队列中元素个数：(Q.rear-Q.front+MaxSize)%MaxSize。 2）增设 size 成员：记录当前元素个数。若入队成功，则 size++，若出队成功，则 size--。 队空条件：Q.size==0。 <!-- page: 90 --> 2027年数据结构考研复习指导
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)初始空队
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) a、b、c入队
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) a出队
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(d1) d、e、f、g入队 （无法判断队满还是队空）
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(d2) d、e、f入队 （牺牲一个存储单元） 图3.7 循环队列出入队的示意图 队满条件：Q.size==MaxSize。 两种情形均有Q.front==Q.rear，由size区分队空与队满。 3）增设tag标志位： 出队后置 tag=0，若此时 Q.front==Q.rear，则为队空。 入队后置 tag=1，若此时 Q.front==Q.rear，则为队满。 3.循环队列的操作（基于牺牲一个单元法） （1）初始化 （2）判队空 （3）入队 （4）出队 ## 3.2.3 队列的链式存储结构 ### 1. 队列的链式存储 **带点信息** ▶ 链式队列的应用场景（2019） 队列的链式表示称为链式队列，本质上是一个同时带有队首指针和队尾指针的单链表，如图3.8所示。队首指针指向队头结点，队尾指针指向队尾结点，即单链表的最后一个结点。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.8 不带队头结点的链式队列 链式队列的类型可定义为 当不带头结点时，若 Q.front == NULL 且 Q.rear == NULL，则链式队列为空队列。 **带点信息** ▶ 链式队列判空的条件（2019） 入队操作：创建一个新结点，将其插入链表尾部，并令 Q.rear 指向该结点；若原队列为空，则同时令 Q.front 也指向该结点。 出队操作：先判断队列是否为空；若非空，则取出队首元素，删除对应结点，并令 Q.front 指向下一个结点；若被删结点是最后一个元素，则将 Q.front 和 Q.rear 均置为 NULL。 不难发现，不带头结点的链式队列在边界处理上较为烦琐。因此，通常将链式队列设计为带头结点的单链表，从而使插入与删除操作逻辑统一，如图3.9所示。 链式队列特别适用于元素数量频繁变化的场景，且不存在队满或溢出问题。此外，若程序中需使用多个队列（如同多个栈的情形），优先选用链式队列可避免存储分配不合理或溢出等问题。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.9 带队头结点的链式队列 ### 2. 链式队列的基本操作 **带点信息** ▶ 链式队列出队/入队操作的基本过程（2019） #### （1）初始化#### （2）判队空void InitQueue(LinkQueue &amp;Q) { //初始化带头结点的链式队列 Q.front = Q.rear = (LinkNode*) malloc(sizeof(LinkNode)); //建立头结点 Q.front -&gt; next = NULL; //初始为空 }（3）入队 （4）出队 ## 3.2.4 双端队列 双端队列是一种允许在两端进行插入和删除操作的线性表，如图3.10所示。双端队列两端的地位是平等的，为便于理解，可将左端视为前端，右端视为后端。bool QueueEmpty(LinkQueue Q) { <!-- page: 92 --> 2027年数据结构考研复习指导 ```c if(Q.front==Q.rear) //判空条件 return true; else return false;
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.10 双端队列 在双端队列入队时：前端插入的元素排列在队列中后端插入的元素之前；后端插入的元素排列在队列中前端插入的元素之后。在双端队列出队时：无论是从前端还是后端出队，先出的元素总是排列在后出的元素之前。思考：如何由入队序列 $a, b, c, d$ 得到出队序列 $d, c, a, b$？ **有关表格** 双端队列出入队操作的分析（2010、2021） 输出受限的双端队列：允许在一端进行插入和删除，但在另一端仅允许插入的双端队列称为输出受限的双端队列，如图3.11所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.11 输出受限的双端队列 输入受限的双端队列：允许在一端进行插入和删除，但在另一端仅允许删除的双端队列称为输入受限的双端队列，如图3.12所示。若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈。 <!-- page: 93 --> 第3章 栈、队列和数组 81
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.12 输入受限的双端队列
例 设有一个双端队列，输入序列为 1,2,3,4，试分别求出以下条件的输出序列。
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。
（3）既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。
解：先看输入受限的双端队列，见图3.13。假设end1端输入1,2,3,4，则end2端的输出相当于普通队列的输出，即1,2,3,4；而end1端的输出相当于栈的输出， $n = 4$ 时仅通过end1端有14种输出序列（由Catalan公式得出），仅通过end1端不能得到的输出序列有 $4! - 14 = 10$ 种：
1,4,2,3
2,4,1,3
3,4,1,2
3,1,4,2
3,1,2,4
4,3,1,2
4,1,3,2
4,2,3,1
4,2,1,3
4,1,2,3
通过 end1 和 end2 端混合输出，可以输出这 10 种中的 8 种，参见下表。其中， $S_{\mathrm{L}}, X_{\mathrm{L}}$ 分别代表 end1 端的入队和出队， $X_{\mathrm{R}}$ 代表 end2 端的出队。
| 输出序列 | 入队出队顺序 | 输出序列 | 入队出队顺序 |
| --- | --- | --- | --- |
| 1,4,2,3 | SLXRSLLSLXLXLXR | 3,1,2,4 | SLLSLLSXLXLXLXR |
| 2,4,1,3 | SLLSLXLLSLXLXLXR | 4,1,2,3 | SLLSLLSLXLXLXLXR |
| 3,4,1,2 | SLLSLLSLXLXLXLXR | 4,1,3,2 | SLLSLLSLXLXLXLXR |
| 3,1,4,2 | SLLSLLSLXLXRSLXLXR | 4,3,1,2 | SLLSLLSLXLXLXLXR |
剩下的两种是不能通过输入受限的双端队列输出的，即4,2,3,1和4,2,1,3。
再看输出受限的双端队列，见图3.14。假设end1和end2端都能输入，仅end2端可以输出。若都从end2端输入，则就是一个栈。当输入序列为1,2,3,4时，输出序列有14种。对于其余10种不能得到的输出序列，通过交替从end1和end2端输入，还可以输出其中8种。设 $S_{\mathrm{L}}$ 代表end1端的输入， $S_{\mathrm{R}}$ 、 $X_{\mathrm{R}}$ 分别代表end2端的输入和输出，则可能的输出序列见下表。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.13 例题中输入受限的双端队列
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.14 例题中输出受限的双端队列 | 输出序列 | 入队出队顺序 | 输出序列 | 入队出队顺序 | | --- | --- | --- | --- | | 1,4,2,3 | SLXRSLLSLXR | 3,1,2,4 | SLLSLXR | | 2,4,1,3 | SLXRRSLXR | 4,1,2,3 | SLLSLXR | | 3,4,1,2 | SLLSLXRRSLXR | 4,2,1,3 | SLXRRSLXR | | 3,1,4,2 | SLLSLXRRSLXR | 4,3,1,2 | SLXRRSLXR | 通过输出受限的双端队列不能得到的两种输出序列是 4,1,3,2 和 4,2,3,1。 综上所述： 1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的是4,1,3,2。 2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的是4,2,1,3。 3）既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的是4,2,3,1。 <!-- page: 94 --> 2027年数据结构考研复习指导