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

栈的定义：

  一种可以实现“先进后出”的存储结构

  栈类似于箱子，先放进去的最后取出来，最后放入的先取出来

栈的分类：

  静态栈的内核是数组

  动态栈的内核是链表

栈的算法：

  出栈

  压栈

栈的应用：

  函数调用

  中断

  表达式求值

  内存分配

  缓冲处理

  迷宫

/*
@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;
}