[数据结构与算法]06栈[数据结构学习笔记]（注释比代码多)

栈

·相关概念

1. 定义：限定只能在表的一端进行插入和删除运算的线性表(比如手电筒存取电池的操作)

2. 逻辑结构：与线性表相同，仍为一对一关系。

3. 存储结构：顺序栈和链式栈都可，但顺序栈更常用

4. 运算规则：只能在栈顶运算，后进先出(LIFO)原则.与线性表不同(随机存取)。

·具体实现

顺序栈：

1. 顺序栈的表示

#define MAXSIZE 100
typedef struct {
    int *base;   // 栈底指针
    int *top;    // 栈顶指针
    int stacksize;  // 栈可用最大容量
}SqStack;

2. 顺序栈的初始化(即构造一个空栈)

Status InitStack(SqStack &S){
    S.base=(int*)malloc(MAXSIZE*sizeof(int));  // 为栈底指针开辟地址(malloc不再赘述)
    if(!S.base)exit(OVERFLOW);  // 如果base地址为0则表示没有分配成功
    S.top=S.base;   //栈顶指针等于栈底指针则为空栈
    S.stacksize=MAXSIZE; //栈的最大容量
    return OK;
}

3. 顺序栈的清空与销毁

// 清空顺序栈
Status ClearStack(SqStack &S){
    if(S.base)S.top=S.base; //如果栈底不为空就令栈顶指针=栈底指针则为空栈
    return OK;
}

// 销毁顺序栈(与清空相比，将地址释放)
Status DestroyStack(SqStack &S){
    if(S.base){ //若是空栈则销毁
        delete S.base;
        S.stacksize=0;
        S.base=S.top=NULL;
    }
    return OK;
}

4. 顺序栈的入栈

·算法思路：

1. 判读是否栈满，若满则报错(上溢)
2. 元素e压入栈顶指针
3. 指针++指向下一元素

//  顺序栈的入栈
Status Push(SqStack &S, int e){
    if(S.top-S.base==S.stacksize) return ERROR;   //判读栈满
    *S.top=e;   //将元素e填入栈此时的顶部
    S.top++;    //让指针加1表示指向下一空间
    return OK;
}

5. 顺序栈的出栈

·算法思路：

1. 判断是否栈空，若空则报错(下溢)
2. 获取栈顶元素,用e返回其指
3. 栈顶指针–指向下一元素

// 顺序栈的出栈
Status Pop(SqStack &S, int &e){
    if(S.top==S.base) return ERROR; //判断是否为空栈
    S.top--;    //令top指向栈顶元素
    e=*S.top;
    return OK;
}

链栈：

概念：链栈是元素受限的单链表，只能在链表头部进行操作

注意(一般情况下)：
· 链表的头指针就是栈顶，不需要头结点
· 基本不存在栈满的情况
· 空栈相当于头指针指向空

1. 链栈的结点定义：

// 链栈的结点
typedef struct StackNode{
    int data;
    struct StackNode *next; //嵌套定义
}StackNode,*LinkStack;

2. 链栈的初始化

// 链栈的初始化(构建空栈)
Status InitStack(LinkStack &S){
    S=NULL;
    return OK ;
}

3. 链栈的入栈

·算法思路：

1. 生成一个新结点p，并且p指针指向该结点
2. 为新结点赋值
3. 让S指向新的栈顶

// 链栈的入栈
Status Push(LinkStack &S, int e){
    StackNode *p;   //定义指向p结点的指针
    p = (LinkStack) malloc(sizeof(LinkStack));//开辟新结点
    p->data=e;  
    p->next=S;
    S=p;
    return OK;
}

4. 链栈的出栈

·算法思路：

1. 判断是否栈空，若空则报错(下溢)
2. 获取栈顶元素,用e返回其值
3. 栈顶指针–指向下一元素

// 链栈的出栈
Status Pop(LinkStack &S,int &e){
    if(S==NULL) return ERROR;   //  判断是否为空
    e = S->data;    // 获取栈顶元素的指，e返回其值
    StackNode *p;   //定义指向p结点的指针
    p = S;          //让结点指针p指向出栈的结点,以便删除
    S=S->next;      //栈顶指针指向下一个元素
    delete p;   //将空结点删除释放空间
    return OK;
}

5.取栈顶元素的值

int GetTop(LinkStack S){
    if(S!=NULL)
        return S->data;
}

栈与递归

递归的定义：

1. 对象递归: 若一个对象包含它自己，或用它自己给自己定义，则这个对象是递归的。
2. 过程递归: 若一个过程直接或间接的调用自己，则为过程递归

递归的用途：

1. 定义数学函数:阶乘等
2. 具有递归特性的数据结构:二叉树，广义表
3. 递归求解问题:迷宫问题，汉诺塔问题

递归问题----用分治法求解

一般形式如下：

void p(参数){
    if(递归结束条件) 可直接求解步骤;----基本项
    else p(较小参数);----归纳项
}

// 递归求阶乘
int DiGuDemo(int n){
    if(n==1) return 1;
    else n*=DiGuDemo(n-1);
}

递归的优缺点

优点：结构清晰，程序易读
缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息，时间开销大。