栈（Stack）顺序栈以及链栈的相关操作（C语言）

一、栈（Stack）

（一）、定义

1. 栈的定义

• 线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为
• L = (a₁，a₂，…，a_i，a_i+1，…，a_n)
• 栈（Stack）是只允许在一端进行插入或删除操作的线性表。
  
  
• 特点：后进先出
• Last In First Out（LIFO）

2. 基本操作

• InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
• DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
• Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
• Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。【删除栈顶元素】
• GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素【不删除栈顶元素】
• StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false。

3. 栈的常考题型

• 进栈顺序：a -> b -> c -> d -> e，有哪些合法的出栈顺序？
  

二、顺序栈

（一）、定义

• 概念：用顺序存储方式实现的栈。
• 代码实现栈的定义

#define MaxSize 10			//定义栈中元素的最大个数
typedef struct{
   
	ElemType data[MaxSize];	//静态数组存放栈中元素
	int top;				//栈顶指针
}SqStack;

void testStack(){
   
	SqStack S;	//声明一个顺序栈（分配空间）
	//...后继操作...
}

• 顺序存储：给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)

（二）、基本操作

（1）InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。

//初始化栈
void InitStack(SqStack &S){
   
	S.top = -1;		//初始化栈顶指针
}

（2）DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。

• 让top=-1，然后由于我们是声明栈时分配内存空间，而不是使用malloc函数，因此函数运行结束后相系统自动回收内存。

（3）Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。

//新元素入栈
bool Push(SqStack &S, ElemType x){
   
	if(S.top == MaxSize-1)		//栈满，报错
		return false;
	S.top = S.top + 1;			//指针先加1
	S.data[S.top] = x;			//新元素入栈
	return true;
}

• 注意：下面图片为初始化栈时，S.top = -1时，下面图片的情况才正确
  
• 注意：下面图片为初始化栈时，S.top = 0 时，下面图片的情况才正确
  

（4）Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。【删除栈顶元素】

//出栈操作
bool Pop(SqStack &S, ElemType &x){
   //👉变量x加了引用符号，所以在出栈里面操作的变量x和函数的调用者定义的变量x对应的是同一份数据，而不是复制品。
	if(S.top == -1)		//栈空，报错
		return false;
	x = S.data[S.top];	//栈顶元素先出栈
	S.top = S.top - 1;	//指针再减1
	return true;
}

• 数据还残留在内存中，只是逻辑上被删除了
• 注意：下面图片为初始化栈时，S.top = -1时，下面图片的情况才正确
  
• 注意：下面图片为初始化栈时，S.top = 0 时，下面图片的情况才正确
  

（5）GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素【不删除栈顶元素】

//读取栈顶元素
bool GetTop(SqStack S, ElemType &x){
   
	if(S.top == -1)		//栈空，报错
		return false;
	x = S.data[S.top];	//x记录栈顶元素
		return true;
}

（6）StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false。

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

（三）、共享栈

• 定义：两个栈共享同一片空间。
• 栈满的条件：top0 + 1 == top1
  

#define MaxSize 10			//定义栈中元素的最大个数
typedef struct{
   
	ElemType data[MaxSize];	//静态数组存放栈中元素
	int top0;				//0号栈栈顶指针
	int top1;				//1号栈栈顶指针
}ShStack;

//初始化栈
void InitStack(ShStack &S){
   
	S.top0 = -1;			//初始化栈顶指针
	S.top1 = MaxSize;
}

三、链栈

（一）定义

• 概念：用链式存储方式实现的栈。
• 链栈的定义

typedef struct Linknode{
   
	ElemType data;			//数据域
	struct Linknode *next;	//指针域
}*LiStack;					//栈类型定义

• 相当于单链表的删除操作（只是只能在链表的一端进行删除或者添加操作）
  

转载：https://blog.csdn.net/qq_44096670/article/details/116459064