[数据结构]栈的C语言简单实现

不念不忘少年蓝@ 2022-06-05 04:22 231阅读 0赞

Github:([https://github.com/FlameCharmander/DataStructure][https_github.com_FlameCharmander_DataStructure])  
栈是一种先进后出的数据结构。应用还是挺多的，像括号匹配就是典型的一个。  
之类我只讲实现，没有理论。为了代码的简单易读，我没有考虑健壮性，等你们真正理解了这段代码后，自己就知道该如何去考虑它的健壮性了。

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 100
    #define ElemType char
    #define BOOL int
    #define TRUE 1
    #define FALSE 0
    
    typedef struct{
        int data[MAXSIZE];
        int top;    //栈顶指针
    }Stack;
    
    void InitStack(Stack *s);   //初始化栈
    void Push(Stack *s, ElemType e);    //压栈操作
    void Pop(Stack *s, ElemType *e); //出栈操作
    BOOL IsEmpty(Stack s);  //是否为空
    
    int main()
    {
        Stack s;
        ElemType e;
        InitStack(&s);
        printf("%d\n", IsEmpty(s));
        Push(&s, 'a');
        Push(&s, 'b');
        Pop(&s, &e);
        printf("%c\n", e);
        printf("%d\n", IsEmpty(s));
        Pop(&s, &e);
        printf("%c\n", e);
        printf("%d\n", IsEmpty(s));
        return 0;
    }
    
    void InitStack(Stack *s){
        s->top = -1;
    }
    
    void Push(Stack *s, ElemType e){
        ++s->top;
        s->data[s->top] = e;
    }
    
    void Pop(Stack *s, ElemType *e){
        *e = s->data[s->top];
        --s->top;
    }
    
    BOOL IsEmpty(Stack s){
        if (s.top <= -1){
            return TRUE;
        }else{
            return FALSE;
        }
    }

这里我建议你们新开一个窗口，把代码和下面的部分进行一行一行阅读。  
Line 1~2 导入头文件。  
Line 4 定义栈内的数组大小。  
Line 5 栈内元素的类型。  
Line 6~8 由于C语言没有布尔型，我们用整型代替布尔型。  
Line 10~13 栈的数据结构，包括一个数组（存放元素），一个栈顶指针（初始值应该为-1，表示栈内元素是没有的）。  
Line 15~18 今天主要实现的4个操作，InitStack是初始化，Push是入栈，Pop是出栈，IsEmpty是判断是否为空。  
Line 20~35 main函数，主要对栈进行初始化，入栈，出栈，判断是否为空的操作进行测试。  
Line 37~39 栈的初始化操作，将栈的指针初始为-1。这里说下为什么参数(Stack *s)是用指针的，因为我们需要把栈内的栈顶指针s->top进行修改，那么我们要把栈的结构体以指针进行传给这个函数（指针可以相当于地址或者门牌号），那么这个函数根据这个指针（地址）就能找到栈（main函数定义的那个栈），并且修改。假如你参数直接给的是一个栈，参数是(Stack s)这样写的，不是指针，那传入的这个栈修改之后，main函数定义的那个栈不会有任何修改（相当于你直接复制了一个栈，给了这个InitStack函数，你修改这个栈不会对原来的栈有任何影响）。  
Line 41~44 栈的压栈操作，把数据写到栈里，先要更新栈顶指针++s->top，然后把元素放在栈顶，s->data\[s->top\] = e。这里的栈传入的参数用了指针，原因如上。  
Line 46~49 栈的出栈操作，先把数据读出来*e = s->data\[s->top\]，然后把更新栈顶指针–S->top（移除嘛，自然是减啦）。这里的栈传入的参数用了指针，原因如上。  
Line 51~57 栈的判断为空操作。这里参数的那个栈为什么不用指针了呢，因为我们只需要判断栈里元素是否为空，我们不需要修改任何东西，只需要一个副本（复制一个房子）就可以判断了。再多说一句，其实这里的标准化操作应该也是要传入指针的，只是我这里跟上面进行一个对比，所以故意传入一个副本的。

[https_github.com_FlameCharmander_DataStructure]: https://github.com/FlameCharmander/DataStructure