参考书：王道考研数据结构

（此贴为博主学习408的笔记，因博主也是学习者，个人总结如有错误欢迎指正。如有侵权请告知，马上删除致歉）​​

目录

一：栈的定义

二：常用的基本操作

三：操作代码

1.栈的顺序存储类型描述

2. 栈判空

3.初始化一个栈

4.进栈

5.出栈

6.读取栈顶元素

7.清空栈

8.销毁栈

9.遍历输出

四：完整代码

一：栈的定义

栈（Stack）是一种后进先出的线性表，限定这种类型的线性表为只能在某一端进行插入和删除操作。

基于栈的特性，我们把它称作后进先出表（Last in First out）LIFO。

常用术语：

栈顶（Top）：线性表允许插入和删除的那一端。

栈底：不可操作的那一端。

空栈：不包含任何元素的空表。

二：常用的基本操作

在国内计算机研究生考试中，如果没有明确规定操作名称，题干没有给出限制，则可以直接使用这些常用操作函数。

以下是基于严蔚敏版的基本操作：

InitStack(&S):初始化一个空表。

StackEmpty(&S): 判断栈是否为空，若为空则返回true，否则为false。

Push(&S,x): 进栈，若栈未满，则将新元素插入到S.top+1的位置。

Pop(&S,&x): 出栈,若栈未空，则将栈顶S.top元素赋值给x，并将Top指针-1。

GetTop(S,&x) :读取栈顶元素，若栈未空，将栈顶元素赋值给x

DestroyStack(&S):销毁栈，并释放栈所用空间。

ClearStack(&S):清空栈，将Top指针指向-1的初始化位置。

三：操作代码

1.栈的顺序存储类型描述

#define MaxSize 10/**栈的顺序存储类型描述栈顶指针S.top,初始化时设置S.top=-1;栈顶元素S.data[S.top];**/typedef struct SqStack{int data[MaxSize];//存放栈元素int top;//栈顶指针}SqStack;

2. 栈判空

/**栈判空**/bool StackEmpty(SqStack S){if(S.top==-1) //栈空return true;else return false;}

功能演示

3.初始化一个栈

/**初始化一个栈，并将栈顶指针指向-1*/void InitStack(SqStack &S){S.top = -1; //初始化栈顶指针}

4.进栈

/**进栈**/bool Push(SqStack &S,int x){if(S.top==MaxSize-1) //栈顶指针指向最后一个，栈满，报错，因为数组下标从0开始，数组下标最大值为Max-1return false;S.data[++S.top] = x; //应熟练掌握++i和i++的区别，这里因为top指针指向的是栈目前最后一个元素，需要将指针移到下一个再装填新元素，否则会覆盖，所以使用++S.top。return true;}

功能演示

5.出栈

/**出栈*/bool Pop(SqStack &S,int &x){if(S.top==-1)return false;x = S.data[S.top--]; //将栈顶元素弹出，指针往下-1。return true;}

功能演示

6.读取栈顶元素

/**读取栈顶元素*/int GetTop(SqStack S){if(S.top==-1)return false; int x = S.data[S.top];return x;}

功能演示

7.清空栈

/*清空栈*/bool ClearStack(SqStack &S){if(S.top==-1)return false;S.top=-1; //将栈顶指针指向-1,遍历的时候到top就结束return true;}

8.销毁栈

/**销毁栈*/bool DestroyStack(SqStack &S){if(S.top==-1)return false;free(S.data);return true;}

9.遍历输出

/**遍历输出栈*/bool PrintStack(SqStack S){if(S.top==-1){printf("栈为空");return false;}for(int i =0;i<=S.top;i++){printf("|%d|\n",S.data[S.top-i]);}return true;}

功能演示

四：完整代码

#include #include /**********************************************制作人：祝星。项目名称：数据结构-顺序栈的基本操作（C语言实现）完成时间：2022年7月21日完成内容：栈的定义，创建，判空运行环境：win10程序环境：VC++文件语言：C语言文件类型：.cpp注：1.VC++的.cpp环境，&为取地址。***********************************************/#define MaxSize 10/**栈的顺序存储类型描述栈顶指针S.top,初始化时设置S.top=-1;栈顶元素S.data[S.top];**/typedef struct SqStack{int data[MaxSize];//存放栈元素int top;//栈顶指针}SqStack;/**栈判空**/bool StackEmpty(SqStack S){if(S.top==-1) //栈空return true;else return false;}/**初始化一个栈，并将栈顶指针指向-1*/void InitStack(SqStack &S){S.top = -1; //初始化栈顶指针}/**进栈**/bool Push(SqStack &S,int x){if(S.top==MaxSize-1) //栈顶指针指向最后一个，栈满，报错，因为数组下标从0开始，数组下标最大值为Max-1return false;S.data[++S.top] = x; //应熟练掌握++i和i++的区别，这里因为top指针指向的是栈目前最后一个元素，需要将指针移到下一个再装填新元素，否则会覆盖，所以使用++S.top。return true;}/**出栈*/bool Pop(SqStack &S,int &x){if(S.top==-1)return false;x = S.data[S.top--]; //将栈顶元素弹出，指针往下-1。return true;}/**读取栈顶元素*/int GetTop(SqStack S){if(S.top==-1)return false; int x = S.data[S.top];return x;}/*清空栈*/bool ClearStack(SqStack &S){if(S.top==-1)return false;S.top=-1; //将栈顶指针指向-1,遍历的时候到top就结束return true;}/**销毁栈*/bool DestroyStack(SqStack &S){if(S.top==-1)return false;free(S.data);return true;}/**遍历输出栈*/bool PrintStack(SqStack S){if(S.top==-1){printf("栈为空");return false;}for(int i =0;i<=S.top;i++){printf("|%d|\n",S.data[S.top-i]);}return true;}int main(){SqStack S;InitStack(S);int chose;int push,pop;printf("\n---------------------------------------------\n");printf("请选择功能：\n1：入栈 2：出栈3：判空4：读取栈顶元素 4：遍历6:清空栈 7：销毁栈\n");scanf("%d",&chose);while(chose == 0 || chose == 1 ||chose == 2 ||chose == 3 ||chose == 4 ||chose == 5 ||chose == 6 ||chose == 7 ){switch(chose){case 0:scanf("%d",&chose);continue;case 1:printf("请输入入栈数：");scanf("%d",&push);Push(S,push);printf("入栈后为：\n");PrintStack(S);chose = 0;break;case 2:Pop(S,pop);printf("将栈顶元素 %d 出栈\n",pop);printf("出栈后为：\n");PrintStack(S);pop = NULL;chose = 0;break;case 3:if(StackEmpty(S)){printf("栈空\n");}elseprintf("栈不为空\n");chose = 0;break;case 4:printf("栈顶元素为%d",GetTop(S));chose = 0;break;case 5:PrintStack(S);chose = 0;break;case 6: ClearStack(S); printf("清空栈\n");chose = 0;break;case 7:DestroyStack(S);printf("销毁栈\n");chose = 0;break;}printf("\n---------------------------------------------\n");printf("请选择功能：\n1：入栈 2：出栈3：判空4：读取栈顶元素 5：遍历6:清空栈 7：销毁栈\n");}return 0;}