第三章栈和队列.doc

第三章 栈和队列一选择题 1栈与一般线性表的区别在于_。 A数据元素的类型不同 B运算是否受限制 C数据元素的个数不同 D逻辑数据不同 分析：该题目主要考查栈的定义。栈属于特殊的线性表，特殊性在于其删 除和插入操作只能够在栈顶进行，是一种运算受到限制的线性表。答案为 。 2一个顺序栈旦被声明，其占用空间的大小_。 A已固定 B可以改变 C不能固定 D动态变化 分析：该题目主要考查顺序栈存储结构的特点。顺序栈用数组实现，因此 一旦顺序栈被声明，则其空间大小固定。答案应选择 A。 3设有顺序栈 S，元素 s1,s2,s3,s4,s5,s6 依次进栈，如果 6 个元素出 栈的顺序是 s2,s4,s3,s6,s5,s1，则栈的容量至少应该是_。 A3 B4 C5 D6 分析：该题目主要考查顺序栈的存储空间定义。当 s2 出栈时，则栈的容量 为 2(s1,s2 在栈中)；当 s4 出栈时，则栈的容量为 3(s1,s3,s4 在栈中)； 当 s6 出栈时，则栈的容量为 3(s1,s5,s6 在栈中)；因此栈的最小容量应为 3。答案应选择 A。 4 从一个栈顶指针为 top 的链栈中删除一个结点时，用 x 保存被删除的 结点，执行_。 Ax=top-data；top=top-next； Btop=top-next；x=top； Cx=top-data； Dx=top；top=top-next； 分析： 该题目主要考查链栈的具体操作。首先将指针变量 x 保存被删除结点，然后调整栈顶指针(top=top-next)。选项 A 中，x=top-data 操作目 的是将栈顶结点的元素值赋给 x，故无法满足题目要求。选项 B 中，首先进 行栈顶指针 top 调整，则 x 保存的不是当前删除的结点，而是栈调整后的 栈顶元素。因此答案应选择 D。 5在个栈顶指针为 top 的链栈中，将一个 s 指针所指的结点入栈，执行 _。 Atop-nexts： B s-next=top-next; top-next=s; Cs-next=top; tops； Ds-next=top; top=top-next; 分析：该题目主要考查链栈的具体操作。根据链栈入栈操作定义，即可得 到答案。答案为 C。从选择题 4、5 可以看出，链栈的入栈和出栈操作实质 上是对没有头结点的单链表进行插入与删除操作。 6链栈和顺序栈相比，有一个比较明显的优点，即_。 A插入操作更加方便 B通常不会出现栈满的情况 C不会出现栈空的情况 D删除操作更加方便 分析： 该题目主要考查链栈和顺序栈的特点。 栈的两种存储方式各有特点， 即顺序栈所需存储空间较少，但栈的大小受数组的限制；链栈由于每个结 点都包含数据域和指针域，则所需空间相对较大，但栈的大小不受限制(受 内存容量的限制)。所以答案为 B。对顺序栈而言，其插入操作(入栈)不需 要大量地移动元素，故插入操作(入栈)则不是链栈的优点，因此 A 选项说 法有问题。 7用单链表表示的链式队列的队头在链表的_位置。 A链头 B链尾 C链中 D任意位置 分析：该题目主要考查链式队列的存储结构，如图 3.2 所示。队列的队头 是对队列元素进行删除的一端，链队列的队头在链表的链头位置。 (不考虑不包含数据元素的头结点)，答案为 A。 图 3.2 链式队列 8在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数 据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲 区中取出数据打印。该缓冲区应该是一个_结构。 A堆栈 B队列 C数组 D线性表 分析：该题目主要考查队列的性质和应用。缓冲区中的数据应该是先到达 的先打印，所以使用具有 FIFO 性质的队列来实现。答案为 B。 9做入栈运算时，应先判断栈是否为 (1) ，做出栈运算时，应先判 断栈是否为 (2) 。当顺序栈中元素为 n 个，做入栈运算时发生上溢， 则说明该栈的最大容量为 (3) 。为了增加内存空间的利用率和减少发 生上溢的可能性，由两个顺序栈共享一片连续的内存空间时，应将两栈的 (4) 分别设在这片内存空间的两端，这样，只有当 (5) 时，才产生上 溢。 (1)、(2)A空 B满 C上溢 D下溢 (3) An-l Bn Cn1 Dn2 (4) A长度 B深度 C栈顶 D栈底 (5) A两个栈的栈顶同时到达栈空间的中心点 B其中一个栈的栈顶到达栈空间的中心点 C两个栈的栈顶在栈空间的某一位置相遇 D两个栈均不为空,且一个栈的栈顶到达另一个栈的栈底 分析：该题目主要考查栈的性质、结构和操作。答案为：(1)B (2)A (3)B a1 a2 . an front rear(4) D (5) C 10 若已知一个栈的入栈序列是 l,2,3, ,30 ， 其输出序列是 p1,p2,p3,pn，若 p130，则 p10 为_。 A 11 B 20 C 30 D 2l 分析：该题目主要考查栈的性质、结构和操作。已知数据的入栈序列是 l， 2，3，30，出栈序列的第 1 个元素是 30，因此可以确定，所有元素是 按入栈序列顺序全部入栈之后才开始出栈的。也就是说，出栈序列与入栈 序列刚好相反，可求得出栈序列的第 10 个元素为 21，即 D 答案正确。 11循环队列 Am存放其元素，用 front 和 rear 分别表示队头及队尾，则 循环队列满的条件是_。 A(Q-rear+1)%m=Q-front BQ-rear=Q-front+1 CQ-rear+1=Q-front DQ-rear=Q-front 分析：该题目主要考查循环队列的存储结构以及队满的判断条件。循环队 列的引入是为了解决队列存在的“假溢出”问题，但在循环队列中会出现 队满和队空的判断条件相同而导致无法判断，通常采用少用一个元素空间 的策略来解决该问题(其它策略讲解请参考配套教材)。 使队尾指针 Q-rear 无法赶上 Q-front，即队尾指针加 1 就会从后面赶上队头指针，这种情况 下队满的条件是：(Q-rear+1) %m= Q-front。答案是 A。 12 设数组 datam作为循环队列 sq 的存储空间， front 为队头指针， rear 为队尾指针，则执行出队操作后其头指针 front 值为_。 Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m 分析：该题目主要考查循环队列的存储结构和出队操作。队列的头指针指 向队首元素的实际位置，因此出队操作后，头指针需向上移动一个元素的 位置。根据第 11 题的解答可知，循环队列的容量为 m，所以头指针 front加 1 以后，需对 m 取余，使之自动实现循环，即当 front 取到最大下标(m-1 处)以后，自动循环回来取 0 值。所以答案是 D。 13由两个栈共享一个向量空间的好处是_ 。 A减少存取时间，降低下溢发生的机率 B节省存储空间，降低上溢 发生的机率 C减少存取时间，降低上溢发生的机率 D节省存储空间，降低下溢 发生的机率 分析：该题目主要考查对顺序栈存储结构的理解。两个栈无论是共享向量 空间还是单独分配空间，对它们的操作所需的时间没有影响。两个栈共享 向量空间，主要是为了节省存储空间，降低上溢的发生机率，因为当一个 栈中的元素较少时，另一个栈可用空间可以超过向量空间的一半。答案应 选择 B。 14若用单链表来表示队列，则应该选用_。 A带尾指针的非循环链表 B带尾指针的循环链表 C带头指针的非循环链表 D带头指针的循环链表 分析：本题主要考查读者对循环单链表存储结构和队列定义的理解。设尾 指针 rear，则通过 rear 可以访问队尾，通过 rear-next 可以访问队头， 因此带尾指针的循环链表较适合。答案应选择 B。 二判断题 1消除递归不一定需要使用栈，此说法是否正确。 正确 分析：该题目主要考查栈在递归中的应用。对于尾递归可以将其转化成递 推，不需栈。所以这种说法是正确的。 尾递归是指一个递归函数的递归调用语句是递归函数的最后一句可执行语句。 例如下面是一个输出数组元素的递归函数。 void RPrintArray(int list,int n) if(n=0) printf(“%d”,listn); RPrintArray(list,-n); 此程序是尾递归程序，消除尾递归很简单，只需首先计算新的 n 值， n=n-1，然后程序转到函数的开始处执行就行了，可以使用 while 语句来实 现。 相应非递归函数如下： void PrintArray(int list,int n) while (n=0) printf(“%d”,listn); -n; 2栈和队列都是限制存取点的线性结构。 正确 分析：该题目主要考查栈和队列的定义。它们都只能在一端或两端存取数据的线性结构。见选择题第 1 题解答。 3入栈操作、出栈操作算法的时间复杂性均为 O(n)。 错误 分析：该题目主要考查栈的操作算法。入栈与出栈操作都在确定的栈顶位 置进行，算法的时间复杂性均为 O(1)。所以这种说法是错误的。 4队列逻辑上是一个下端和上端既能增加又能减少的线性表。 错误 分析：该题目主要考查队列的逻辑结构和操作。队列是上端只能进行入队 操作(即增加操作)，下端只能进行出队操作(即减少操作)。 5用 I 代表入栈操作，O 代表出栈操作，栈的初始状态和栈的最终状态都 为空，则使用栈的入栈和出栈可能出现的操纵序列为 IOIOIOOI。 错误 分析：该题目主要考查栈的操作和“溢出”问题。在栈的操作中，保证出 栈前提是栈中有元素，否则会造成栈的下溢，IOIOIOOI 会出现下溢。 6任何一个递归过程都可以转换为非递归过程。 正确 分析：该题目主要考查栈在递归过程非递归化中的应用。任何一个递归过 程都可以按照一定的步骤机械地转换为非递归过程。由于栈的后进先出特 性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法。递归 过程转换为非递归过程的实质就是将递归中隐含的栈机制转化为由用户直 接控制的栈，利用堆栈保存参数。 三填空题 1已知一个栈的输入序列为 abcd，判断下面两个序列能否通过栈的 Push_Stack 和 Pop_Stack 操作输出：(1)dbca (1) (2)cbda (2) 答案：(1)不能 (2)能 分析：该题目主要考查栈的操作。(1)不能，因为弹出 d 时，abc 均已依次 压入栈，下一个弹出的元素只能是 c 而不是 b。(2)能，Push_Stack (s,a)， Push_Stack (s,b)，Push_Stack (s,c)，Pop_Stack (s)，Pop_Stack (s)， Push_Stack (s,d), Pop_Stack (s), Pop_Stack (s)。 2对循环队列 Q(设循环队列空间大小为 MAXSIZE)，如何修改队头指针? (1) ； 如何修改队尾指针? (2) 答案：(1)front=(front+1)% MAXSIZE (2)rear=(rear+1)% MAXSIZE 分析：该题目主要考查循环队列的操作。具体解答请参见选择题第 11 和 12 题。 3设长度为 n 的链队列用单循环链表表示，若只设头指针，则入队列出队 列操作的时间分别为 (1) 和 (2) ；若只设尾指针，则入队列出队列 操作的时间分别为 (3) 和 (4) 。 答案：(1)O(n) (2)O(n) (3)O(1) (4)O(1) 分析：该题目主要考查链队列和单循环链表的综合知识。当只设头指针时 (如图 3.3(a)所示)，入队相当于在 an 结点之后执行结点插入操作，根据链 表的插入操作特点可知，插入操作前必须知道结点 a1 和 an 的地址，获取结 点 an 的地址的时间复杂度为 O(n)；出队则相当于删除结点 a1 的操作，因此 必须获取结点 an 的地址，同样其时间复杂度为 O(n)。若设置尾指针(如图 3.3(b)，入队相当于在结点 a1 之前和 an 之后执行结点插入操作，通过 rear 和 rear-next 可以获得结点 an 和 a1 的地址，则其时间复杂度为 O(1)；出 队则相当于删除结点 a1 的操作，同样其时间复杂度为 O(1)。(a) (b) 图 3.3 单循环链表表示的链队列示意图 4对于循环向量中的循环队列，写出求队列中元素个数的公式 _。 答案： (rear-frontMAXSIZE)% MAXSIZE，其中 MAXSIZE 表示队列的存 储空间。 分析：该题目主要考查循环队列的存储结构特点。 5向顺序栈插入新元素分为三步：第一步，进行 (1) 判断，判断条件 是 (2) ；第二步是修改 (3) ；第三步把新元素赋给 (4) 。同样从 顺序堆栈删除元素分为三步；第一步，进行 (5) 判断，判断条件是 (6) ；第二步是把 (7) 值返回；第三步 (8) 。 答案：(1)栈是否满(2)s-top= MAXSIZE -1(3)栈顶指针(top+)(4)栈 顶对应的数组元素(5)栈是否空(6)stop=-1(7)栈顶元素(8)修改栈顶指 针(top-) 分析：该题目是考虑栈的运算规则及其入出栈的实现步骤。入栈时一般考 虑判断栈满否，条件是是否超出最大空间。如果没有超出应该修改栈顶指 针，然后将元素压入堆栈。出栈时，应首先考虑堆栈是否空。如果不空， 先保留栈顶元素，然后修改栈顶指针。 6在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要 使用栈。对于前者，进入栈的元素为表达式中的 (1) ，而对于后者，进 入栈的元素为 (2) 。中缀表达式(a+b)/c-(f-d/e)所对应的后缀表达式 a1 a2 . an head a1 a2 . an rear是 (3) 。 答案：(1)运算符 (2)操作数 (3)ab+c/fde/- 分析：该题目主要考查栈的应用。中缀表达式就是将运算符写于参与运算 的操作数的中间，操作数依原序排列。后缀表达式就是将运算符列于参与 运算的操作数之后，操作数的排列依原序。因此计算后缀表达式值的过程 为：从左向右扫描后缀表达式，遇到操作数就进栈，遇到运算符就从栈中 弹出两个操作数，执行该运算符所规定的运算，并将所得结果进栈。如此 下去，直到表达式结束。所以对于计算后缀表达式，进栈的元素为操作数。 7假设以 S 和 X 分别表示入栈和出栈操作，则对输入序列 a，b，e，d，e 进行一系列栈操作 SSXSXSSXXX 之后，得到的输出序列为_。 答案：bceda 分析：该题目主要考查入栈和出栈操作。入栈和出栈操作只能在栈顶位置 进行。根据操作序列，首先 a，b 进栈，然后 b 出栈；接着 c 进栈、c 出栈； d、e 相继进栈，栈顶元素为 e，最后 e、d、a 相继出栈。这样，得到出栈 序列为 bceda。 四应用题 1将整数 1、2、3、4 依次入栈或出栈，请回答下述问题： (1)当入、出栈次序为 Push_Stack(S，1)、Pop_Stack(S)、Push_Stack(S， 2)、Push_Stack(S，x3)、Pop_Stack(S)、Push_Stack(S，4)、Pop_Stack(S)， 出栈的数字序列为何？ (2)能否得到出栈序列1423和1432？并说明为什么不能得到或者如何得到。 (3)设有 n 个数据元素的序列顺序进栈，试给出可能输出序列的个数和不可 能输出序列的个数。当 n=4(1、2、3、4)有 24 种排列，哪些序列是可以通 过相应的入出栈操作得到的。分析与解答：该题目主要考查栈的性质、结构和操作。 (1) 出栈序列为 l、3、4。 (2) 序列 1、4、2、3 不可能得到。因为 4 和 2 之间隔了 3，当 4 出栈 后， 栈顶元素是 3， 而 2 在 3 的下面。 序列 1、 4、 3、 2 可以得到： Push_Stack(S， 1)、Pop_Stack(S)、Push_Stack(S，2)、Push_Stack(S，3)、Push_Stack(S， 4)、Pop_Stack(S)、Pop_Stack(S)、Pop_Stack(S)。 (3) 设有 n 个数据元素的序列(假设这个序列为 1，2，3，4，5n) 顺序进栈，那么输出序列个数 f(n)可以递推求出：为讨论方便, 设 n=0, f(0)=1，当， n=1：显然 f(1)=1 n=2：容易得知 f(2)=2 n=3：1 最后出栈的序列有 f(2)种，2 最后出栈的序列有 f(1)* f(1)种， 3 最后出栈的序列有 f(2)种，所以 f(3)=2* f(2)+f(1)*f(1)=5 n=4：1 最后出栈的序列有 f(3)种，2 最后出栈的序列有 f(1)* f(2) 种，3 最后出栈的序列有 f(2)*f(1)种，4 最后出栈的序列有 f(3)种，所以 f(4)= 2*f(3)+ f(1)* f(2)+ f(2)* f(1)=14 可以看出 i(i=1,2,3,n)最后出栈的序列有 f(i-1)*f(n-i) 所以 f(n)=f(0)*f(n-1)+ f(1)*f(n-2)+f(2)*f(n-3)+f(3)*f(n-4)+ + f(n-1)*f(0)，用数学方法可得到 f(n)= ( ) ( )! n 2n ! n ! 2n 1 n 1 C 1 n 1 C 2nn n - + = + = 对有 n 个数据元素的序列，全部可能的排列个数为：Pn=n! 所以，不可能输出序列的个数为：Pn-Cn。 因此 4 个元素的出栈序列数为：14 ! 4 ! 4 8 1 4 1 C 4 = + = ！ 这 14 种出栈序列如下： 1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 ( ) ( ) 2 n n! ! 2n 1 n 1 C + = 2试说明下述运算的结果 (1) Pop_Stack(Push_Stack(S，A)； (2) Push_Stack(S，Pop_Stack(S)； (3) Push_Stack(S，Pop_Stack(Push_Stack(S，B) 分析与解答：该题目主要考查栈的操作。 (1) 首先要实现运算 Push_Stack(S，A)，其结果是将元素 A 压入栈 S 中。若栈 S 满，则出现上溢现象的处理；否则把元素 A 压入栈顶，且元素 个数加 1。然后作 Pop_Stack(S)运算， 将栈顶元素弹出，且元素个数减 1。 (2) 首先作 Pop_Stack(S)运算。若栈 A 为空，则作下溢处理；否则弹 出栈顶元素。然后再进行压入运算，将刚才弹出的元素压入栈 S 中。 (3) 这种复合运算复杂一些，在(1)、(2)的基础上可知，这种运算的 结果使栈 S 增加了一个栈顶元素 B。 3何谓队列的上溢现象，一般有几种解决方法，试简述之。 分析与解答：该题目主要考查队列的存储结构。 在队列的顺序存储结构中，设队列指针为 front，队尾指针为 rear， 队列的容量(即存储的空间大小)为 MAXSIZE。当有元素要加入队列(即入队) 时，若 rear=MAXSIZE-1，则队列已满，此时就不能将该元素加入队列。对 于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以 用循环队列解决。 一般地，要解决队列的上溢现象可有以下几种方法： (1) 可建立一个足够大的存储空间以避免溢出，但这样做往往会造 成空间使用率低，浪费存储空间，一般不采用这种方法。 (2) 采用移动元素的方法，每当有一个新元素入队，就将队列中已 有的元素向对头移动一个位置，假定空余空间足够。每当删去一个队头元 素，则可依次移动队列中的元素总是使 front 指针指向队列中的第一个位 置。 (3) 采用循环队列方式。将队头、队尾看作是一个首尾相接的循环 队列，利用一维数组顺序存储并用取模运算实现。 4设栈 S=1,2,3,4,5,6,7,其中 7 为栈顶元素。请写出调用 algo(&S)后 栈 S 的状态。 void algo(PseqStack S) int x; PseqQueue Q； PseqStack T； Q=Init_SeqQueue( )； T=Init_SeqStack( )； while(!Empty_SeqStack(S) Pop_ SeqStack(S,&x); if (x/2!=0) Push_SeqStack(T，x)； else En_SeqQueue(Q，x)； while(!Empty_SeqQueue(Q) Out_ SeqQueue(Q,&x); Push_SeqStack(S，x)； while(!Empty_SeqStack(T) Pop_ SeqStack(T,&x); Push_SeqStack(S，x)； 分析与解答：本函数的功能是将顺序栈 S 中递增有序的整数中的所有偶数 调整到所有奇数之前，并且要求偶数按递减序排列，奇数按递增序排列。 算法首先设置并初始化中间栈 T 和中间队列 Q， 然后将 S 栈中的整数出 栈，若整数为奇数，入栈 T,若为偶数，入队列 Q。这样 S=,T=7,5,3,1, 其中 1 为栈顶元素,Q=6,4,2,其中 6 为队头元素。然后，将 Q 中整数出队 列并入栈 S, 这样 S=6,4,2,其中 2 为栈顶元素,再将 T 中元素出栈，并入 栈 S, 这样 S=6,4,2,1,3,5,7,其中 7 为栈顶元素。 最后 S 栈的状态如图 3.4 所示。 1 2 3 4 5 6 7 8 9 10 6 4 2 1 3 5 7 图 3.4 调用 algo(&S)后栈 S 的状态 5假设两个队列共享一个循环向量空间(如图 3.5 所示)，其类型 Queue2 定义如下： front1 rear1 rear0 front0 toptypedef struct DateType dataMAXSIZE; int front2,rear2; Queue2; 图 3.5 双循环队列示意图 对于i=0或1， fronti和reari分别为第i个队列的头指针和尾指针。 请对以下算法填空，实现第 i 个队列的入队操作。 int EnQueue (Queue2 *Q, int i, DateType x) /*若第 i 个队列不满，则元素 x 入队列，并返回 1；否则返回 0*/ if(i1) return 0; if(Q-reari=Q-front (1) ) return 0; Q-data (2) =x; Q-reari=( (3) ); return 1; 分析与解答：入队操作需先判队满。队列是否满，要看一个队列的队尾元 素位置与另一个队列的队首元素位置之间是否还有空间。我们规定，队首 指针总是指向队首元素的实际位置，队尾指针总是指向队尾元素的后一个 位置。 因此，0 号队列队满的判断条件是 rear0=front1。同样，1 号队列 队满的判断条件是 rear1=front0。 这样一来，就要判断传递进来的 i 是 0 还是 1。但程序中没有提供判断 i 的语句 。因此可以将上述队满的判断条件统一成下列关系式： reari=front(i+1)%2。在上式中，当 i=0 时，(i+1)%2 为 1，当 i=1时，(i+1)%2 为 0。 上述程序，第 1 个空是判队列 i 是否满；第 2 个空是将 x 插入到队列 i 的当前队尾， 即在 reari的位置上插入； 第 3 个空是修改队列 i 的尾指针， 因为是循环队列，所以要对向量的容量 MAXSIZE 取模。 本题答案是：(1) (i+1)%2 (或 1-i) (2) Q-reari (3) (Q-reari+1)% MAXSIZE 五算法设计题 1已知 Q 是一个非空队列，S 是一个空栈。仅用队列和栈的基本操作和少 量工作变量，编写一个算法，将队列 Q 中的所有元素逆置。 分析：该题目主要考查队列和栈的应用。将队列逆置的步骤为： (1)顺序取出队列中的元素，将其入栈； (2)所有元素入栈后，再从栈中逐个取出，入队列。 算法描述如下： Reverse_queue(PseqQueue q) DataType x ; PSeqStack S ; S=Init_SeqStack( ); while(! Empty_SeqQueue(q) /*若队列非空，则将队列中的元素入 栈*/ Out_SeqQueue(q,&x); Push_SeqStack(S, x); while(!Empty_SeqStack(S) /*若栈非空，则将栈中元素入队*/ Pop_SeqStack(S,&x); In_SeqQueue(q，x); 2试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形 如“序列 1&序列 2”模式的字符序列。其中序列 1 和序列 2 中都不含字符 & ，且序列 2 是序列 1 的逆序列。例如， “a+b&b+a”是属该模式的字符 序列，而“1+3&3-1”则不是。 分析：本题主要利用栈的工作原理，对于给定的字符串在读到字符&前 入栈，在逐个读&之后的字符并和栈顶字符比较，若相等，则出栈，否 则序列 2 不是序列 1 的逆序列。 算法描述如下： int IsReverse( ) /*判断输入的字符串中&前和&后部分是否为逆串, 是则返回 1,否则返回 0*/ PSeqStack S; char e,ch; S=Init_SeqStack( ); while (e =getchar()!=&) /*将输入的字符串中&的前半部分 入栈*/ Push_SeqStack (S,e)；; while (e=getchar()!=) /*遇到字符循环结束，否则进行比 较*/ if (Empty_SeqStack(S) return 0; Pop_ SeqStack(S, &ch);if (e!=ch) return 0; if (!Empty_SeqStack(S) return 0; return 1; 3请利用两个栈 s1 和 s2 来模拟一个队列。用栈的运算来实现该队列的三 个运算：inqueue，插入一个元素入队列；outqueue，删除一个元素出队列； queue_empty，判断队列为空。 分析：由于队列是先进先出，而栈是后进先出；所以只有经过两栈，即在 第一个栈里先进后出，再经过第二个栈后进先出来实现队列的先进先出。 因此，用两个栈模拟一个队列运算就是用一个栈作为输入(输入栈)，而另 一个栈作为输出(输出栈)。当入队列时，总是将数据进入到输入栈中。在 输出时，如果输出栈已空，则将输入栈的所有数据压入输出栈中，然后由 输出栈输出数据；如果输出栈不空，就从输出栈输出数据。显然，只有在 输入、输出栈均空时队列才为空。 一个栈 s1 作为输入栈，用来插入数据，另一个栈 s2 作为输出栈，用来 删除数据，删除数据时应将前一栈 s1 中的 所有数据读出，然后进入到第 二个栈 s2 中。s1 和 s2 大小相同。 算法描述如下： void inqueue(SeqStack s1,int x) /*插入一个数据入队列*/ if(s1-top=n) /*输入栈 s1 已满*/ if(Empty_SeqStack(s2) /*若输出栈 s2 为空，则将 s1 中的所有 数据退栈后压入 s2*/ while(!Empty_SeqStack(s2) Pop_SeqStack(s1, &x) ; Push_SeqStack(s2, x); else /*若输出栈 s2 不为空，不能利用这里面的空间 存储数据，队列满*/ printf(“队列满”); else /*输入栈 s1 不满，直接入栈*/ Push_SeqStack(s1,x); void outqueue(SeqStack s1,SeqStack s2,int x) /*删除一个数据 出队列*/ if (Empty_SeqStack(s1) & Empty_SeqStack(s2) /*队列 空*/ printf(“队列空”); else if (Empty_SeqStack(s2) /*s2 空*/ while(!Empty_SeqStack(s1) /*将 s1 的所有元素退栈 后压入 s2*/ Pop_SeqStack(s1, &x) ; Push_SeqStack(s2,x); Pop_SeqStack(s2,&x); /*弹出栈 s2 的栈顶元素(队首元素)并赋给 x*/ int queue_empty(SeqStack s1, SeqStack s2) /*判断队列为空*/ if (Empty_SeqStack(s1) & Empty_SeqStack(s2) return 1; /*队列为空*/ else return 0; /*队列不为空*/ 4. 用递归方法编程求 n 个元素的集合的幂集。n 为整数，集合包含的元素 为不大于 n 的正整数。 分析：考查集合 Sx(x=0，n-1，n)，和其幂集 P(Sx)，可以分析出它们 之间的关系如下。 S0=，P(S0)=； S1=1，P(S1)=,1；