栈的实现及与递归关系

为啥数据结构的书籍，先要从数据结构概念讲起，再到物理结构，然后是线性表？因为在数据存储的时候，只有两种结构，任何时候都不会脱离这个范畴，即顺序存储和链式存储

Stack的概念及特性

1.栈是一种受限的线性表，只允许在一端进行删除和插入。
2.可以操作的这一端被称之为栈顶，相对的一端叫栈底。
3.插入元素被叫作入栈或压栈，删除元素叫作出栈或退栈。
4.在内存中，栈是从高地址向低地址生长
总结：
栈是线性结构，特点是先进后出

栈的顺序实现

顺序栈的结构

typedef struct{
    ElementType stack[MAXSIZE];
    int top;//用于指向栈顶，初始值为-1
} SqStack;

顺序栈的初始化

Status initStack(SqStack *stack){
    
    stack->top = -1;
    return OK;
}

顺序栈的是否为空

Status stackEmpty(SqStack st){
    
    if (st.top == -1) {
        return TRUE;
    }
    
    return FALSE;
}

获取栈顶元素

Status getTop(SqStack st, ElementType *e){
    if (st.top == -1)
        return ERROR;
    *e = st.stack[st.top];
    return OK;
}

顺序栈的插入

Status pushStack(SqStack *st, ElementType e){
    if (st->top == MAXSIZE - 1)
        return ERROR;
    st->stack[++st->top] = e;
    return OK;
}

顺序栈的删除

Status popStack(SqStack *st, ElementType *e){
    if (st->top == -1)
        return ERROR;
    *e = st->stack[st->top--];
    return OK;
}

顺序栈的长度

Status stackLength(SqStack st){
    
    return st.top+1;
}

顺序栈的清空

Status clearStack(SqStack *stack){
    
    stack->top = -1;
    return OK;
}

栈的链式实现

链式栈的结构

//栈节点，其实就是链表结构
typedef struct StackNode{
    ElementType data;
    struct StackNode *next;
    int top;
} StackNode,*LinkStackNode;

//栈
typedef struct {
    LinkStackNode top;//指向栈顶的指针
    int count;//记录个数
} LinkStack;

链式栈的初始化

Status initLinkStack(LinkStack *st){
   
    //初始化栈顶元素，指向NULL
//    st->top = (LinkStackNode)malloc(sizeof(StackNode));
//    if (st->top == NULL)
//        return ERROR;
    //以上是按照链表思路写的，可以不要，只保留st->top = NULL;
    st->top = NULL;
    st->count = 0;
    return OK;
}

链式栈的插入

栈的链式插入，你可以理解为没有头节点的元素进行头插

Status pushLinkStack(LinkStack *st,ElementType e){
    if (st == NULL)
        return ERROR;
    
    LinkStackNode p = malloc(sizeof(StackNode));
    if (!p)
        return ERROR;
    
    p->data = e;
    //插入的元素放的后继指向栈顶
    p->next = st->top;
    //更新栈顶指针，栈顶指针为新插入元素，
    st->top = p;
    st->count++;
    
    return OK;
}

链式栈的删除

Status popLinkStack(LinkStack *st,ElementType *e){
    //不存在栈或者栈是空，直接返回错误
    if (st == NULL || st->count == 0)
        return ERROR;
    
    LinkStackNode p = st->top;
    //删除栈顶元素
    free(p);
    //更新栈顶指针
    st->top = st->top->next;
    //元素个数减一
    st->count--;
    
    return OK;
}

获取链式栈的栈顶元素

Status getTopLinkStack(LinkStack st,ElementType *e){
    
    if (!st.top ||  st.count == 0) {
        return ERROR;
    }
    
    *e = st.top->data;
    
    return OK;
}

链式栈的清空

Status clearLinkStack(LinkStack *st){
    if (!st)
        return OK;
    //清空栈，要把栈中的元素删除
    LinkStackNode p,q;
    p = st->top;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    st->count = 0;
    return OK;
}

栈与递归

什么是递归呢？

递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上，递归，顾名思义，其包含了两个意思：递 和 归，这正是递归思想的精华所在。

什么情况下使用递归

1.定义是递归的
例如，求和、阶乘、斐波那契数列
2.数据结构是递归的
例如，链表
3.问题解法是递归的
汉诺塔、把皇宫问题、迷宫问题

递归的三要素

1.明确递归终止条件；
2.给出递归终止时的处理办法；
3.提取重复的逻辑，缩小问题规模

递归的优缺点

优点	缺点
实现简单	递归调用占用空间大，容易栈溢出
可读性好	可能存在重复计算

递归的优化方法

1.考虑是否重复计算
使用递归的时候，必要须要考虑有没有重复计算，如果重复计算了，一定要把计算过的状态保存起来
2.考虑尾递归
如果一个函数中所有递归形式的调用都出现在函数的末尾，就是尾递归
不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。而使用尾递归，只保留后一个函数堆栈即可

递归与循环

递归与循环相同特性是重复任务，不同的地方是：
1.递归是一个问题求解的过程
2.递归有函数调用的开销，而循环没有
递归修改成循环
1.自己建立“堆栈”来保存这些内容一边替代系统堆栈，例如树的非递归方式
2.把对递归的调用变为对循环处理

栈与递归的关系

在高级语言中，调用函数和被调用函数之间的连接及信息交换都是通过栈来进行的，具体过程如下：
在运行被调用函数之前：
1.将所有实参、返回地址等信息信息调用传递给被调用函数保存
2.为被调用函数的变量分配存储空间
3.将控制转移到被调用函数入口
被调用函数将要完成时：
1.保存被调用函数的返回结果
2.释放被调用函数的存储空间
3.按照它保存的返回地址将控制移动到调用函数

注意：多个函数嵌套，按照“先调用后返回”的原则，函数之间的信息传递和控制转移要通过栈来实现