社区 › 安全 › 线性结构常见应用之栈[基于郝斌课程]

缑娅瑛 发表于 2025-9-24 11:14:27

线性结构常见应用之栈[基于郝斌课程]

栈的定义：
  一种可以实现“先进后出”的存储结构
  栈类似于箱子，先放进去的最后取出来，最后放入的先取出来
栈的分类：
  静态栈的内核是数组
  动态栈的内核是链表
栈的算法：
  出栈
  压栈
栈的应用：
  函数调用
  中断
  表达式求值
  内存分配
  缓冲处理
  迷宫
/*
@file      main.c
@brief   线性结构常见应用之栈
@author    EricsT (EricsT@163.com)
@version   v1.0.0
@date      2025-09-23
@history   2025-09-23 EricsT - 新建文件
*/

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct NODE
{
        int data;
        NODE* ptrNext;
}* PtrNode, Note;

typedef struct STACK
{
        PtrNode ptrTop;
        PtrNode ptrBottom;
}* PtrStack, Stack;

void InitStack(PtrStack ptrStack);//初始化
void PushStack(PtrStack ptrStack, int pushValue);//压栈
bool PopStack(PtrStack ptrStack);//出栈
void TraverseStack(const PtrStack ptrStack);//遍历
bool IsEmptyStack(const PtrStack ptrStack);//判断是否为NULL
void ClearStack(PtrStack ptrStack);//清空栈

int main(void)
{
        Stack stack;

        InitStack(&stack);

        int pushValue;
        printf("请输入插入数值");
        scanf("%d", &pushValue);
        PushStack(&stack, pushValue);

        printf("请输入插入数值");
        scanf("%d", &pushValue);
        PushStack(&stack, pushValue);

        printf("请输入插入数值");
        scanf("%d", &pushValue);
        PushStack(&stack, pushValue);

        printf("请输入插入数值");
        scanf("%d", &pushValue);
        PushStack(&stack, pushValue);

        printf("请输入插入数值");
        scanf("%d", &pushValue);
        PushStack(&stack, pushValue);

        TraverseStack(&stack);

        PopStack(&stack);

        TraverseStack(&stack);

        ClearStack(&stack);

        TraverseStack(&stack);

        return 0;
}

void InitStack(PtrStack ptrStack)
{//顶栈和底栈都指向空节点

        ptrStack->ptrBottom = (PtrNode)malloc(sizeof(NODE));
        ptrStack->ptrBottom->ptrNext = NULL;

        ptrStack->ptrTop = ptrStack->ptrBottom;
}

void PushStack(PtrStack ptrStack, int pushValue)
{
        PtrNode ptrPushNode = (PtrNode)malloc(sizeof(NODE));

        ptrPushNode->data = pushValue;
        ptrPushNode->ptrNext = ptrStack->ptrTop;

        ptrStack->ptrTop = ptrPushNode;
}

void TraverseStack(const PtrStack ptrStack)
{
        PtrNode ptrNodeCur = ptrStack->ptrTop;

        //while (NULL != ptrNodeCur->ptrNext)
        //{
        //        printf("%d ", ptrNodeCur->data);
        //        ptrNodeCur = ptrNodeCur->ptrNext;
        //}

        while (ptrStack->ptrBottom != ptrNodeCur)
        {
                printf("%d ", ptrNodeCur->data);
                ptrNodeCur = ptrNodeCur->ptrNext;
        }

        printf("\n");
}

bool PopStack(PtrStack ptrStack)
{
        if (IsEmptyStack(ptrStack))//空栈时无法出栈
                return false;

        PtrNode ptrNode = ptrStack->ptrTop;
        ptrStack->ptrTop = ptrNode->ptrNext;
        free(ptrNode);
        //ptrStack->ptrTop = ptrStack->ptrTop->ptrNext;这种写法无法释放原来顶栈的内存
        return true;
}

bool IsEmptyStack(const PtrStack ptrStack)
{
        if (ptrStack->ptrBottom == ptrStack->ptrTop)
                return true;

        return false;
}

void ClearStack(PtrStack ptrStack)
{
        if (IsEmptyStack(ptrStack))
                return;

        PtrNode ptrNoteCur = ptrStack->ptrTop;
        PtrNode ptrNoteNext = NULL;

        while (ptrStack->ptrBottom != ptrNoteCur)
        {
                ptrNoteNext = ptrNoteCur->ptrNext;
                free(ptrNoteCur);//释放内存
                ptrNoteCur = ptrNoteNext;
        }

        ptrStack->ptrTop = ptrStack->ptrBottom;
} 

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

查看完整版本: 线性结构常见应用之栈[基于郝斌课程]