【数据结构】栈的深度学习

数据结构再度学习（详细注释版）：栈<顺序栈，链栈，共享空间栈>

顺序栈

//
//  main.c
//  SequenceStack
//
//  Created by Eason on 2020/8/1.
//  Copyright © 2020 Eason. All rights reserved.
//

#include <stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
typedef int ElemType;
typedef int State;
typedef struct{   //顺序栈的存储结构
    ElemType data[MAXSIZE];   //用数组存放数据，最大为MAXSIZE，作为栈满条件
    int top;   //用作栈顶指针
}SqStack;

//初始化顺序栈
State initStack(SqStack *S){
    S->top = -1;   //将栈顶指针置为-1，即将栈作为还是空的时候
    return OK;
}

//获得顺序栈的长度
int getLength(SqStack S){
    return (S.top)+1;   //根据数组下标的规则，数组中的长度为指针+1个元素
}

//清空顺序栈
State clearStack(SqStack *S){
    S->top = -1;   //将栈顶指针重新设置为-1，即此时表示栈空
    return OK;
}

//判断顺序栈是否为空
State isEmpty(SqStack S){
    if(S.top==-1){   //如果此时栈顶指针为-1表示栈此时为空，非-1则表示非空
        return TRUE;
    }else{
        return FALSE;
    }
}

//入栈
State push(SqStack *S, ElemType *e){
    if(S->top==MAXSIZE-1){   //根据数组下标的特点，当指针指向最后一个元素时为MAXSIZE-1，此时栈满
        printf("栈满，无法入栈\n");
        return ERROR;   //栈满说明空间已满已经不可以再入栈
    }else{    //如果栈非满则执行添加过程
        S->top++;   //栈顶指针+1指向一个新的顶部空间
        S->data[S->top]=e;   //将现在指向的这个新的空的栈顶空间元素置为指定元素（后进先出）
        return OK;
    }
}

//出栈
State pop(SqStack *S, ElemType *e){
    if(S->top==-1){   //当栈顶指针指向-1，说明栈空，则无法出栈
        printf("栈空，无法出栈\n");
        return ERROR;
    }else{   //如果栈非空则执行出栈程序
        *e = S->data[S->top];   //将当前栈顶元素的指针赋给可供返回查看的e
        S->top--;   //栈顶元素出栈后，栈顶指针向下走一格，表示新的栈顶元素
        return OK;
    }
}

//获取栈顶元素（只供查看，不出栈）
State getTop(SqStack S, ElemType *e){
    if(S.top==-1){   //当栈顶指针指向-1，说明栈空，栈顶元素为空
        printf("栈空，无栈顶元素\n");
        return ERROR;
    }else{   //当栈非空的时候，则将栈顶元素赋值给可供返回查看的e，但是栈顶元素并不出栈
        *e = S.data[S.top];   //将栈顶元素赋值给e，栈顶指针top不变
        return OK;
    }
}

//遍历打印顺序栈
State printStack(SqStack S){
    if(S.top==-1){   //当栈顶指针指向-1，说明栈空，无栈元素可供打印
        printf("栈空\n");
        return ERROR;
    }
    int i=0;   //计数器，记录当前是第几个元素
    while(S.top!=-1){
        i++;   //栈顶指针还未到-1，则说明当前栈顶指针有元素，计数器+1
        printf("栈顶向下第%d个元素为：%d\n", i, S.data[S.top]);  //当前栈顶指针的元素打印出
        S.top--;   //栈顶指针向下走一格，继续进行循环打印
    }
    return OK;
}

//测试
int main(int argc, const char * argv[]) {
    SqStack S;
    initStack(&S);
    printf("初始化后的线性栈的长度为：%d\n", getLength(S));
    printf("将1-5元素依次入栈可得：\n");
    for(int i=1;i<=5;i++){
        push(&S, i);
    }
    printStack(S);
    printf("此时顺序栈的长度为：%d\n", getLength(S));
    int e;
    pop(&S, &e);
    printf("出栈：%d\n", e);
    pop(&S, &e);
    printf("出栈：%d\n", e);
    printf("现在顺序栈的长度为：%d\n", getLength(S));
    getTop(S, &e);
    printf("获取栈顶元素：%d\n", e);
    printf("现在顺序栈的长度为：%d\n", getLength(S));
    printf("现在顺序栈的为：\n");
    printStack(S);
    clearStack(&S);
    printf("清空顺序栈后的栈为：\n");
    printStack(S);
    printf("长度为：%d", getLength(S));
    return 0;
}

共享空间栈

