)
栈
一.核心定义
栈是一种特殊的线性表，其数据元素的插入和删除操作只能在线性表的同一端进行。
这个特性通常被形象地概括为：后进先出 或 先进后出。
二.关键术语
栈顶：允许进行插入和删除操作的一端。
栈底：不允许进行操作的另一端，它是固定的。
空栈：不包含任何数据元素的栈。
入栈 / 压栈：向栈顶插入一个新元素。
出栈 / 弹栈：从栈顶删除一个元素
三. 栈的分类
1.按存储结构分类
数组栈（顺序栈）和链表栈，也是我们这篇文章主要讲述的方面
2.按容量是否可变分类
静态栈和动态栈
3.按功能用途分类（了解即可）
通用栈、双端栈、受限栈、特殊功能栈
数组栈（顺序栈）
一.核心思想
用一个数组存数据，用一个变量top表示栈顶下标。
空栈：top=-1；入栈：top++，再放数据；出栈：取arr[top]，再top–。
二. 优缺点
优点:
1.访问速度极快：通过下标（top）直接定位栈顶，入栈(Push)、出栈(Pop)、取栈顶(GetTop)操作快。
2.实现极其简单：结构清晰，代码简洁。
缺点:
1.容量固定：最大的问题。
2.难以扩容：扩容难度大，不如动态栈方便。
三.完整代码（C语言）
#include<stdio.h>// 初始最大容量，可自定义#defineMAXSIZE10// 数组栈结构体typedefstruct{intdata[MAXSIZE];inttop;// 栈顶指针}Stack;// 初始化栈voidinitStack(Stack*s){s->top=-1;}// 判断栈空intisEmpty(Stack*s){returns->top==-1;}// 判断栈满intisFull(Stack*s){returns->top==MAXSIZE-1;}// 入栈intpush(Stack*s,intval){if(isFull(s)){printf("栈满，无法入栈\n");return0;}s->data[++s->top]=val;return1;}// 出栈intpop(Stack*s,int*val){if(isEmpty(s)){printf("栈空，无法出栈\n");return0;}*val=s->data[s->top--];return1;}// 取栈顶intgetTop(Stack*s,int*val){if(isEmpty(s))return0;*val=s->data[s->top];return1;}// 遍历栈voidshowStack(Stack*s){if(isEmpty(s)){printf("栈空\n");return;}printf("栈内容（栈底→栈顶）：");for(inti=0;i<=s->top;i++){printf("%d ",s->data[i]);}printf("\n");}// 测试intmain(){Stack s;initStack(&s);push(&s,10);push(&s,20);push(&s,30);showStack(&s);intval;pop(&s,&val);printf("出栈元素：%d\n",val);showStack(&s);getTop(&s,&val);printf("当前栈顶：%d\n",val);return0;}代码运行结果
链表栈
一.核心思想
用单链表实现的栈,关于单链表的知识可以参考其他文章
二.优缺点
优点：
1.没有容量限制
2.不用扩容
缺点
1.代码较复杂
2.速度稍慢
3.占用空间较大
三.完整代码
#include<stdio.h>#include<stdlib.h>// 链表结点结构typedefstructNode{intdata;structNode*next;}Node;// 栈结构（只需要栈顶指针）typedefstruct{Node*top;}LinkStack;// 初始化栈voidInitStack(LinkStack*s){s->top=NULL;}// 判断栈是否为空intIsEmpty(LinkStack*s){returns->top==NULL;}// 入栈intPush(LinkStack*s,intvalue){Node*p=(Node*)malloc(sizeof(Node));if(p==NULL){printf("内存分配失败\n");return0;}p->data=value;p->next=s->top;s->top=p;return1;}// 出栈intPop(LinkStack*s,int*value){if(IsEmpty(s)){printf("栈空，无法出栈\n");return0;}Node*p=s->top;*value=p->data;s->top=p->next;free(p);return1;}// 取栈顶元素（不删除）intGetTop(LinkStack*s,int*value){if(IsEmpty(s))return0;*value=s->top->data;return1;}// 遍历栈（从栈顶到栈底）voidShowStack(LinkStack*s){if(IsEmpty(s)){printf("栈空\n");return;}Node*p=s->top;printf("栈元素(顶→底)：");while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");}// 销毁栈，释放所有结点voidDestroyStack(LinkStack*s){Node*p=s->top,*q;while(p!=NULL){q=p->next;free(p);p=q;}s->top=NULL;}// 主函数测试intmain(){LinkStack s;InitStack(&s);Push(&s,10);Push(&s,20);Push(&s,30);Push(&s,40);ShowStack(&s);intval;Pop(&s,&val);printf("出栈元素：%d\n",val);GetTop(&s,&val);printf("当前栈顶：%d\n",val);ShowStack(&s);DestroyStack(&s);return0;}代码运行结果
总结
数组栈：快、简单、省空间，但大小受限
链表栈：大小不限、灵活，但慢一点、占空间
