3 - 1 改写顺序栈的进栈成员函数 Push (x ) ，要求当栈满时执行一个 stackFull ( ) 操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前 MaxSize 位置。

3 - 2 铁路进行列车调度时 , 常把站台设计成栈式结构的站台，如右图所示。试问：

(1) 设有编号为 1,2,3,4,5,6 的六辆列车 , 顺序开入栈式结构的站台 , 则可能的出栈序列有多少种 ?

(2) 若进站的六辆列车顺序如上所述 , 那么是否能够得到 435612, 325641, 154623 和 135426 的出站序列 , 如果不能 , 说明为什么不能 ; 如果能 , 说明如何得到 ( 即写出 " 进栈 " 或 " 出栈 " 的序列 ) 。

3 - 3 试证明：若借助栈可由输入序列 1, 2, 3, … , n 得到一个输出序列 p 1 , p 2 , p 3 , … , p n ( 它是输入序列的某一种排列 ) ，则在输出序列中不可能出现以下情况，即存在 i < j < k ，使得 p j < p k < p i 。 ( 提示：用反证法 )

3 - 4 将编号为 0 和 1 的两个栈存放于一个数组空间 V[m] 中，栈底分别处于数组的两端。当第 0 号栈的栈顶指针 top[0] 等于 - 1 时该栈为空，当第 1 号栈的栈顶指针 top[1] 等于 m 时该栈为空。两个栈均从两端向中间增长。当向第 0 号栈插入一个新元素时，使 top[0] 增 1 得到新的栈顶位置，当向第 1 号栈插入一个新元素时，使 top[1] 减 1 得到新的栈顶位置。当 top[0]+1 == top[1] 时或 top[0] == top[1] - 1 时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈 (Double Stack) 结构的类定义，并实现判栈空、判栈满、插入、删除算法。

3 - 5 写出下列中缀表达式的后缀形式：

(1) A * B * C

(2) - A + B - C + D

(3) A* - B + C

(4) (A + B) * D + E / (F + A * D) + C

(5) A && B || ! (E > F) /* 注：按 C++ 的优先级 */

(6) !(A && ! ( (B < C) || (C > D) ) ) || (C < E)

【解答】

3 -6 假设以数组 Q[m] 存放循环队列中的元素 , 同时设置一个标志 tag ，以 tag == 0 和 tag == 1 来区别在队头指针 (front) 和队尾指针 (rear) 相等时，队列状态为 “ 空 ” 还是 “ 满 ” 。试编写与此结构相应的插入 (enqueue) 和删除 (dlqueue) 算法。

【解答】

3 -7 若使用循环链表来表示队列， p 是链表中的一个指针。试基于此结构给出队列的插入 (enqueue) 和删除 (dequeue) 算法，并给出 p 为何值时队列空。

【解答】

答案

>>返回