目录

• • • • 一、栈的相关概念
      • 二、栈的基本操作
      • 三、顺序栈
      • • 3.1 顺序栈的定义
        • 3.2 顺序栈的操作
        • • `InitStack(*S)`:构造一个空栈S
          • `StackEmpty(S)`:若栈S为空栈，则返回TRUE，否则为FALSE。
          • `Push(*S,e)`:插入元素e为新的栈顶元素
          • `Pop(*S,*e)`:删除S的栈顶元素，并用e返回其值。
          • `StackLength(S)`:返回栈S的元素个数，即栈的长度。
          • `GetTop(S,*e)`:用e返回栈顶元素
          • `StackTraverse(S)`:从栈底到栈顶依次遍历栈S，打印其中的元素
          • `DestoryStack(*S)`:销毁栈
          • `ClearStack(*S)`:栈S清为空栈
        • 3.3 完整源码
      • 四、链栈

一、栈的相关概念 栈的定义

栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。因此，对于栈来说，表尾端有着特殊含义，称为栈顶(top),相应地，表头段称为栈底(bottom)。不含元素的空表叫做空栈。

栈顶：线性表允许进行插入删除的那一端。
栈底：固定的，不允许进行插入和删除的一端。
空栈：不含任何元素的空表。
栈的操作特性：后进先出（Last In First Out）

假设某个栈S=(a1,a2,…,an),则称a1为栈底元素，an为栈顶元素。
栈中的元素按照a1,a2,…,an的顺序进栈，退栈的第一个元素应为栈顶元素。
换句话说，栈的修改是按后进先出的原则进行的，可以简称为LIFO；

【数据结构|栈(操作受限的线性表)---C语言版】栈的示意图：

文章图片

栈的数学特性

n个不同的元素进栈，出栈元素不同的排列的个数为 1 n + 1 C 2 n n \frac{1}{n+1}C_{2n}^n n+11?C2nn?。该公式称为卡特兰数。

二、栈的基本操作

• InitStack(*S):构造一个空栈S
• StackEmpty(S):若栈S为空栈，则返回TRUE，否则为FALSE。
• Push(*S,e):插入元素e为新的栈顶元素
• Pop(*S,*e):删除S的栈顶元素，并用e返回其值。
• StackLength(S):返回栈S的元素个数，即栈的长度。
• GetTop(S,*e):用e返回栈顶元素
• StackTraverse(S):从栈底到栈顶依次遍历栈S，打印其中的元素
• DestoryStack(*S):销毁栈
• ClearStack(*S):栈S清为空栈

接下来便分为栈的顺序存储和链式存储来实现这些操作。
三、顺序栈 采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素。
3.1 顺序栈的定义 顺序栈实际上也就是操作受限的顺序表，我们这里采用动态分配的方式。关于顺序表的内容，可以查看顺序表（线性表的顺序存储）—C语言版
仍旧使用该例子，我们要如何存储该表呢？

id	name	description
1	史强	最强辅助
2	章北海	我不需要钢印，我是自己思想的主人
3	罗辑	人类不感谢罗辑
4	维德	失去人性，失去很多。失去兽性，失去一切

步骤一：声明数据元素类型

首先我们使用结构体声明数据元素（对应表中的一行数据）的类型

