3.1.2_栈的顺序存储实现

知识总览：

顺序栈的定义：

顺序栈是用顺序存储实现的 ，代码定义方式和顺序表类似(啥是顺序表来着？？？)

定义一个顺序栈struct结构体SqStack，结构体中有静态数组data来存放栈里边的元素+1个int型的top指针用来指向栈顶元素(该指针一般记录的是栈顶元素的索引下标，data数组索引下标从0开始)，声明一个顺序栈SqStack S;后会在内存分配一块连续的内存空间(应该是因为是顺序存储)，空间大小为data数组中的每个元素所占空间大小*元素个数(MaxSize * sizeOf(ElemType))+top指针占用空间(int型的占4Byte)，比如说空间大小是10，依次压栈进入5个元素a、b、c、d、e，则现在top指向e元素的位置(不是指向没有元素的最上方)，即top=4(e的索引下标)

声明栈SqStack S：

此时栈里边data数组元素为空，即栈顶元素为空，则让top指针指向-1位置，而不是data[0]位置==》因此，判断栈空，就用S.top==-1即可

以下为S.top指针指向栈顶元素位置(即开始栈顶元素为空，则指向-1位置)====》现在时，和压栈元素同呼吸共命运

初始化栈：

让top指针指向-1位置，即S.top == -1;

进栈操作：

因为数组的长度是固定的，所以每次进栈前都要判断指向栈顶元素的top指针表示的索引位置==Maxsize-1，相等这表示要数组下标越界了，注意每次top指针指向的索引位置都是要进来的元素位置，所以每次进栈的时候都要让当前的top+1先操作，再把元素放到top+1位置，即让top先挪位置，再把元素放进来，++top前++，先自身+1再执行操作

出栈操作：

出栈前先判断栈里边还有没有元素即判断栈是否空，有元素才出栈，即用S.top==-1判断，出栈要把出栈元素返回用引用X返回，出栈时只是把数组里的元素逻辑上删除了，但是该元素还依然存在内存(因为该元素用X返回了)，出栈时先把该元素出栈再让S.top-1，即先让当前栈顶元素腾地出去赋值给X，再让栈顶元素指针下移，先操作再自身-1，S.top--

读栈顶元素操作：

和上边出栈类似，只是没有S.top指针下移，只是把栈顶元素返回，栈顶元素依然不变

以下为栈顶指针指向下一个元素可以插入的位置(即开始栈为空，下一个元素要插入的位置是0，即让栈顶指针指向0位置)===》未来式，等待式，即栈顶指向的位置肯定是没值的：

故判断栈空用S.top==0，进栈时判断栈满用S.top==MaxSize，出栈时栈空用S.top==0，出栈时先S.top-1先把指针下移指向要出栈的元素位置

回收栈：即让栈顶指针指向-1，即让栈空即可，然后内存中的空间自动回收，不用使用malloc函数

缺点：顺序栈是用静态数组存储实现的，静态数组长度固定，导致栈的大小不可改变，可以用链式存储的方式实现改变缺点，也可以开始申请一大片连续的内存空间，但是申请了不用又浪费，

共享栈：

2个栈共用一片连续的内存空间，解决申请一大片连续内存空间浪费的情况

2个栈有2个栈顶指针，开始2个栈都为空，0号栈栈顶指针指向-1,1号栈栈顶指针指向MaxSize【即2个栈顶指针用的都是现在式，要入栈的话，0号栈先top+1,1号栈先top-1】，即0号栈入栈从下往上走，1号栈入栈从上往下走，当0号栈的S.top+1==1号栈的S.top，或者1号栈的S.top-1==0号栈的S.top证明共享栈已满，2个栈物理上共用一块连续空间

 

知识回顾：

 

 。。。。。。。。。