栈是一种限定性线性表，限定：插入和删除操作限制在栈顶进行，栈底固定。
特性：后进先出
栈：即LIFO表
ADT Stack {
数据对象：元素类型任意且相同。
结构关系：线性关系。
基本操作：
① InitStack(S) //初始化
操作前提：S为未初始化的栈。
操作结果：将S初始化为空栈。
② ClearStack(S) //置空
操作前提：栈S已存在。
操作结果：将S置成空栈。
③ IsEmpty(S) //判空
操作前提：栈S已存在。
操作结果：空栈返回真，否则返回假。
④ IsFull(S) //判满
操作前提：栈S已存在。
操作结果：栈满返回真，否则返回假。
⑤ Push(S,x) //进栈
操作前提：栈S已存在。
操作结果：成功返回真，否则返回假。
⑥ Pop(S,x) //出栈
操作前提：栈S已存在。
操作结果：成功返回真，否则返回假。
⑦ GetTop(S,x) //读栈顶元素
操作前提：栈S已存在。
操作结果：成功返回真，否则返回假。
}ADT Stack ;
栈的表示和实现
两种基本存储结构：顺序栈、链栈
顺序栈：顺序存储的栈。
链栈： 链式存储的栈。
#define Stack_Size 50
typedef char StackElemType;
typedef struct {
StackElemType elem[Stack_Size];
int top; //位置指针，栈顶下标
} SeqStack;
(1) 初始化
void InitStack(SeqStack *S)
{
S->top=-1;
}
(2) 进栈
int Push(SeqStack *S,StackElemType x) {
if(S->top==Stack_Size-1)
return FALSE;
S->top++;
S->elem[S->top]=x;
return TRUE;
}
(3) 出栈
int Pop(SeqStack *S,StackElemType *x) {
if(S->top==-1)
return FALSE;
*x=S->elem[S->top];
S->top--;
return TRUE;
}
(4) 读栈顶元素
int GetTop(SeqStack *S,StackElemType *x) {
if(S->top==-1)
return FALSE;
*x=S->elem[S->top];
return TRUE;
}
(5) 双端栈：两个栈的共享技术
#define M 100
typedef struct {
StackElemType Stack[M];
int top[2]; //栈顶指示器：top[0]、top[1]
} DqStack;
双栈进栈出栈过程示意
//双端栈初始化
void InitStack(DqStack *S)
{
S->top[0]=-1;
S->top[1]=M;
}
//双端栈进栈
int Push(DqStack *S,StackElemType x,int i)
{
if(S->top[0]+1==S->top[1])
return FALSE;
switch(i) {
case 0:
S->top[0]++;
S->Stack[S->top[0]]=x;
break;
case 1:
S->top[1]--;
S->Stack[S->top[1]]=x;
break;
default:
return FALSE;
}
return TRUE;
}
//双端栈出栈
int Pop(DqStack *S,StackElemType *x,int i)
{
switch(i) {
case 0:
if(S->top[0]==-1)
return FALSE;
*x=S->Stack[S->top[0]];
S->top[0]--;
break;
case 1:
if(S->top[1]==M)
return FALSE;
*x=S->Stack[S->top[1]];
S->top[1]++;
break;
default:
return FALSE;
}
return TRUE;
}
链栈
链栈栈顶指针：链表的表头指针
入栈、出栈操作：表头操作即可
链栈结点类型、链栈类型的定义
typedef struct node{
StackElemType data;
struct node *next;
} LinkStackNode,*LinkStack;
链栈结点类型： LinkStackNode
链栈类型： LinkStack
//链栈初始化
void InitStack(LinkStack *top) {
*top=(LinkStack)malloc(sizeof(LinkStackNode));
(*top)->next=NULL;
}
//链栈进栈
int Push(LinkStack top,StackElemType x) {
LinkStackNode *temp;
temp=(LinkStackNode *)malloc(sizeof(LinkStackNode));
if(temp==NULL) return FALSE;
temp->data=x;
temp->next=top->next;
top->next=temp;
return TRUE;
}
//链栈出栈
int Pop(LinkStack top,StackElemType *x)
{
LinkStackNode *temp;
temp=top->next;
if(temp==NULL) return FALSE;
top->next=temp->next;
*x=temp->data;
free(temp);
return TRUE;
}
栈的应用举例
括号匹配问题 ( { ( [ ] [ ( ) ] ) } )
算法要点：
左括号入栈
匹配右括号出栈
算法要点：
当前运算符优先级低于栈顶运算符时，两栈出栈运算，值再入栈。
递归：在定义函数自身的同时又出现对自身的引用。
直接递归：定义体内直接调用自己。
间接递归：通过其他函数调用自己。
斐波那契数列
int fib(int n) {
if(n==0||n==1) return n;
else return fib(n-1)+fib(n-2);
}
阿克曼函数
int ack(int m, int n) {
if(m==0) return n+1;
else if(n==0) return ack(m-1,1);
else return ack(m-1,ack(m,n-1));
}
计算n!
递归算法：就是在算法中直接或间接调用算法本身的算法。
long f(int n)
{
if(n==0) return 1;
return n*f(n-1);
}
使用递归算法的前提：
①原问题可以层层分解为类似的子问题，且子问题比原问题的规模更小。
②规模最小的子问题具有直接解。
设计递归算法的方法：
①寻找分解方法：将原问题转化为子问题求解。
②设计递归出口：根据规模最小的子问题确定递归终止条件。
汉诺塔递归算法
void hanoi(int n,char x,char y,char z) {
if(n==1) move(x,1,z); //最小子问题
else {
hanoi(n-1,x,z,y); //子问题：n-1个盘从x到y
move(x,n,z); //子问题：n盘从x到z
hanoi(n-1,y,x,z); //子问题：n-1个盘从y到z
}
}
理解递归过程
long f(int n) {
if(n==0) return 1;
return n*f(n-1); }
递归过程：递归进层、递归退层
递归进层：上层→下层（i→i+1层）
①栈中保留本层参数和返回地址
②为下层函数分配局部变量并为参数赋值
③将程序转移到被调用函数入口
递归退层：下层→上层（i+1→i层）
①保存被调函数的计算结果
②释放被调函数的数据区，恢复上层参数
③将程序转移到被调用函数入口
(1) 单向递归：递归函数中有一处以上的递归调用语句，但各递归调用语句的参数只和主调函数有关，相互之间参数无关，并且这些递归调用语句处于算法的最后。
int fib(int n) {
if(n==0||n==1) return n;
else return fib(n-1)+fib(n-2);
} // T(n) = O(2n)
int fib(int n) {
int x,y,z,i;
if(n==0||n==1) return n;
else {
x=0,y=1;
for(i=2;i<=n;i++) { z=y; y=x+y; x=z; }
return y;
}
} // T(n) = O(n)
(2)尾递归：递归调用语句只有一句的单向递归。尾递归是单项递归的特例。
long f(int n) {
if(n==0) return 1;
return n*f(n-1);
} // T(n) = O(n)
long f(int n) {
int s=1,i;
for(i=1;i<=n;i++) s*=i;
return s;
} // T(n) = O(n)
思考：用递归算法实现单链表的输出
void PrintLinkList ( LinkList L ) {
if ( L->next != NULL ) {
print (L->next->data);
PrintLinkList (L->next);
}
}
欢迎大家加我微信交流讨论（请备注csdn上添加）