//
//  main.c
//  ShareStack
//
//  Created by Eason on 2020/8/1.
//  Copyright © 2020 Eason. All rights reserved.
//

#include <stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
typedef int ElemType;
typedef int State;
typedef struct{   //定义共享栈的存储结构
    ElemType data[MAXSIZE];   //用数组存储共享栈的数据，并设定最大值判断栈满
    int lefttop;   //左栈的栈顶指针
    int righttop;   //右栈的栈顶指针
}SharedStack;

//初始化共享栈
State initStack(SharedStack *S){
    S->lefttop = -1;   //将左栈与右栈的栈顶指针指向空栈时的默认值，即初始化成功
    S->righttop = MAXSIZE;
    return OK;
}

//获取共享栈的长度
int getLength(SharedStack S){
    return MAXSIZE-(S.righttop-S.lefttop-1);   //根据共享栈的与数组的特性可得，用栈最大存储量减去未存储量即为当前栈的长度
}

//判断共享栈是否为空
State isEmpty(SharedStack S){
    if(S.lefttop==-1 && S.righttop==MAXSIZE){   //如果左栈右栈的栈顶指针均在初始位置即共享栈为空
        return TRUE;
    }else{
        return FALSE;
    }
}

//判断共享栈是否已满
State isFull(SharedStack S){
    if(S.lefttop+1==S.righttop){   //根据共享栈的特性，当左栈的栈顶指针与右栈栈顶指针相邻的时候则表明当前栈已经没有存储空间了
        return TRUE;
    }else{
        return FALSE;
    }
}

//清空共享栈
State clearStack(SharedStack *S){
    S->lefttop=-1;
    S->righttop=MAXSIZE;   //即将共享栈的左右栈顶指针置为初始值则可以代表已经清空了共享栈
    return OK;
}

//入栈（i=0表示入左栈，i=1表示入右栈）
State push(SharedStack *S, int i, ElemType *e){
    if(isFull(*S)){   //判断是否栈满
        printf("栈满，无法入栈");
        return ERROR;
    }
    if(i!=0 && i!=1){   //判断输入的判断左右栈的标志是否有误
        printf("输入有误！请输入插入左栈的代表数字0或右栈代表数字1！");
        return ERROR;
    }
    if(i==0){   //如果i=0则表示进入左栈
        S->lefttop++;  //入栈时栈顶指针向上走一格指向新的空的栈元素位置
        S->data[S->lefttop]=e;  //将该新的栈顶位置给予特定值e
        return OK;  //
    }
    if(i==1){   //如果i=1则表示进入右栈
        S->righttop--;  //入栈时栈顶指针向上走一格指向新的空的栈元素位置
        S->data[S->righttop]=e;  //将该新的栈顶位置给予特定值e
        return OK;
    }
    return OK;
}

//出栈（i=0表示入左栈，i=1表示入右栈）
State pop(SharedStack *S, int i, ElemType *e){
    if(isEmpty(*S)){   //判断当前共享栈是否栈空，若栈空则无元素可出栈
        printf("栈空，无法出栈");
        return ERROR;
    }
    if(i!=0 && i!=1){   //判断输入的判断左右栈的标志是否有误
        printf("输入有误！请输入插入左栈的代表数字0或右栈代表数字1！");
        return ERROR;
    }
    if(i==0){   //如果i=0则表示想要左栈出栈
        *e = S->data[S->lefttop];   //将左栈的栈顶元素出栈赋给可供返回查看的e
        S->lefttop--;   //出栈完成后栈顶指针向下走一格（即向左走一格）指向新的栈顶元素
        return OK;
    }
    if(i==1){   //如果i=1则表示想要右栈出栈
        *e = S->data[S->righttop];   //将右栈的栈顶元素出栈赋给可供返回查看的e
        S->righttop++;   //出栈完成后栈顶指针向下走一格（即向外右一格）指向新的栈顶元素
        return OK;
    }
    return OK;
}

//获取栈顶元素（i=0表示入左栈，i=1表示入右栈）
State getTop(SharedStack S, int i, ElemType *e){
    if(isEmpty(S)){   //判断是否为空栈，若为空栈则无栈顶元素可供查看
        printf("栈空，无栈顶元素");
        return ERROR;
    }
    if(i!=0 && i!=1){   //判断输入的判断左右栈的标志是否有误
        printf("输入有误！请输入插入左栈的代表数字0或右栈代表数字1！");
        return ERROR;
    }
    if(i==0){   //如果i=0则表示想要获取左栈栈顶元素
        *e = S.data[S.lefttop];   //将左栈的栈顶元素出栈赋给可供返回查看的e（仅获取，栈顶指针无需移动）
        return OK;
    }
    if(i==1){   // //如果i=1则表示想要获取右栈栈顶元素
        *e = S.data[S.righttop];   //将右栈的栈顶元素出栈赋给可供返回查看的e（仅获取，栈顶指针无需移动）
    }
    return OK;
}

