栈的定义:
一种可以实现“先进后出”的存储结构
栈类似于箱子,先放进去的最后取出来,最后放入的先取出来
栈的分类:
静态栈的内核是数组
动态栈的内核是链表
栈的算法:
出栈
压栈
栈的应用:
函数调用
中断
表达式求值
内存分配
缓冲处理
迷宫
/*
@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;
}