5.2 链栈的表示和实现
链栈是运算受限的单链表，只能在链表头部进行操作。
class LinkStack { public: SElemType data; LinkStack *next; }
链表的头指针就是栈顶；不需要头结点；基本不存在栈满的情况；空栈相当于头指针指向空；插入和删除仅在栈顶处执行。
链栈的初始化：
void InitStack(LinkStack *S) { S = NULL; return true; }
判断链栈是否为空：
bool StackEmpty(LinkStack *S) { if(S==NULL) return true; else return false; }
链栈的入栈：
bool Push(LinkStack *S, SElemType &e) { LinkStack *p = new LinkStack; //生成新的节点p p->data = e; //将新节点数据域置为e p->next = S; //将新节点插入栈顶 S = p; //修改栈顶指针 return true; }
链栈的出栈：
bool Pop(LinkStack *S, SElemType &e) { if(S==NULL) return false; e = S->data; LinkStack *p = S; S = S->next; delete p; return true; }
取栈顶元素：
SElemType GetTop(LinkStack *S) { if(S != NULL) return S->data; }
6、栈和递归
6.1 递归的定义
若一个对象部分地包含它自己，或者用它自己给自己定义，则称这个对象是递归的，如单链表定义时的指针域；
若一个过程直接地或者间接地调用自己，则称这个过程是递归的过程，例如求n的阶乘。
//求n的阶乘 long Fact(long n) { if(n==0) return 1; else return n*Fact(--n); }
常常用到递归的情况：
1、递归定义的数学函数
如阶乘函数：
如Fibonaci数列：
2、具有递归特性的数据结构：
如二叉树，广义表等。
3、可以使用递归求解的问题：
如迷宫问题，汉诺塔问题。
递归问题是使用分治法来解决问题的一种思路。分治法是指：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或者类似的子问题来求解。使用分治法必备的三个条件：
1) 能将一个问题转变成一个新问题，而新问题与原问题的解法相同或者类同，不同的仅仅是处理的对象不同，且这些处理对象是有规律变化的；
2) 可以通过上述转化使得问题得以简化；
3) 必须有一个明确的递归出口，或者称为递归边界。
分治法求解递归问题的一般形式：
void p(参数表) { if(递归结束条件) 可以直接求解步骤; //基本项 else p(较小的参数); //归纳项 }
6.2 递归的优缺点
优点：结构清晰，程序易读；
缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。
将递归程序转化为非递归程序的两种方法：
方法一：尾递归，单向递归可以使用循环结构来进行转化；
方法二：可以自己设计栈模拟系统运行时的栈；
7、队列的表示和操作的实现
7.1 相关术语
队列是仅在表尾进行插入操作，在表头进行删除操作的线性表；
表尾称为队尾，表头称为队头；
队列是一种先进先出(FIFO)的线性表；
插入元素称为入队，删除元素称为出队；
队列的存储结构为链队或者顺序队，常使用循环顺序队
7.2 队列的抽象数据类型定义
7.3 队列的顺序表示
#define MAXQSIZE 100 //最大的队列长度 class SqQueue { QElem *base; //队列的头指针，初始化时分配存储空间 int front; //头指针 int rear; //尾指针 };
循环队列：将base[0]接在base[MaxQSIZE-1]之后，若rear+1==M，则令rear=0。
实现方法是：利用求模(mod %)运算，插入元素操作包括两步代码：
Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXQSIZE;
删除元素操作包括两步代码：
x=Q.base[s.front]; Q.front=(Q.front+1)%MAXQSIZE;
循环队列可以循环使用为队列分配的存储空间。
使用循环队列时，若不做其他处理，队空和队满的判断条件都是“头指针==尾指针”。为了区别队空和队满，可以有以下处理方式：
另外设置一个变量，记录元素的个数，通过变量个数和头尾指针是否相等两个条件判断队空和队满
可以少用一个元素空间，当(rear+1)%MAXQSIZE== front时，表示队满；当rear== front时表示队空。
队列的初始化
void InitBase(SqQueue &Q) { Q.base = new QElemType[MAXQSIZE]; //分配数组空间 if(!Q.base) return -1;//分配空间失败 Q.front = Q.rear = 0; //将头尾指针置为0 }
求队列的长度
int QueueLength(SqQueue &Q) { return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }
循环队列的元素入队
void EnQueue(SqQueue &Q, QElemType &e) { if((rear+1)%MAXQSIZE==front) { cout << "队列满了，不能插入元素了"<<endl; return; } Q.base[Q.rear]=e; Q.rear = (Q.rear+1)%MAXQSIZE;//尾指针后移 }
循环队列的元素出队
void DeQueue(SqQueue &Q, QElemType &e) { if(rear==front) { cout << "队列为空，不能出队"<<endl; return; } e=Q.base[Q.front]; Q.front = (Q.front+1)%MAXQSIZE;//头指针后移 }
取队头元素
QElemType DeQueue(SqQueue &Q) { if(rear!=front) return Q.base[Q.front]; }
7.4 队列的链式表示
若用户无法估计所用队列的长度，则应该采用链式队列，链式队列的节点类型定义如下所示：
#define MAXQSIZE 100 //最大队列长度 class QNode { QElemType data; QNode *next; };
链式队列的定义如下所示：
class LinkQueue { QNode *front; //队头指针 QNode *rear; //队尾指针 }
链式队列的初始化
void InitQueue(LinkQueue &Q) { Q.front = Q.rear = new QNode; Q.front->next = nullptr; Q.rear->next = nullptr; }
链式队列的销毁，从队头节点开始，依次释放所有的节点
void DestroyQueue(LintQueue &Q) { while(Q.front) { QNode *p = Q.front->next; delete Q.front; Q.front = p; } }
链式队列的元素入队
void EnQueue(LinkQueue &Q, QElemType e) { QNode *p = new QNode; p->data = e; p->next = nullptr; Q.rear->next = p; Q.rear = p; }
链式队列的元素出队
void DeQueue(LinkQueue &Q) { if(Q.front == Q.rear) return; //空队列无须出队 QNode *p = Q.front->next; Q.front->next = p->next; if(Q.rear == p) Q.rear = Q.front; delete p; }
链式队列取队头元素
void GetHead(LinkQueue &Q, QElemType &e) { if(Q.front == Q.rear) return; e = Q.front->next->data; }