//打印共享栈（i=0表示入左栈，i=1表示入右栈，i=3表示全栈打印）
State printStack(SharedStack S, int i){
    if(isEmpty(S)){   //判断是否为空栈，若为空栈则无栈元素可打印
        printf("栈空");
        return OK;
    }
    if(i!=0 && i!=1 && i!=3){   //判断输入的判断左右以及全栈的标志是否有误
        printf("输入有误！请输入插入左栈的代表数字0或右栈代表数字1代表全栈的数字3！");
        return ERROR;
    }
    if(i==0){   //如果i=0则表示想要打印左栈元素
        int i=1;   //当前元素位置计数器
        while(S.lefttop!=-1){   //判断当前栈顶指针是否为初始值，若不是则进行打印
            printf("左栈栈顶向下第%d个元素为：%d\n", i, S.data[S.lefttop]);   //打印当前左栈栈顶元素的数据
            S.lefttop--;   //栈顶元素向下走一格继续循环遍历进行打印（向左走一格）
        }
        return OK;
    }
    if(i==1){   //如果i=0则表示想要打印右栈元素
        int i=1;   //当前元素位置计数器
        while(S.righttop!=MAXSIZE){   //判断当前栈顶指针是否为初始值，若不是则进行打印
            printf("右栈栈顶向下第%d个元素为：%d\n", i, S.data[S.righttop]);   //打印当前右栈栈顶元素的数据
            S.righttop++;   //栈顶元素向下走一格继续循环遍历进行打印（向右走一格）
        }
        return OK;
    }
    if(i==3){   //如果i=3则表示想要打印全栈元素
        int i=1;
        while(S.lefttop!=-1){   //同左栈打印步骤
            printf("左栈栈顶向下第%d个元素为：%d\n", i, S.data[S.lefttop]);
            S.lefttop--;
        }
        i=1;  //左栈元素打印完毕，计数器初始化
        while(S.righttop!=MAXSIZE){   //同右栈打印步骤
            printf("右栈栈顶向下第%d个元素为：%d\n", i, S.data[S.righttop]);
            S.righttop++;
        }
    }
    return OK;
}

//测试
int main(int argc, const char * argv[]) {
    SharedStack S;
    initStack(&S);
    printf("初始化一个共享栈，长度为：%d\n", getLength(S));
    printf("将1-5顺序入左栈得：\n");
    for(int i=1;i<=5;i++){
        push(&S, 0, i);
    }
    printStack(S, 0);
    printf("将11-15顺序入右栈得：\n");
    for(int i=11;i<=15;i++){
        push(&S, 1, i);
    }
    printStack(S, 1);
    printf("全栈为：\n");
    printStack(S, 3);
    printf("当前共享栈是否为空（0非空1空)：%d\n", isEmpty(S));
    printf("当前共享栈是否为满（0非满1满)：%d\n", isFull(S));
    printf("当前共享栈的长度为：%d\n", getLength(S));
    int e;
    pop(&S, 0, &e);
    printf("左栈出栈元素：%d\n", e);
    pop(&S, 0, &e);
    printf("左栈出栈元素：%d\n", e);
    pop(&S, 1, &e);
    printf("右栈出栈元素：%d\n", e);
    getTop(S, 0, &e);
    printf("获取当前左栈的栈顶元素：%d\n", e);
    getTop(S, 1, &e);
    printf("获取当前右栈的栈顶元素：%d\n", e);
    printf("现在共享栈的元素为：\n");
    printStack(S, 3);
    printf("现在共享栈的长度为：%d\n", getLength(S));
    return 0;
}

链栈

//
//  main.c
//  LinkStack
//
//  Created by Eason on 2020/8/1.
//  Copyright © 2020 Eason. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;
typedef struct StackNode{   //链栈的结点存储结构
    ElemType data;   //数据域
    struct StackNode *next;  //指针域
}*StackNodePtr,StackNode;   //StackNodePtr 即struct StackNode {}*

typedef struct{   //链栈头指针的存储结构
    StackNodePtr top;   //链栈头指针
    int count;   //链栈的元素数量计数器
}LinkedStack;

