【数据结构】【线性表】栈的顺序存储实现(附C语言源码)
栈的顺序存储实现
在之前的内容中我们讲过，栈也是线性表的一种，它和顺序表以及链表的区别不在存储结构上，而是在删除和插入的操作上，栈只允许在其一端进行插入或删除的操作。因此栈的实现可以和顺序表类似，也可以和链表类似，在这里，我们先介绍一下栈的顺序存储实现。顺序存储顾名思义，内存空间练习，元素顺序和存储顺序一致。
顺序栈的定义
define MaxSize 10//定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize];//用数组存放各个元素，Elemtype表示任意数据类型
int top;//栈顶指针
}SqStack;
内存分别大致如图所示：
顺序栈的初始化
将顺序栈初始化为空栈，为了清除顺序栈中元素数据，可以先遍历将各元素的data设置成一个特定的值，并将栈顶指针设置为负数（因为非空栈的栈顶指针必定为非负数）
void InitStack(SqStack &S,ElemType e){
for(int i=0;i<MaxSize;i++){
S.data[i]=e;
}
S.top=-1;
}
进栈
新的元素进栈需要先判断栈是否满员，防止上溢；在栈有剩余空间的前提下，先将栈顶指针+1，然后将元素放入其中。
bool PushStack(SqStack &S,ElemType e){
if(S.top==MaxSize-1)//判断顺序栈是否满员
return flase;//顺序栈已满，进栈失败
S.top=S.top+1;//栈顶指针先+1
S.data[S.top]=e;//元素进栈
return true；//进栈成功
}
出栈
将元素出栈需要先判断栈是否为空栈，在不是空栈的情况下，先将元素出栈，然后栈顶指针-1.
bool PopStack(SqStack &S,ElemType &e){
if(S.top==-1)//判断是否空栈
return false;//空栈，出栈失败
e=S.data[S.top];//数据出栈
S.top=S.top-1;//栈顶指针-1
return true;//出栈成功
}
这里需要注意的是，顺序结构里的出栈，不会真正的删除该元素，元素数据还保留在原来的内存中，只是从逻辑上删除了，top相当于一个盖子，让栈不会越过盖子访问下一个内存，视为删除（出栈）
读栈顶元素
类似于出栈，不同的在于我只需要读出栈顶元素的数据内容，不需要改变其栈顶指针
bool ReadTop(SqStack &S,ElemType &e){
if(S.top==-1)//判断是否空栈
return false;//空栈，读栈顶元素栈失败
e=S.data[S.top];//读取栈顶数据
return true;//读栈顶成功
}
共享栈
两个栈共享一个空间，内存分布大致情况如图所示：
共享栈公用同一片连续空间，两端分别为各自的栈底，两个栈的栈顶向其共享空间延申。
其结构体构建为：
define MaxSize 10//定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize];//用数组存放各个元素，Elemtype表示任意数据类型
int top1;//栈顶指针1
int top2;//栈顶指针2
}SqStack;
我们在初始化时需要注意栈顶指针的赋值，应当分别赋值给两端;同时为了清除数据，也可以将内存中各个元素赋予一个特定的值e，例如e=0；
void InitStack(SqStack &S,ElemType e){
for(int i=0;i<MaxSize;i++){
S.data[i]=e;
}
S.top1=-1;
S.top2=MaxSize;
}
共享栈的入栈和出栈的方法思路和正常栈是一致的，但也有几点注意事项需要说明一下：
- 共享栈共享同一个空间，栈底不是固定不变的，当两个栈顶指针相邻时，说明满栈，如图所示：
满栈的判定条件为：top1==top2-1;
- 共享栈空栈则二者的top都为初始化的值：
top1=-1;
top2==MaxSize;
- 需要注意的是，满栈判定什么两个栈均已满，但空栈判定只说明单个栈是空栈，也可能存在一个栈是空栈，另一个栈是满栈，此时的空栈没有剩余空间了，也视为满栈。
原文地址：https://blog.csdn.net/weixin_58498967/article/details/143948258
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！