数据结构-顺序栈的基本操作(C语言实现)

  行业动态     |      2024-01-21 11:04

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

(此贴为博主学习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 
#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-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;
}