//初始化链栈
Status initStack(LinkedStack *L){
    L->top = (StackNodePtr)malloc(sizeof(StackNode));   //为头结点分配内存空间
    if(!L->top){   //判断内存空间是否分配成功
        return ERROR;
    }
    L->top = NULL;   //空链栈的头结点指针指向空
    L->count = 0;   //链栈内的结点数量初始为0
    return OK;
}

//判断链栈是否为空
Status isEmpty(LinkedStack L){
    if(L.count==0){   //若此时链栈头结点中的计数器为0则说明链栈为空
        return TRUE;
    }else{
        return FALSE;
    }
}

//清空链栈
Status clearStack(LinkedStack *L){
    StackNodePtr p, q;   //定义临时链栈结点
    p = L->top;   //将p作为首个结点
    while(p){   //如果p存在的话则继续循环执行循环体
        q=p;   //将p赋给q
        p=p->next;   //p向下继续进行
        free(q);   //将q释放掉，即完成了p区域的清理，然后继续循环判断
    }
    L->count=0;   //将链栈头结点中的计数器归零
    return OK;
}

//获取链栈的长度
int getLength(LinkedStack L){
    return L.count;   //链栈的长度就是头结点中的计数器数值
}

//链栈的入栈
Status push(LinkedStack *L, ElemType *e){
    StackNodePtr p = (StackNodePtr)malloc(sizeof(StackNode));  //为入栈元素分配内存空间
    p->data=e;  //将新元素的数据域置为指定值
    p->next = L->top;   //将目前的首个结点置为新结点的下一个结点
    L->top = p;   //然后将首个结点设置为p
    L->count++;   //入栈成功，头结点的计数器+1
    return OK;
}

//链栈的出栈
Status pop(LinkedStack *L, ElemType *e){
    StackNodePtr p;   //定义临时结点
    if(isEmpty(*L)){   //出栈先判断当前栈是否为空，为空则没有栈顶元素可以出栈
        printf("链栈为空，无法出栈\n");
        return ERROR;
    }
    p = L->top;   //将p作为链栈的首个结点，即栈顶结点
    *e = p->data;   //将栈顶结点的值赋给e以供返回查看
    L->top = p->next;   //将首个结点的下个结点作为头结点的下个结点（即重新设置首个结点）
    free(p);   //将老的栈顶结点p释放掉
    L->count--;   //出栈成功，头结点的计数器-1
    return OK;
}

//获取链栈的栈顶元素
Status getTop(LinkedStack L, ElemType *e){
    if(isEmpty(L)){   //要获取栈顶元素首先判断当前链栈是否为空栈，若为空栈则无栈顶元素可供获取
        printf("链栈为空，无栈顶元素\n");
        return ERROR;
    }
    *e = L.top->data;   //链栈不为空，则将此时的栈顶元素的数据赋给e以供返回查看
    return OK;
}

//链栈的打印
Status printStack(LinkedStack L){
    if(isEmpty(L)){   //判断链栈是否为空，若为空则无元素可供打印
        printf("链栈为空，无元素可打印\n");
        return ERROR;
    }
    StackNodePtr p;   //定义临时结点p
    int i = 0; //当前位置计数器
    p=L.top;   //将p设置为首个结点
    while(p){   //若p存在的话则执行循环体
        i++;   //若存在则说明当前位置要+1
        printf("链栈由栈顶向下的第%d个元素为：%d\n", i, p->data);   //将当前结点（即栈顶元素）输出
        p = p->next;   //栈顶位置继续向下，循环到p不存在
    }
    return OK;
}

//测试
int main(int argc, const char * argv[]) {
    LinkedStack L;
    initStack(&L);
    printf("初始化链栈后链栈L的长度为：%d\n", getLength(L));
    printf("此时链栈为空为吗？(1为是，0为否）：%d\n", isEmpty(L));
    printf("将1-8顺序入栈得：\n");
    for(int i=1;i<=8;i++){
        push(&L, i);
    }
    printStack(L);
    printf("此时的链栈长度为：%d\n", getLength(L));
    int e;
    getTop(L, &e);
    printf("此时的栈顶元素为：%d\n", e);
    pop(&L, &e);
    printf("出栈：%d\n", e);
    pop(&L, &e);
    printf("出栈：%d\n", e);
    printf("现在的链栈内容为：\n");
    printStack(L);
    getTop(L, &e);
    printf("现在的栈顶元素为：%d\n", e);
    printf("现在链栈的长度为：%d\n", getLength(L));
    printf("清空链栈后的链栈为：\n");
    clearStack(&L);
    printStack(L);
    return 0;
}