【数据结构】-共享栈

布满荆棘的人生 2023-02-28 04:25 12阅读 0赞

### 共享栈 ###

*  共享栈示意图
 *  1.头文件及类型定义
 *  2.共享栈类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 初始化共享栈
     *  4.2 1号栈判空
     *  4.3 2号栈判空
     *  4.4 1号栈入栈
     *  4.5 2号栈入栈
     *  4.6 1号栈出栈
     *  4.7 2号栈出栈
     *  4.8 1号栈读取栈顶元素
     *  4.9 2号栈读取栈顶元素
     *  4.10 main函数
 *  5.小结

# 共享栈示意图 #

![共享栈][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center]

# 1.头文件及类型定义 #

#include<stdio.h>
    #define MaxSize 10				//定义共享栈中元素的最大个数
    #define ElemType int

# 2.共享栈类型定义 #

typedef struct {
        
    	ElemType data[MaxSize];		//静态数组存放栈中元素
    	int top1;					//1号栈栈顶指针
    	int top2;					//2号栈栈顶指针
    }ShStack;

# 3.函数声明 #

/*函数声明*/
    void InitShStack(ShStack& S);				//1.初始化共享栈
    bool Stack1Empty(ShStack S);				//2. 1号栈判空
    bool Stack2Empty(ShStack S);				//2. 2号栈判空
    bool Push1(ShStack& S, ElemType x);			//3. 1号栈入栈
    bool Push2(ShStack& S, ElemType x);			//4. 2号栈入栈
    bool Pop1(ShStack& S, ElemType& x);			//5. 1号栈出栈
    bool Pop2(ShStack& S, ElemType& x);			//6. 2号栈出栈
    bool GetTop1(ShStack S, ElemType& x);		//7. 1号栈读取栈顶元素
    bool GetTop2(ShStack S, ElemType& x);		//8. 2号栈读取栈顶元素

# 4.基本操作 #

## 4.1 初始化共享栈 ##

//1.初始化共享栈
    void InitShStack(ShStack& S) {
        
    	S.top1 = -1;		//初始化1号栈栈顶指针
    	S.top2 = MaxSize;	//初始化2号栈栈顶指针
    }

## 4.2 1号栈判空 ##

//2. 1号栈判空
    bool Stack1Empty(ShStack S) {
        
    	return (S.top1 == -1);
    }

## 4.3 2号栈判空 ##

//2. 2号栈判空
    bool Stack2Empty(ShStack S) {
        
    	return (S.top2 == MaxSize);
    }

## 4.4 1号栈入栈 ##

//4. 1号栈入栈操作：新元素入栈(先存再加)
    bool Push1(ShStack& S, ElemType x) {
        
    	if (S.top1+1 == S.top2)		//栈满，报错
    		return false;
    	S.data[++S.top1] = x;
    	return true;
    }

## 4.5 2号栈入栈 ##

//5. 2号栈入栈操作：新元素入栈(先存再加)
    bool Push2(ShStack& S, ElemType x) {
        
    	if (S.top1 + 1 == S.top2)		//栈满，报错
    		return false;
    	S.data[--S.top2] = x;
    	return true;
    }

## 4.6 1号栈出栈 ##

//6. 1号栈出栈操作：栈顶元素出栈
    bool Pop1(ShStack& S, ElemType& x) {
        
    	if (S.top1 == -1)	//1号栈栈空，报错
    		return false;
    	x = S.data[S.top1--];	
    	return true;
    }

## 4.7 2号栈出栈 ##

//7. 2号栈出栈操作：栈顶元素出栈
    bool Pop2(ShStack& S, ElemType& x) {
        
    	if (S.top2 == MaxSize)	//2号栈栈空，报错
    		return false;	
    	x = S.data[S.top2++];
    	return true;
    }

## 4.8 1号栈读取栈顶元素 ##

//8. 1号栈读取栈顶元素操作
    bool GetTop1(ShStack S, ElemType& x) {
        
    	if (S.top1 == -1)	//1号栈栈空，报错
    		return false;
    	x = S.data[S.top1];
    	return true;
    }

