C和数据结构——栈的两种实现和应用

这篇文章围绕 C和数据结构——栈的两种实现和应用 做一份便于复习和查阅的整理，内容以概念梳理、代码实现和关键细节为主。

核心代码

/*这是一个可执行文件，直接粘贴代码就可以执行示例1，修改main函数就可以实现其他的示例。大家如果感兴趣，可以自己修改试试，同时欢迎大家把修改后的main函数放在评论区，供大家参考，谢谢。*/
    #include <bits/stdc++.h>
    using namespace std;
    //任何一种存储结构都可以写成顺序存储和链式存储
    //入栈：Push：*(S.top)++,出栈：Pop:*--S.top；栈顶元素top，从
    /*栈的顺序表结构*/
    #define STACK_INIT_SIZE 100 //初始分配量
    #define STACK_INCREMENT 10  //存储空间分配增量
    typedef char ElemType;
    typedef struct
    {
    ElemType *base; //栈底指针,位置不变
    ElemType *top;  //栈顶指针，top = base 时，栈为空
    int stacksize;  //栈空间大小
    } SqStack;
    //初始化栈
    void intStack(SqStack &S)
    {
    if (!(S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType))))
        exit(OVERFLOW); //存储分配失败
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    }

    //销毁栈
    void DestroyStack(SqStack &S)
    {
    free(S.base);  //首地址
    S.base = NULL; //置空
    S.top = NULL;
    S.stacksize = 0;
    }

    //进栈操作
    void Push(SqStack &S, ElemType e)
    {
    if ((S.top - S.base) >= S.stacksize)
    { //动态扩充空间
        S.base = (ElemType *)realloc(S.base, ((S.stacksize) + STACK_INCREMENT) * sizeof(ElemType));
        if (!S.base)
            exit(OVERFLOW); //判断上一步是否分配成功
        S.top = S.base + S.stacksize;
        S.stacksize += STACK_INCREMENT;
    }
    *(S.top)++ = e; //Push
    }

    //出栈
    int Pop(SqStack &S, ElemType &e)
    {
    if (S.top == S.base) //如果栈空，返回0
        return 0;
    e = *--S.top;
    return 1;
    }

    //取出栈顶元素值,这里并没有对S.top进行修改，因为只是
    int GetTop(SqStack S, ElemType &e) //取出的值通过e返回，但是对S不进行修改
    {
    if (S.top > S.base)
    {
        e = *(S.top - 1); //传出栈顶值
        return 1;
    }
    else
        return 0;
    }

    //判断栈是否为空
    int StackEmpty(SqStack S)
    { //当栈为空的时候，返回值为1,否则为0；
    if (S.top == S.base)
        return 1;
    else
        return 0;
    }

    /*栈的应用，对概念的理解和数据结构有关的数理逻辑分析
    1,判断Pop和Push是否合法：
    定义I为进栈操作，O为出栈操作，已知栈的初始和末尾状态都是空
    请设计程序，使得对于任意的IO序列，都可以判断是否符合要求*/
    //先写出顺序表产生的栈的算法：
    int Right_Not(SqStack &st, char str[])
    {
    int i;
    ElemType x;
    int n = strlen(str);    //计算一下输入的字符串的长度
    for (i = 0; i < n; i++) //循环遍历，给栈填充字符
    {
        if (str[i] == 'I') //I代表入栈
            Push(st, str[i]);
        else if (str[i] == 'O') //O代表出栈，
            if (!Pop(st, x))
            { //判断进行Pop操作之后，栈是否为空，这里其实进行了两步，
                //先Pop一次，然后判断是否成功，成功Pop返回1，就继续循环，
                //如果Pop不成功，也就是Pop返回为0，那么!Pop为1，执行销毁栈，然后返回0；
                DestroyStack(st);
                return 0;
            }
    }
    if (StackEmpty(st)) //判断经过入栈和出栈操作后，栈是否为空
    {
        DestroyStack(st); //为空时说明操作合法，返回1
        return 1;
    }
    else
    {
        DestroyStack(st);
        return 0;
    }
    }
    int main()
    {
    SqStack st;
    char str[3] = "IO";
    int e;
    e = Right_Not(st, str);
    printf("%d", e);
    }

    //2，利用顺序栈的基本操作，设计算法，判断任意给定的字串是否为回文
    /*思路，因为栈的先进后出的特点，可以很容易想到，先将字符串如数Push
    然后再依次Pop,同时每Pop一次，就和字符串的第一个字符比较一次，依次
    进行，直到栈为空，如果出现任意一次不符合，就返回0，否则，返回1；*/
    int Palindrome(char str[], int n)
    {
    SqStack st;
    intStack(st);
    int i;
    char ch;
    for (i = 0; i < n; i++) //将字符串压入栈
        Push(st, str[i]);
    //这里要重新定义i= 0，使得字符串从头遍历，当然，再定义一个j = 0也行，
    //但是基于程序设计的思想，最好少设置变量
    i = 0;
    while (!StackEmpty(st)) //只要栈部位空，就进行比较
    {
        Pop(st, ch);        //将st的栈顶元素依次Pop给ch
        if (ch != str[i++]) //比较ch和str中对应的字符是否匹配
            return 0;       //如果不匹配，返回0；
    }
    }

    //选择合适的存储结构，来判断对于任意表达式中的括号是否匹配
    /*思路：
    比如1*(10+1{10+1})),就不匹配，显然末尾的)没有与之匹配的
    (,分析可知，先出现的括号，要和最后出现的与之匹配的括号对应，
    这不正是栈的特点吗？*/
    int Match(char str[], int n)
    {
    int flag;
    SqStack st;
    intStack(st);
    int flag = 1, i = 0;
    char ch;
    while (i < n && flag == 1)
    {
        switch (str[i])
        { //判断进入的是哪一种括号
        case '(':
        case '{':
        case '[':
            Push(st, str[i]);
            break;
        case ')':
            if (!Pop(st, ch) || ch != '(')
                flag = 0;
            break;
        case ']':
            if (!Pop(st, ch) || ch != ']')
                flag = 0;
            break;
        case '}':
            if (!Pop(st, ch) || ch != '{')
                flag = 0;
            break;
        }
        i++;
        if (StackEmpty(st) && flag == 1)
            return 1;
        else
            return 0;
    }

---

#include <bits/stdc++.h>
using namespace std;
//链栈：采用单链表作为链栈，单链表不带头结点
//此时不存在栈满的情况
//初始时Top ==NULL
//Push：创建新的结点p,将p插到栈顶的位置！头插法！
//Pop:返回栈顶Data值，同时删除该结点
//top指针指向An栈顶，A1指向栈底
typedef char ElemType;
//栈的定义和单链表的定义基本一致
typedef struct node
{
    ElemType data;
    struct node *next;

} LinkStack;

//初始化链栈
void InitStack(LinkStack *&top)
{
    top = NULL;
}

//销毁栈
//说实话，这里暂时没有搞明白
void DestroyStack(LinkStack *&top)
{
    LinkStack *pre = top, *p;
    if (pre == NULL)
        return;
    p = pre->next;
    while (P != NULL)
    {
        free(pre);
        pre = p;
        p = p->next;
    }
    free(pre);
}

//进栈：头插
int Push(LinkStack *&top, ElemType x)
{
    LinkStack *p;
    p = (LinkStack *)malloc(sizeof(LinkStack)); //每次Push都要申请空间
    p->data = x;                                //数据域
    p->next = top;                              //top移动到前面
    top = p;
    return 1;
}

//出栈：通过x返回栈点的值，删除该栈点
int Pop(LinkStack *&top, ElemType &x)
{
    LinkStack *p;
    if (top == NULL) //判断栈空否
        return 0;
    else
    {
        p = top;       //进入栈顶
        x = p->data;   //取
        top = p->next; //链接
        free(p);       //释放top的上一个结点p,则top也被释放了
        return 1;
    }
}

//取栈顶元素
int GetTop(LinkStack *top, ElemType &x) //用X取出值
{
    if (top == NULL) //判断是否为空
        return 0;
    else
    {
        x = top->data; //取出
        return 1;
    }
}

//判断栈是否为空
int StackEmpty(LinkStack *top)
{
    if (top == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}