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;     //指针先加 1S.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;  //指针再-1return 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;  //栈空elsereturn 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