03-3.1.2 栈的顺序存储的实现

• 👋 Hi, I’m @Beast Cheng
• 👀 I’m interested in photography, hiking, landscape…
• 🌱 I’m currently learning python, javascript, kotlin…
• 📫 How to reach me --> 458290771@qq.com

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏和《程序员必备工具》专栏（该专栏暂未开设）日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

用顺序存储方式实现的栈

顺序栈的定义

回顾顺序存储的定义[[2.2.1 顺序表的定义#^28be66]]

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

基本操作

创（初始化）

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

增（进栈）

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.data[++S.top] = x;

删（出栈）

bool Pop(SqStack &S, ElemType &x){
	if(S.top == -1)     //栈空，报错
		return false;
	x = S.data[S.top];  //栈顶元素先出栈
	S.top = S.top - 1;  //指针再-1
	return true;
}

//和入栈操作类似，出栈操作这两句可以等价为：
x = S.data[S.top--];

查（获取栈顶元素）

x = S.data[S.top - 1];

判空、判满

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

另一种方式

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

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

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

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

共享栈

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

判断共享栈栈满的条件：
top0 + 1 == top1