typedef struct{ int id; //对应表中的id char name[100]; //对应表中的姓名 char description[200]; //对应表中的描述 }SElemType; //此处的SElemType是个类型名

步骤二：顺序栈的定义

#define InitSize 10; //栈的初始长度 #define ListIncrement 2; //扩容时的分配增量 typedef struct{ SElemType *base; //栈的基地址，指示动态分配的数组的指针 SElemType *top; //栈顶指针 int MaxSize; //当前栈的最大存储长度 }SqStack; //顺序栈的类型定义

3.2 顺序栈的操作

• 栈结构不存在：base==NULL;
• 栈为空：base==top
• 入栈：*top=e; top++; 先赋值再加一
• 出栈：top--; *e=*top; 先减一再返回
  
  文章图片
  

InitStack(*S):构造一个空栈S

/*初始化*/ int InitStack(SqStack *S){ S->base=(SElemType *)malloc(sizeof(SElemType)*InitSize); //给栈分配存储空间 if(!S->base) return FALSE; //分配失败返回FALSE S->top=S->base; //空栈的top和base指向同一个位置 S->MaxSize=InitSize; //初始最大长度 return TRUE; //成功初始化返回TRUE }

StackEmpty(S):若栈S为空栈，则返回TRUE，否则为FALSE。

/*判断是否为空栈*/ int StackEmpty(SqStack S){ if (S.base==S.base) return TRUE; return FALSE; }

Push(*S,e):插入元素e为新的栈顶元素

/*插入*/ int Push(SqStack *S,SElemType e){ if(S->top-S->base>=S->MaxSize){ S->base=(SElemType*)realloc(S->base,(S->MaxSize+StackIncrement)*sizeof(SElemType)); //栈满追加存储空间 if (!S->base) return FALSE; //存储分配失败 S->top=S->base; S->MaxSize+=StackIncrement; } *S->top++=e; //先赋值再加一 return TRUE; }

Pop(*S,*e):删除S的栈顶元素，并用e返回其值。

/*删除*/ int Pop(SqStack *S,SElemType *e){ if (S->top==S->base) return FALSE; //如果栈为空，返回 *e=*(--S->top); //先减一再返回 return TRUE; }

StackLength(S):返回栈S的元素个数，即栈的长度。

/*求栈长*/ int StackLength(SqStack S){ int length=0; for( ; S.base.top; S.base++){ length++; } return length; }

GetTop(S,*e):用e返回栈顶元素

/*获取栈顶元素*/ int GetTop(SqStack S,SElemType *e){ if (S.top==S.base) return FALSE; *e=*(S.top-1); return TRUE; }

StackTraverse(S):从栈底到栈顶依次遍历栈S，打印其中的元素

/*打印*/ void StackTraverse(SqStack S){ for ( ; S.base.top; S.base++){ printf("id=%d,name=%s,description=%s\n",S.base->id,S.base->name,S.base->description); } }

DestoryStack(*S):销毁栈

/*销毁顺序表*/ void DestroyStack(SqStack *S){ free(S->base); S->MaxSize=0; S->base=NULL; S->top=NULL; }

ClearStack(*S):栈S清为空栈

/*清空栈*/ void ClearStack(SqStack *S){ S->top=S->base; }

3.3 完整源码

#include #include #define TRUE 1 #define FALSE 0 #define InitSize 10//表的初始长度 #define StackIncrement 2//扩容时的分配增量 typedef struct{ int id; //对应表中的id char name[100]; //对应表中的姓名 char description[200]; //对应表中的描述 }SElemType; //此处的SElemType是个类型名typedef struct{ SElemType *base; //栈的基地址，指示动态分配的数组的指针 SElemType *top; //栈顶指针 int MaxSize; //当前栈的最大存储长度 }SqStack; //顺序栈的类型定义/*初始化*/ int InitStack(SqStack *S){ S->base=(SElemType *)malloc(sizeof(SElemType)*InitSize); //给栈分配存储空间 if(!S->base) return FALSE; //分配失败返回FALSE S->top=S->base; //空栈的top和base指向同一个位置 S->MaxSize=InitSize; //初始最大长度 return TRUE; //成功初始化返回TRUE } int StackEmpty(SqStack S){ if (S.base==S.base) return TRUE; return FALSE; }/*插入*/ int Push(SqStack *S,SElemType e){ if(S->top-S->base>=S->MaxSize){ S->base=(SElemType*)realloc(S->base,(S->MaxSize+StackIncrement)*sizeof(SElemType)); //栈满追加存储空间 if (!S->base) return FALSE; //存储分配失败 S->top=S->base; S->MaxSize+=StackIncrement; } *S->top++=e; //先赋值再加一 return TRUE; } /*删除*/ int Pop(SqStack *S,SElemType *e){ if (S->top==S->base) return FALSE; //如果栈为空，返回 *e=*(--S->top); return TRUE; }/*求栈长*/ int StackLength(SqStack S){ int length=0; for(; S.base.top; S.base++){ length++; } return length; }/*获取栈顶元素*/ int GetTop(SqStack S,SElemType *e){ if (S.top==S.base) return FALSE; *e=*(S.top-1); return TRUE; }/*打印*/ void StackTraverse(SqStack S){ for ( ; S.base.top; S.base++){ printf("id=%d,name=%s,description=%s\n",S.base->id,S.base->name,S.base->description); } }/*销毁顺序表*/ void DestroyStack(SqStack *S){ free(S->base); S->MaxSize=0; S->base=NULL; S->top=NULL; }/*清空栈*/ void ClearStack(SqStack *S){ S->top=S->base; }int main(void){ ///初始化SqStack S; int i=InitStack(&S); if (i==1){ printf("初始化成功\n"); }else{ printf("初始化失败\n"); } printf("\n"); ///插入 SElemType a[4]={ {1,"史强","最强辅助"}, {2,"章北海","我不需要钢印，我是自己思想的主人"}, {3,"罗辑","人类不感谢罗辑"}, {4,"维德","失去人性，失去很多。失去兽性，失去一切"} }; int j; for ( j = 0; j < 4; j++){ i=Push(&S,a[j]); } StackTraverse(S); printf("\n"); 删除 SElemType e; Pop(&S,&e); printf("被删除的元素：id=%d,name=%s,description=%s\n",e.id,e.name,e.description); printf("删除之后：\n"); StackTraverse(S); printf("\n"); //获取栈顶元素 i=GetTop(S,&e); printf("栈顶元素：id=%d,name=%s,description=%s\n",e.id,e.name,e.description); printf("\n"); //销毁查找 DestroyStack(&S); StackTraverse(S); //打印为空了 }

运行结果：

初始化成功id=1,name=史强,description=最强辅助 id=2,name=章北海,description=我不需要钢印，我是自己思想的主人 id=3,name=罗辑,description=人类不感谢罗辑 id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切被删除的元素：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切 删除之后： id=1,name=史强,description=最强辅助 id=2,name=章北海,description=我不需要钢印，我是自己思想的主人 id=3,name=罗辑,description=人类不感谢罗辑栈顶元素：id=3,name=罗辑,description=人类不感谢罗辑

四、链栈

推荐阅读

• 

  健康码申诉多久有结果
• 

  脑卒中|它比癌症死亡率还高，每21秒就有1人因它死去！预防方法却很简单
• 

  酸枣仁泡水喝正确方法和用量 酸枣仁泡水喝正确方法
• 

  爱普生nx410清零
• 

  2017-2018学年八年级英语教学工作总结
• 

  民国时期的军阀孙传芳是怎么死的
• 

  佳能痰盂镜头 尼康小痰盂镜头半幅
• 

  遇到松下三匹变频空调外机不转怎么办？3个处理方法帮助你
• 

  苹果id锁定是什么意思（苹果ld锁定的意思）
• 

  如何提高文笔和写作能力 怎么提高写作水平
• 

  烧开的艾叶水能连续泡几天吗
• 

  外出烧烤必备烧烤食材清单
• 

  魔域手游9月14日更新内容介绍 全新功能寄售行上线
• 

  舷组词 汉字舷组词
• 

  68531异常指标分析
• 

  这一世，只为你
• 

  梦见打牌赢钱是什么意思
• 

  什么是即席分析,smartview即席分析
• 

  水中毒是怎么引起的
• 

  逃离塔科夫霰弹枪技能效果介绍 霰弹枪技能特效是什么

• 数据结构|遗落在时光里的静态链表（线性表的静态存储）---C语言版
• c语言|单链表（线性表的链式存储）---C语言版
• c语言|垃圾回收GC经典算法
• 单片机|单片机学会了有出路吗（学单片机有什么用？）
• 蓝桥杯|蓝桥杯 试题 基础练习 杨辉三角形
• 没事就吃树莓派|【树莓派C语言开发】实验05（激光传感器模块）
• 总结|STL讲课讲义
• #|kuangbin线段树专题
• Codeforces|Codeforces940F Machine Learning (带修莫队)