C语言实现顺序栈和链式栈

电玩女神 2022-02-20 14:41 335阅读 0赞

### 文章目录 ###

*  1 顺序栈
 *  2 链栈

**栈：先进后出**

# 1 顺序栈 #

#include <stdio.h>
    #include <stdlib.h>
    
    #define STACK_INIT_SIZE 100 //栈初始容量
    #define STACKINCREMENT 10 //存储空间分配增量
    typedef int dataType;
    typedef struct { 
        dataType *base; //栈底指针，指向栈底元素
        dataType *top;  //栈顶指针，指向栈顶元素下一位置
        int stackSize;  //栈的容量
    } SqStack;
    
    int initSqStack(SqStack *S); // 创建空栈。创建成功返回1，否则返回0
    int isEmpty(SqStack *S);     // 判空。栈空返回1，否则返回0
    int pushSqStack(SqStack *S, dataType x); // 入栈。入栈失败返回0，否则返回1
    int popSqStack(SqStack *S, dataType *x); // 出栈。出栈失败返回0，否则返回1
    int getTop(SqStack S, dataType *x); // 取栈顶元素。成功取出返回1，否则返回0
    int lengthSqStack(SqStack S);    // 返回栈中元素个数
    void clearSqStack(SqStack *S);   // 清空栈
    void destroySqStack(SqStack *S); // 销毁栈
    void traverseSqStack(SqStack S); // 遍历栈中元素并输出
    
    int main()
    { 
        SqStack S;
        int i;
        dataType x;
    
        initSqStack(&S);
        for (i = 0; i < 10; i++) { 
            pushSqStack(&S, i);
        }
        traverseSqStack(S);
        printf("栈中元素个数为：%d\n", lengthSqStack(S));
    
        topSqStack(S, &x);
        printf("栈顶元素为：%d\n", x);
    
        int count = lengthSqStack(S);
        for (i = 0; i < count; i++) { 
            popSqStack(&S, &x);
        }
        traverseSqStack(S);
        printf("栈中元素个数为：%d\n", lengthSqStack(S));
    
        destroySqStack(&S);
    
        return 0;
    }
    
    // 创建空栈。创建成功返回1，否则返回0
    int initSqStack(SqStack *S)
    { 
        S->base = (dataType *)malloc(STACK_INIT_SIZE * sizeof(dataType));
        if (!S->base)
            return 0;
        S->top = S->base;
        S->stackSize = STACK_INIT_SIZE;
        return 1;
    }
    // 判空。栈空返回1，否则返回0
    int isEmpty(SqStack *S)
    { 
        if (S->top == S->base)
            return 1;
        else
            return 0;
    }
    // 入栈。入栈失败返回0，否则返回1
    int pushSqStack(SqStack *S, dataType x)
    { 
        if (S->top - S->base >= S->stackSize) { 
            S->base = (dataType *)realloc(
                S->base, (STACK_INIT_SIZE + STACK_INIT_SIZE) * sizeof(dataType));
            if (!S->base)
                return 0;
            S->top = S->base + S->stackSize;
            S->stackSize += STACKINCREMENT;
        }
        *S->top++ = x;
        return 1;
    }
    // 出栈。出栈失败返回0，否则返回1
    int popSqStack(SqStack *S, dataType *x)
    { 
        if (isEmpty(S) == 1)
            return 0;
        else { 
            *x = *--S->top;
            return 1;
        }
    }
    // 取栈顶元素。成功取出返回1，否则返回0
    int getTop(SqStack S, dataType *x)
    { 
        if (S.top == S.base)
            return 0;
        else { 
            *x = *(S.top - 1);
            return 1;
        }
    }
    // 返回栈中元素个数
    int lengthSqStack(SqStack S)
    { 
        if (S.top == S.base)
            return 0;
        else
            return S.top - S.base;
    }
    // 清空栈
    void clearSqStack(SqStack *S)
    { 
        S->top = S->base;
        printf("顺序栈已被清空！\n");
    }
    // 销毁栈
    void destroySqStack(SqStack *S)
    { 
        if (S->base == NULL)
            printf("栈已被销毁！\n");
        else { 
            free(S->base);
            S->base == NULL;
            printf("栈已被销毁！\n");
        }
    }
    
    void traverseSqStack(SqStack S)
    { 
        int count = lengthSqStack(S);
    
        if (count == 0)
            printf("栈为空！\n");
        else { 
            int i;
            for (i = 0; i < count; i++) { 
                printf("%d, ", *(--S.top));
            }
            printf("\n");
        }
    }

