数据结构之栈的实现

栈的定义：

栈又名堆栈，是一种受限制的线性表，只在表尾进行插入和删除操作的线性表。这一端被称为栈顶，另一端称为栈底。向一个栈插入新元素称为进栈、入栈或压栈，将新元素放到栈顶，从栈顶删除一个元素，称为出栈或者退栈，相邻的元素作为新的栈顶。

栈是一种数据结构，只能从栈顶进行插入和删除的。在我们常见的开发当中，栈的使用很多。例如手机页面push的跳转，只能从最前面显示的界面一个一个退出。

栈的示意图

截屏2020-04-12上午10.30.19.png

链式栈结构

截屏2020-04-12上午10.30.41.png

进栈操作

截屏2020-04-12上午10.30.49.png

出栈操作

截屏2020-04-12上午10.31.09.png

接下来，我们用数组和链表的方式，来演示一下对栈的一些操作。

一、数组实现

先创建一个栈的结构体

typedef int Status;
typedef int Elemtype;

typedef struct {
    Elemtype data[MAXSIZE];
    int top;
}Stack;

首先先建立一个空栈，判断一个栈是否为空或者将栈置空，只需要判断top为-1来表示，
获取栈的长度，判断top的值就可以知道栈的长度。

//1.1构建一个空栈
Status InitStack(Stack *S){
    S->top = -1;
    return OK;
}
//1.2将栈置空
Status  ClearStack(Stack *S){
    S->top = -1;
    return OK;
}
//1.3判断顺序栈是否为空
Status StackEmpty(Stack S){
    if(S.top == -1) return TRUE;
    else    return FALSE;
}
//1.4返回栈的长度
Status StackLength(Stack S){
    return S.top+1;
}

获取栈顶:在获取栈顶时，需要先判断栈是否为空，不为空则将数组中的第top个元素赋值即可

//1.5获取栈顶
Status GetTopStack(Stack S,Elemtype *e){
    if(S.top == -1)
        return ERROR;
    else
        *e = S.data[S.top];
    
    return OK;
}

push操作：先对栈进行判断，判断栈是否已满，没有满则在数组第top个元素插入，top++
pop操作：先对栈进行判空，不为空则将数组中第top个元素删除，top--
遍历操作，利用循环，将数组中的每一个值打印输出

//1.6插入元素e为新栈顶元素
Status PushDataInStack(Stack *S,Elemtype e){
    if(S->top == MAXSIZE-1) return ERROR;
    S->top++;
    S->data[S->top] = e;
    return OK;
}
//1.7删除s栈顶元素，并且用e带回
Status PopDataInStack(Stack *S,Elemtype *e){
    if(S->top == -1)    return ERROR;
    *e = S->data[S->top];
    S->top--;
    return OK;
}
//1.8从栈底到栈顶一次对栈中的每个元素打印
Status StackDisPlay(Stack S){
    int i = 0;
    while (i<=S.top) {
        printf("%d   ",S.data[i++]);
    }
    printf("\n");
    return OK;
}

main函数

   Stack S;
    int e = 0;
    if(InitStack(&S) == OK){
        for (int i = 1; i<10; i++) {
            PushDataInStack(&S, i);
        }
    }
    printf("顺序栈元素为:\n");
    StackDisPlay(S);
    
    PopDataInStack(&S, &e);
    printf("弹出的是:%d \n",e);
    
    StackDisPlay(S);
    printf("是否为空栈:%d(0为假,1为真)\n",StackEmpty(S));
    
    GetTopStack(S, &e);
    
    printf("栈顶元素为:%d \n",e);
    
    ClearStack(&S);
    printf("清空是否已经清空,%d(0为假,1为真),栈的长度为:%d\n",ClearStack(&S),StackLength(S));
    
    

打印结果

15865728980098.png

链表实现栈的操作

链表实现栈的操作比数组实现更复杂一点

先对节点和栈进行定义

//定义节点结构体
typedef struct StackNode{
    Elemtype data;
    struct StackNode *next;
}StackNode;

typedef struct StackNode *LinkStackPtr;

//定义栈
typedef struct {
    LinkStackPtr top;
    int count;
}LinkStack;

创建空栈，只需要判断栈的top为空，count 为0
而将栈置空，则需要对链表的每一个节点一一释放
判断空栈和判断栈中的个数，都只需要判断conut的数量，为0则栈为空，不为0，则栈中有元素。

