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

（此贴为博主学习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-1
return 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 <stdio.h>
#include <stdlib.h>
 
 
/**********************************************
制作人：祝星。
项目名称：数据结构-顺序栈的基本操作（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-1
return 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");
}else
printf("栈不为空\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;
}