## 4.9 2号栈读取栈顶元素 ##

//9. 2号栈读取栈顶元素操作
    bool GetTop2(ShStack S, ElemType& x) {
        
    	if (S.top2 == MaxSize)	//2号栈栈空，报错
    		return false;
    	x = S.data[S.top2];
    	return true;
    }

## 4.10 main函数 ##

int main() {
        
    	ShStack S;		//声明一个共享栈(分配内存空间)
    
    	/*1、初始化共享栈*/
    	InitShStack(S);
    
    	/*2、1号栈-判空*/
    	if (Stack1Empty(S))
    		printf("当前1号栈空！\n");
    	else
    		printf("当前1号栈非空！\n");
    
    	/*3、1号栈-入栈操作*/
    	ElemType e1;
    	printf("请输入1号栈入栈元素的值：");
    	scanf("%d", &e1);
    	if (Push1(S, e1))
    		printf("1号栈新元素入栈成功！\n");
    	else
    		printf("共享栈已满,1号栈新元素入栈失败！\n");
    
    	/*4、1号栈-读取栈顶元素*/
    	ElemType e2 = -1;
    	if (GetTop1(S, e2))
    		printf("1号栈读取栈顶元素成功，当前栈顶元素值为：%d\n", e2);
    	else
    		printf("1号栈已空，读取栈顶元素失败！\n");
    
    	/*5、1号栈-出栈操作*/
    	ElemType e3 = -1;
    	if (Pop1(S, e3))
    		printf("1号栈栈顶元素出栈成功，出栈元素值为：%d\n", e3);
    	else
    		printf("1号栈已空，栈顶元素出栈失败！\n");
    
    	/*6、1号栈-读取栈顶元素*/
    	ElemType e4 = -1;
    	if (GetTop1(S, e4))
    		printf("1号栈读取栈顶元素成功，当前栈顶元素值为：%d\n", e4);
    	else
    		printf("1号栈已空，读取栈顶元素失败！\n");
    
    	/*7、2号栈-判空*/
    	if (Stack2Empty(S))
    		printf("当前2号栈空！\n");
    	else
    		printf("当前2号栈非空！\n");
    
    	/*8、2号栈-入栈操作*/
    	ElemType e21;
    	printf("请输入2号栈入栈元素的值：");
    	scanf("%d", &e21);
    	if (Push2(S, e21))
    		printf("2号栈新元素入栈成功！\n");
    	else
    		printf("共享栈已满,2号栈新元素入栈失败！\n");
    
    	/*9、2号栈-读取栈顶元素*/
    	ElemType e22 = -1;
    	if (GetTop2(S, e22))
    		printf("2号栈读取栈顶元素成功，当前栈顶元素值为：%d\n", e22);
    	else
    		printf("2号栈已空，读取栈顶元素失败！\n");
    
    	/*10、2号栈-出栈操作*/
    	ElemType e23 = -1;
    	if (Pop2(S, e23))
    		printf("2号栈栈顶元素出栈成功，出栈元素值为：%d\n", e23);
    	else
    		printf("2号栈已空，栈顶元素出栈失败！\n");
    
    	/*11、2号栈-读取栈顶元素*/
    	ElemType e24 = -1;
    	if (GetTop2(S, e24))
    		printf("2号栈读取栈顶元素成功，当前栈顶元素值为：%d\n", e24);
    	else
    		printf("2号栈已空，读取栈顶元素失败！\n");
    	return 0;
    }

# 5.小结 #

1.  **共享栈的定义**  
    共享栈是逻辑上实现了两个栈，但物理上这两个栈共享同一片内存空间。因此在进行判空操作时，两个栈分别进行判断，但在判满时要判断整个共享栈的存储情况。
2.  **说明**  
    共享栈的实现与顺序栈的实现大同小异，它们都属于栈的顺序存储，只需要注意在栈顶指针处别犯错就可以。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/ae9456a48cbc4b0a97aa7c387fd3ca0a.png