数据结构——栈（C语言实现）

左手的ㄟ右手 2023-01-01 14:54 210阅读 0赞

### 目录 ###

*  结构定义
 *  结构操作
 *  代码实现

# 结构定义 #

栈是一种先进后出的数据结构（FILO），类比现实中的例子就是放羽毛球的圆筒，最先放进去的，会最后才拿出来用。栈是一种顺序结构，用一段连续的存储空间存储元素，所以可以用动态数组。使用栈一般都是用于处理具有完全包含关系的问题，例如括号匹配。

1.  数据空间`data`。动态开辟数组空间。
2.  空间大小`size`。记录数组空间的大小。
3.  栈顶元素下标`top`。记录当前栈顶元素在数组中的下标。

# 结构操作 #

1.  初始化`init()`。创建栈并初始化栈空间。
2.  清除栈`clear()`。清除栈空间。
3.  入栈`push()`。将元素压进栈空间。
4.  出栈`pop()`。将元素弹出栈空间。
5.  取元素`front()`。取出栈顶元素。
6.  扩容`expand()`。当栈内空间已满，还要入栈时，扩容栈空间。
7.  判空`empty()`。判断栈内空间是否为空。

# 代码实现 #

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Stack {
        
        //定义指向动态数组空间的指针
        int *data;
        //定义栈顶下标，栈空间大小
        int top, size;
    } Stack;
    
    Stack *init(int n) {
        
        //开辟栈结构空间
        Stack *s = (Stack *)malloc(sizeof(Stack));
        //开辟动态数组空间
        s->data = (int *)malloc(sizeof(int) * n);
        //初始化栈空间大小
        s->size = n;
        //初始化栈顶下标
        s->top = -1;
        return s;
    }
    
    int empty(Stack *s) {
        
        //如果栈顶下标为-1，则为空
        return s->top == -1;
    }
    
    int expand(Stack *s) {
        
        //定义扩容大小
        int extr = s->size;
        //指向新空间的指针
        int *p;
        //当扩容大小不为0，重复扩容操作
        while (extr) {
        
            //扩容操作
            p = (int *)realloc(s->data, sizeof(int) * (s->size + extr));
            //p不为空，扩容成功
            if (p) break;
            //扩容失败，减少扩容大小
            extr /= 2;
        }
        //p为空，扩容失败，返回0
        if (!p) return 0;
        //扩容成功，更新栈空间指向，空间大小
        s->data = p;
        s->size += extr;
        return 1;
    }
    
    int top(Stack *s) {
        
        //返回数组空间中栈顶下标的元素
        return s->data[s->top];
    }
    
    int push(Stack *s, int val) {
        
        //栈结构为空，返回0
        if (s == NULL) return 0;
        //栈空间满了，进行扩容操作
        if (s->top + 1 == s->size) {
        
            //如果扩容失败，返回0
            if (!expand(s)) return 0;
        }
        //元素入栈，更新栈顶下标
        s->data[++(s->top)] = val;
        return 1;
    }
    
    int pop(Stack *s) {
        
        //栈结构为空，返回0
        if (s == NULL) return 0;
        //栈空间为空，返回0
        if (empty(s)) return 0;
        //更新栈顶下标，相当于旧元素弹出
        s->top--;
        return 1;
    }
    
    void clear(Stack *s) {
        
        if (s == NULL) return ;
        //释放栈开辟的动态数据
        free(s->data);
        //释放栈结构空间
        free(s);
        return ;
    }