3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
若入、出栈次序为Push， Pop，Push，Push， Pop， Pop，Push， Pop，则出栈的数字序列为何表示i进栈，Pop表示出栈)?
能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。
请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。
答：
出栈序列为：1324
不能得到1423序列。因为要得到14的出栈序列，则应做Push，Pop，Push，Push ，Push，Pop。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push， Pop，Push，Push，Push，Pop，Pop，Pop。
在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是：
1234，1243，1324，1342，1432，2134，2143，2314，2341，2431，3214，3241，3421，4321
不能得到的序列是：
1423，2413，3124，3142，3412，4123，4132，4213，4231，43123.2 链栈中为何不设置头结点?
答：
链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3 循环队列的优点是什么? 如何判别它的空和满?
答：
循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。
3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?
答：
当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
3.5 指出下述程序段的功能是什么?
void Demo1 //Demo1
SeqStack S1， S2， tm
DataType x;
...//假设栈tmp和S2已做过初始化
while )
while )
void Demo2
}
void Demo3
while )
}// Demo3
CirQueue Q1， Q2; // 设DataType 为int 型
int x， i ， n= 0;
... // 设Q1已有内容， Q2已初始化过
while )
for
答：
程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。
程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。
程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。
程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。
这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。
3.6 回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。
解：
根据提示，算法可设计为：
//以下为顺序栈的存储结构定义
#define StackSize 100 //假定预分配的栈空间最多为100个元素
typedef char DataType;//假定栈元素的数据类型为字符
typedef structSeqStack;
int IsHuiwen
return 1 ; // 比较完毕均相等则返回 1
}
3.7 利用栈的基本操作，写一个将栈S中所有结点均删去的算法void ClearStack，并说明S为何要作为指针参数?
解：
算法如下
void ClearStack
因为要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。
3.8 利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize，并说明S为何不作为指针参数?
解：
算法如下：
int StackSize
return n;
}
上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。
3.9 设计算法判断一个算术表达式的圆括号是否正确配对。 ‘就退掉栈顶的‘
if EmptyStack return 1;// 匹配，返回1
else return 0;//不匹配，返回0
}
3.10 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack 、入栈Push 和出栈Pop等算法， 其中i为0 或1， 用以表示栈号。
解：
双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：
//双向栈的栈结构类型与以前定义略有不同
#define StackSize 100 // 假定分配了100个元素的向量空间
#define char DataType
typedef structDblStack
void InitStack
int EmptyStack
int FullStack
void Push
DataType Pop
3.11 Ackerman 函数定义如下：请写出递归算法。
┌ n+1 当m=0时
AKM = │ AKM 当m≠0 ，n=0时
└ AKM) 当m≠0， n ≠ 0时
解：
算法如下
int AKM
3.12 用第二种方法 ，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。
解：
算法设计如下:
//循环队列的定义
#define QueueSize 100
typedef char Datatype ; //设元素的类型为char型
typedef struct CirQueue;
置空队
void InitQueue
判队空
int EmptyQueue
判队满
int FullQueue
出队
DataType DeQueue
入队
void EnQueue
取队头元素
DataType FrontQueue
3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点 ，试编写相应的置空队、判队空 、入队和出队等算法。
解：
算法如下：
//先定义链队结构:
typedef struct queuenodeQueueNode; //以上是结点类型的定义
typedef structLinkQueue; //只设一个指向队尾元素的指针
置空队
void InitQueue
//回收结点空间
}
判队空
int EmptyQueue
入队
void EnQueue
出队
Datatype DeQueue
else
Q-rear-next-next=p-next;//摘下结点p
free;//释放被删结点
return x;
}
3.14 对于循环向量中的循环队列，写出求队列长度的公式。
解：
公式如下%QueueSize
3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。
解：
根据题意，可定义该循环队列的存储结构：
#define QueueSize 100
typedef char Datatype ; //设元素的类型为char型
typedef struct CirQueue;
CirQueue Q;
循环队列的队满条件是：Q-quelenQueueSize
知道了尾指针和元素个数，当然就能计算出队头元素的位置。算法如下：
判断队满
int FullQueue
入队
void EnQueue
出队
Datatype DeQueue
