[数据结构与算法]栈的基本操作

前言：最近复习数据结构，回归C++的怀抱~

代码环境：

Dev-C++ 5.11

定义：

/* 栈 */ 
typedef struct{
	ElemType data[MaxSize];
	int top;
}SqStack;

/* 共享栈 */ 
typedef struct{
	ElemType data[MaxSize];
	int top[2];
}SqShareStack;

基本操作的实现：

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

void InitShareStack(SqShareStack &ShareS){
	ShareS.top[0] = -1;
	ShareS.top[1] = MaxSize;
} 

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

//进栈
bool Push(SqStack &S , ElemType x){
	if(S.top == MaxSize-1){
		return false;
	} 
	S.data[++S.top] = x;
	return true;
} 

/* 共享栈进栈 */ 
int PushShare(SqShareStack &ShareS , int i , ElemType x){
	if(i < 0 || i > 1){
		cout << "不存在这个栈" << endl;
		exit(0); 
	}
	if( (ShareS.top[1]-ShareS.top[0]) == 1){
		cout << "栈已满" <<endl;
		return false;
	}
	
	switch(i){
		case 0: 
		ShareS.data[++ShareS.top[0]]=x; return 1;
		    break;
		case 1: 
		ShareS.data[--ShareS.top[1]]=x; return 1;
	}
}

//出栈
bool Pop(SqStack &S, ElemType &x){
	if(S.top == -1){
		return false;
	}
	x = S.data[S.top--];
	return true;
} 

/* 共享栈出栈 */ 
int PopShare(SqShareStack &ShareS , int i){
	if( i < 0 || i > 1){
		cout << "栈号输入错误" << endl; 
	} 
	switch(i){
		case 0:
			if(ShareS.top[0] == -1){
				cout << "0号栈空" << endl;
				return false; 
			}
			else{
				return ShareS.data[ShareS.top[0]--];
			}
		case 1:
			if(ShareS.top[1] == MaxSize){
				cout << "1号栈空" << endl;
				return false; 
			}
			else{
				return ShareS.data[ShareS.top[1]++];
			}
	}
}

//栈顶元素
int  Gettop(SqStack &S, ElemType &x){
	if(S.top == -1){
		return false;
	}
	x = S.data[S.top];
	return x;
} 

//建栈
void CreateStack(SqStack &S){
	int val;
	cout << "请输入元素值" <<endl;
	while( (cin >> val) && ( val != -1) ){
		Push(S, val);
	}
} 

void CreateShareStack(SqShareStack &ShareS){
	int stacktop;
	cout << "请选择需要建的栈:";   cin>>stacktop; 
	cout << "请输入元素值(输入“-1”结束进栈)："; 
	int val; 
	while( (cin >> val) && ( val != -1)){
		PushShare(ShareS , stacktop , val);
	}
}

//栈遍历
void TravelStack(SqStack &S){
	while( S.top != -1){
		cout<< S.data[S.top]<<" ";
		S.top--; 
	} 
	cout<<endl;
} 

void TravelSqSharkStack(SqShareStack &ShareS , int stacktop){
	if(stacktop == 0){
		if(ShareS.top[0] == -1){
			cout<<"0号栈为空"<<endl; 
		}
		while (ShareS.top[0] != -1)
		{
			cout<<ShareS.data[ShareS.top[0]] <<" ";
			ShareS.top[0]--;
		}
		cout<<endl;
	}
	else{
		if(ShareS.top[1] == MaxSize){
			cout<<"1号栈为空"<<endl; 
		}
		while(ShareS.top[1] != MaxSize)
		{
			cout<<ShareS.data[ShareS.top[1]] <<" ";
			ShareS.top[1]++;
		}
		cout<<endl;
	}
	
}

//栈长度 
int GetSize(SqStack &S)
{
	int len=0;
	len =  S.top+1;
	return len;
}

完整代码：

#include<iostream>
#define MaxSize 50
using namespace std;

//元素类型 
typedef int ElemType; 

/* 栈 */ 
typedef struct{
	ElemType data[MaxSize];
	int top;
}SqStack;

/* 共享栈 */ 
typedef struct{
	ElemType data[MaxSize];
	int top[2];
}SqShareStack;


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

void InitShareStack(SqShareStack &ShareS){
	ShareS.top[0] = -1;
	ShareS.top[1] = MaxSize;
} 

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

//进栈
bool Push(SqStack &S , ElemType x){
	if(S.top == MaxSize-1){
		return false;
	} 
	S.data[++S.top] = x;
	return true;
} 

