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

（此贴为博主学习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


typedef struct SqStack{
	int data[MaxSize];//存放栈元素
	int top;	//栈顶指针
}SqStack;

2. 栈判空        

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

功能演示

 

3.初始化一个栈

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 




#define MaxSize 10


typedef struct SqStack{
	int data[MaxSize];//存放栈元素
	int top;	//栈顶指针
}SqStack;


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


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;
}