4-1 在下题中，s是栈的名字，a、b是栈中的元素，操作PUSH返回栈s的栈顶元素地址，POP返回从栈中退出的元素。试说明下列运算的结果：
(1)POP(PUSH(s,a));
(2)PUSH(s,POP(s));
(3)PUSH(s,POP(PUSH(s,b)));

1）返回a；
2）s栈先退出元素，后又将退出的元素压回栈中，返回栈顶元素，栈顶元素无变化；
3）b压入了栈中，并返回栈顶元素地址。

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

思路：将p105页的Push()函数改成if结构的；调用stackFull函数。创建stackFull函数。

template < class Type >void Stack< Type >::Push(const Type& item){
//若栈满执行stackFull。再执行压栈操作.
   if(IsFull())
     stackFull();
   elements[++top]=item;
}

template < class Type >void Stack< Type >::stackFull(){
   maxSize*=3;                   //最大元素扩大2倍
   Type *temp=new Type[maxSize];
   for(int i=0;i <= top;i++)     //复制数据
      temp[i]=elements[i];
   delete[]elements;
   elements=temp;
}

4-3 铁路进行列车调度时，常把站台设计成栈式结构的站台，如右图所示。试问：
(1)设有编号1，2，3，4，5，6的六辆车，顺序开入栈式结构的站台，则可能的出栈顺序有多少种？
(2)若进站的六辆列车顺序如上述，那么是否能够得到435612，325641，154623，135426的出战顺序，如果不能，请说明为什么不能；如果能，说明如何得到。

1)第一题不会做 答案也看不懂
然后上水木请教了，不过一般大侠都很忙，给了三字锦囊 catalan google之
然后google到了一些东西,h(n)=c(2n-2,n-1)/n
一个c++学习者对于atalan的总结
这个网站上，其他一些学习编程的心得也不错
组合数学中的catalan数
我的理解：
可以对这6辆车的出栈次序计数作如下分析
我们把这6辆车分为如下5种分组:
前1辆车后5辆车，前2后4，前3后3(123 456)，前4后2，前5后1(12345 6)
我们总是让前组的车完成出栈后 再让后组车进栈，并且我们人为的规定后组车的第一辆车进栈后不会立刻弹出，要不然会和后一种情形重复，得少算一种情况。最后654321这样的出栈顺序并未包含在上述分组中。
至此，我们将6辆车的出栈次序全部列出，并令其为函数f(k),k=1,2...6
那么f(6)=f(1)*(f(5)-1)+f(2)*(f(4)-1)+f(3)*(f(3)-1)+f(4)*(f(2)-1)+f(5)*f(1)
好像不对
还是很晕，得回去查一下组合数学的书，恩，得好好看。
答案应该是h(n+1)=c(2n,n)/(n+1)
后注:在二叉树计数一章有详细的讲解

2)不可能得到435612和154623这两种出栈序列，问题出在最后的12和23不可能实现。
325641：1进-2进-3进-3出-2出-4进-5进-5出-6进-6出-4出-1出
135426：1进-1出-2进-3进-3出-4进-5进-5出-4出-2出-6进-6出

4-4试证明：若借助栈可由输入序列1，2，3，...，n得到一个输出序列p1,p2,p3...pn(它是输入序列的某种排列)，则在输出序列中不可能出现以下情况，即存在i< j< k,使得pj< pk< pi。

假设，存在这样的pj< pk< pi
首先i< j,即pi先于pj出栈，而我们根据题意知道输入序列从小到大进栈，pj< pi，那么pj先于pi是先进栈的。所以pi和pj之间的进出栈关系是pj进栈，pi进栈，pi出栈，pj出栈。---1
然后我们看j< k,同样pj先于pk出栈，而pj< pk，那么pj先于pk入栈，那么pj和pk之间的关系是：pj进栈，pj出栈，pk进栈，pk出栈。---2
再考察i< k,pi先于pk出栈，pk< pi，pk先于pi入栈，那么：pk入栈，pi入栈，pi出栈，pk出栈.--3
把序列3代入2，得到 pj进，pj出，pk进，pi进，pi出，pk出。其结果和序列1矛盾.
故不存在这样的出栈序列

4-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)
(6)!(A&&!((B< C)||(C >D)))||(C< E)