/* 共享栈进栈 */ 
int PushShare(SqShareStack &ShareS , int i , ElemType x){
	if(i < 0 || i > 1){
		cout << "不存在这个栈" << endl;
		exit(0); 
	}
	if( (ShareS.top[1]-ShareS.top[0]) == 1){
		cout << "栈已满" <<endl;
		return false;
	}
	
	switch(i){
		case 0: 
		ShareS.data[++ShareS.top[0]]=x; return 1;
		    break;
		case 1: 
		ShareS.data[--ShareS.top[1]]=x; return 1;
	}
}

//出栈
bool Pop(SqStack &S, ElemType &x){
	if(S.top == -1){
		return false;
	}
	x = S.data[S.top--];
	return true;
} 

/* 共享栈出栈 */ 
int PopShare(SqShareStack &ShareS , int i){
	if( i < 0 || i > 1){
		cout << "栈号输入错误" << endl; 
	} 
	switch(i){
		case 0:
			if(ShareS.top[0] == -1){
				cout << "0号栈空" << endl;
				return false; 
			}
			else{
				return ShareS.data[ShareS.top[0]--];
			}
		case 1:
			if(ShareS.top[1] == MaxSize){
				cout << "1号栈空" << endl;
				return false; 
			}
			else{
				return ShareS.data[ShareS.top[1]++];
			}
	}
}

//栈顶元素
int  Gettop(SqStack &S, ElemType &x){
	if(S.top == -1){
		return false;
	}
	x = S.data[S.top];
	return x;
} 

//建栈
void CreateStack(SqStack &S){
	int val;
	cout << "请输入元素值" <<endl;
	while( (cin >> val) && ( val != -1) ){
		Push(S, val);
	}
} 

void CreateShareStack(SqShareStack &ShareS){
	int stacktop;
	cout << "请选择需要建的栈:";   cin>>stacktop; 
	cout << "请输入元素值(输入“-1”结束进栈)："; 
	int val; 
	while( (cin >> val) && ( val != -1)){
		PushShare(ShareS , stacktop , val);
	}
}

//栈遍历
void TravelStack(SqStack &S){
	while( S.top != -1){
		cout<< S.data[S.top]<<" ";
		S.top--; 
	} 
	cout<<endl;
} 

void TravelSqSharkStack(SqShareStack &ShareS , int stacktop){
	if(stacktop == 0){
		if(ShareS.top[0] == -1){
			cout<<"0号栈为空"<<endl; 
		}
		while (ShareS.top[0] != -1)
		{
			cout<<ShareS.data[ShareS.top[0]] <<" ";
			ShareS.top[0]--;
		}
		cout<<endl;
	}
	else{
		if(ShareS.top[1] == MaxSize){
			cout<<"1号栈为空"<<endl; 
		}
		while(ShareS.top[1] != MaxSize)
		{
			cout<<ShareS.data[ShareS.top[1]] <<" ";
			ShareS.top[1]++;
		}
		cout<<endl;
	}
	
}

//栈长度 
int GetSize(SqStack &S)
{
	int len=0;
	len =  S.top+1;
	return len;
}



int main()
{
	SqStack S;  SqShareStack ShareS;
	int i=0; int x=0; 
	InitStack(S);
	InitShareStack(ShareS);
	cout << "【1】 创建栈(输入“-1”结束) 【2】 遍历栈        【3】 获取栈长度      【4】 判断栈是否为空"<<endl; 
	cout << "【5】 获取栈顶元素           【6】 创建共享栈    【7】 遍历共享栈      【0】 退出"<<endl;
	do
	{
		cout << "请输入要执行的操作: ";
		cin >> i;
		switch (i)
		{
		case 1:
			CreateStack(S);
			break;
		case 2:
			TravelStack(S);
			break;
		case 3:
			cout << "该栈的长度为" << GetSize(S) << endl;
			break;
		case 4:
			if (StackEmpty(S))
				cout << "该栈为空" << endl;
			else
			{
				cout << "该栈不为空" << endl;
			}
			break;
		case 5:
			cout << "栈顶元素的值为" << Gettop(S,x) << endl;
			break;
		case 6:
		    CreateShareStack(ShareS);
		    break;
		case 7:
			int stacktop; 
		    cout << "请输入想遍历的栈号：" ; cin >> stacktop;
		    TravelSqSharkStack(ShareS ,stacktop);
		default:
			break;
		}
	}while (i != 0);
}

运行结果：

• 实现都只是个人的见解，欢迎大家批评指正！