//1.1构建一个空栈
Status InitStack(LinkStack *s){
    s->top = NULL;
    s->count = 0;
    return OK;
}
//1.2把链表s置为空栈
Status ClearStack(LinkStack *s){
    LinkStackPtr p,q;
    p = s->top;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    s->count = 0;
    return OK;
}
//1.3判断栈是否为空,若栈s为空，返回true，否则返回false
Status StackEmpty(LinkStack s){
    if(s.count == 0)
        return TRUE;
    else
        return FALSE;
}
//1.4返回s的元素个数
Status StackCount(LinkStack s){
    return s.count;
}

用链表实现栈的操作，有点像前插法一样，将最后插入的元素放在指针top的前面，将新创建的节点的next指向top，再将指针top前移，count++；删除时，则将最前面的指针指向下一个元素，将第一个节点释放，最后将count--，遍历栈时，用新创建的节点指向top，用循环对栈中的每一个元素进行打印输出。

//1.5取栈顶
Status GetStackTop(LinkStack s,Elemtype *e){
    if(s.count == 0)
        return ERROR;
    else
        *e = s.top->data;
    return OK;
}
//1.6插入元素到栈顶
Status pushData(LinkStack *s,Elemtype e){
    LinkStackPtr temp;
    temp = (LinkStackPtr)malloc(sizeof(LinkStackPtr));
    temp->data = e;
    temp->next = s->top;
    s->top = temp;
    s->count++;
    return OK;
}
//1.7删除栈顶
Status pop(LinkStack *s,Elemtype *e){
    LinkStackPtr p;
    if(StackEmpty(*s)){
        return ERROR;
    }
    *e = s->top->data;
    p = s->top;
    s->top = s->top->next;
    free(p);
    s->count--;
    return OK;
    
}

main 函数

  LinkStack s;
    int e=0,i=0;
    if(InitStack(&s) == OK)
        for (i = 1; i<10; i++) {
            pushData(&s, i);
        }
    printf("栈中的元素:");
    StackDisplay(s);
    pop(&s, &e);
    printf("弹出栈顶元素为:%d\n",e);
    StackDisplay(s);
    printf("栈是否为空:%d(1:空，0:不空)\n",StackEmpty(s));
    GetStackTop(s, &e);
    printf("栈顶元素为:%d,栈的长度为:%d\n",e,StackCount(s));
    ClearStack(&s);
    printf("清空栈后，栈是否为空：%d(1:空，0:不空)\n",StackEmpty(s));
    return 0;

打印结果

15865735382258.png

栈与递归

递归的定义：编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。

在高级语言程序中，调用函数和被调用函数之间的链接与信息交换都是通过栈来进行的，通常，当一个函数的运行期间调用另一个函数时，在运行被调用函数之前，需要完成3件事情：
1、将所有的实参，返回地址等信息调用传递被调用函数保存；
2、为被调用函数的局部变量分配存储空间；
3、将控制转移到被调用函数入口；

而从被调用函数返回调用函数之前，系统同样需要完成3件事情：
1、保存被调用函数的计算结果；
2、释放被调用函数的数据区；
3、依照被调用函数保存的返回地址将控制移动到调用函数；

当多个函数构成嵌套调用时，按照“先调用后返回”的原则，上述函数之间的信息传递和控制转移必须通过栈来实现，即系统将整个程序运行时所需要的数据空间都安排在一个栈中，每当调用一个函数时，就在它的栈顶分配一个存储区，每当这个函数退出时，就释放它的存储区，则当前运行时的函数的数据区必在栈顶。

下面通过一个题目来理解递归与栈的关系
爬楼梯问题：假设你正在爬楼梯，需要n阶你才能到达楼顶，每次可以爬1或2个台阶，问有多少种不同的方法可以爬上楼顶（给定n为正整数）。

首先来分析一下这个题目：
当只有一阶或者2阶时，我们只有1种和2种方法可以爬上楼顶

当有3层或者3层时，你会发现分别有3种和5种方法可以爬到楼顶，你是不是已经发现了什么？

我们可以用递归来解决这个问题

int ClimbStairs(int n){    
    if(n == 0||n == 1||n ==2)
        return n;
    else
        return ClimbStairs(n-1)+ClimbStairs(n-2);
}

当然如果楼梯的阶层很大，那么达到楼顶的方法也就有很多，那就要考虑性能和精度的问题，在这里，我们对程序进行一些优化。可以节省因递归次数过多，而导致的性能问题的影响。

int ClimbStairs(int n){
    double Stairs[1000];
    Stairs[0]=0;
    Stairs[1]=1;
    Stairs[2]=2;
    for (int i = 3; i<=n; i++) {
        Stairs[i] = Stairs[i-1]+Stairs[i-2];
    }
    return dp[n];
}