![在这里插入图片描述][2019041323594276.jpg]

# 2 链栈 #

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int dataType;
    typedef struct node // 栈节点
    { 
        dataType data;
        struct node *next;
    } StackNode;
    
    typedef struct // 栈结构
    { 
        StackNode *top; // 栈顶指针，指向栈顶元素
        int lengtgh;    // 栈中元素个数
    } LinkStack;
    
    int initLinkStack(LinkStack *S); // 创建空栈。创建成功返回1，否则返回0
    int pushLinkStack(LinkStack *S, dataType x); // 入栈。入栈失败返回0，否则返回1
    int popLinkStack(LinkStack *S, dataType *x); // 出栈。出栈失败返回0，否则返回1
    int getTop(LinkStack S, dataType *x); // 取栈顶元素。成功取出返回1，否则返回0
    void destroyLinkStack(LinkStack *S);  // 销毁栈
    void traverseLinkStack(LinkStack *S); // 遍历栈中元素并输出
    
    int main()
    { 
        LinkStack S;
        int i;
        dataType x;
    
        initLinkStack(&S);
        for (i = 0; i < 10; i++) { 
            pushLinkStack(&S, i * 10);
        }
        traverseLinkStack(&S);
        printf("栈中元素个数为：%d\n", S.lengtgh);
    
        getTop(S, &x);
        printf("栈顶元素为：%d\n", x);
    
        int n = S.lengtgh;
        for (i = 0; i < n; i++) { 
            popLinkStack(&S, &x);
        }
        traverseLinkStack(&S);
        printf("栈中元素个数为：%d\n", S.lengtgh);
    
        destroyLinkStack(&S);
    
        return 0;
    }
    
    // 创建空栈。创建成功返回1，否则返回0
    int initLinkStack(LinkStack *S)
    { 
        S->top = NULL;
        S->lengtgh = 0;
        return 1;
    }
    // 入栈。入栈失败返回0，否则返回1
    int pushLinkStack(LinkStack *S, dataType x)
    { 
        StackNode *p;
    
        p = (StackNode *)malloc(sizeof(StackNode));
        if (!p)
            return 0;
        else { 
            p->data = x;
            p->next = S->top;
            S->top = p;
            S->lengtgh++;
            return 1;
        }
    }
    // 出栈。出栈失败返回0，否则返回1
    int popLinkStack(LinkStack *S, dataType *x)
    { 
        if (S->lengtgh == 0)
            return 0;
        else { 
            StackNode *p = S->top;
    
            S->top = p->next;
            S->lengtgh--;
            *x = p->data;
            free(p);
            return 1;
        }
    }
    // 取栈顶元素。成功取出返回1，否则返回0
    int getTop(LinkStack S, dataType *x)
    { 
        if (S.lengtgh == 0)
            return 0;
        else { 
            *x = S.top->data;
            return 1;
        }
    }
    // 销毁栈
    void destroyLinkStack(LinkStack *S)
    { 
        if (S->lengtgh == 0)
            printf("要销毁的栈不存在！\n");
        else { 
            dataType x;
            while (S->lengtgh != 0) { 
                popLinkStack(S, &x);
            }
            printf("栈已被销毁！\n");
        }
    }
    
    void traverseLinkStack(LinkStack *S)
    { 
        if (S->lengtgh == 0)
            printf("栈中元素为：空！\n");
        else { 
            int i;
            StackNode *p = S->top;
    
            printf("栈中元素为：");
            for (i = 0; i < S->lengtgh; i++) { 
                printf("%d, ", p->data);
                p = p->next;
            }
            printf("\n");
        }
    }

![在这里插入图片描述][20190414094619777.jpg]

[2019041323594276.jpg]: /images/20220220/8fe5ef632e0a4a6bb1c086057ec02aea.png
[20190414094619777.jpg]: /images/20220220/c80b9b72ca4a426e91e54ffe632f1e8b.png