3.1栈的结构定义
typedef struct SqStack{
ElemType *V; //定义数组元素首地址
int top; //定义栈顶标记
}SqStack;
初始化：
#define MAXSIZE 100
int Initial_SqStack(SqStack &S){
S.V=new ElemType[MAXSIZE];
//申请存储空间
if(!(S.V)){return -1;}
S.top=0;
//堆栈置空
return 0;
说明：顺序存储增加结点要判断是否已满，删除结点要判断删除位是否合法，如栈用顺序存储，删除结点时要判断栈是否已为空。
3.2双栈（共享栈）
将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端，0号栈的栈顶指针top[0]等于-1时该栈为空，1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长，一个top[0]++，一个top[1]--。下面是双栈结构定义，初始化，栈空、栈满判断：
//定义双栈数据结构
typedef struct DblStack{
int top[2],base[2];
Elemtype *V;
int m;
}DblStack;
int InitialStack(DblStack &S,int m){
//申请空间并判断是否成功
S.V=new Elemtype[m];
if(!(S.V)){return 0;}
//初始化
S.top[0]=S.base[0]=-1;
S.top[1]=S.base[1]=m;
S.m=m;
return 1;
}
int IsEmpty(DblStack S){
if((S.top[0]==S.base[0])&&(S.top[1]==S.base[1])){return 1;}
else{return 0;}
}
int IsFull(DblStack S){
if(S.top[0]+1==S.top[1]){return 1;}
else{return 0;}
}
3.3链栈
链栈的结点结构与单链表相同，链栈是操作受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针（前插法）。
3.4链栈的初始化
链栈的初始化与链表类似，不同的是链栈不需要定义头结点。
void InitStack(LinkStack &S )
{
S=NULL;
}
3.5栈的应用——递归
例题1：计算下面递归算法的时间复杂度。
说明：上面是等比数列求和。
Hanoi塔时间复杂度2n。
3.6栈的应用——表达式求值
表达式：A+B(C-D)-E/F
其实上式本身是中缀表达式的写法，对应的是树的先序遍历。另外有一种后缀表达式，对应树的后序遍历，如上式的后缀表达式为：
ABCD-+EF/-。
例题2：
设有一个递归算法如下:
int X(int n)
{ if(n<=3) return 1;
else return X(n-2)+X(n-4)+1
}
则计算X(X(8))时需要计算X函数 D 次.
A. 8 B.9 C.16 D.18
3.6作业
作业一：编写十进制转八进制的程序。
思路：不断对8取余，将余数压入栈内，直到商为0，再从栈中输出各个元素。
作业二：回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。
思路：将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较，若相等，则再出栈一个元素与后一个字符比较，……，直至栈空，结论为字符序列是回文。在出栈元素与串中字符比较不等时，结论字符序列不是回文。
易错点：输入输出字符串多种方式。
1 、C语言的scanf/printf本身不支持字符串输入输出，要通过字符数组实现。
char str[100];
scanf("%s",str);
printf("%s",str);
2、C语言还支持专门的字符串输入输出函数：gets/puts。
（需要<string.h>头文件）
gets的作用为读入一行输入，并将读到的换行符替换为字符串结束符，并自动加’\0'。puts的作用为将字符串单行输出，会自动在结尾增加换行，字符数组必须以'\0'结束。
char str[100];
gets(str);
puts(str);
*以上两种方式，字符串载体都是字符数组，输入串长度应小于字符数组维数。scanf输入遇到空格或回车停止，gets输入包含空格遇到回车停止。
3、C++的cin/cout可以直接对string类型操作，如：
#include <string.h>
string a;
cin >> a;
cin同样遇到空格或回车停止，并自动在末尾加'/0'。
