前言
废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~
资料获取
4.4栈的顺序存储结构及实现
4.4.1栈的顺序存储结构
既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，简称为顺序栈。线性表是用数组来实现的，想想看，对于栈这种只能一头插入删除的线性表来说，用数组哪一端来作为栈顶和栈底比较好?
对，没错，下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。
我们定义一个top变量来指示栈顶元素在数组中的位置，这top就如同中学物理学过的游标卡尺的游标，它可以来回移动，意味着栈顶的top 可以变大变小，但无论如何游标不能超出尺的长度。同理，若存储栈的长度为StackSize, 则栈顶位置top必须小于StackSize。 当栈存在一个元素时，top 等于0,因此通常把空栈的判定条件定为top等于-1。
typedef int SElemType; /* SElemType 类型根据实际情况而定，这里假设为int */ typedef struct { SElemType data[MAXSIZE]; int top; /*用于栈顶指针*/ } SqStack;
若现在有一个栈，StackSize 是5,则栈普通情况、空栈和栈满的情况示意图
4.4.2栈的顺序存储结构--进栈操作
对于栈的插入，即进栈操作，其实就是做了下面的处理
/*插入元素e为新的栈顶元素*/ Status Push ( SqStack *S, SElemType e) { if (S->top == MAXSIZE -1) //栈满 { return ERROR; } s->top++; /*栈顶指针增加一/ S->data[S->top]=e; /*将新插入元素赋值给栈顶空间,将To*/ return OK; }
4.4.3栈的顺序存储结构--出栈操作
/*插入元素e为新的栈顶元素*/ Status Push ( SqStack *S, SElemType e) { if (S->top -- MAXSIZE -1) //栈满 { return ERROR; } *e = s->data[s->top] /*将要删除的栈顶元素赋值给e*/ s->top--; /*栈顶指针减一/ return OK; }
两者没有涉及到任何循环语句，因此时间复杂度均是o(1)
4.5 两栈共享空间
其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表 插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。对于一个栈，我们也只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。
做法如图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素,就是两端点向中间延伸。
其实关键思路是:它们是在数组的两端，向中间靠拢。top1 和top2是栈1和栈2的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。
从这里也就可以分析出来，栈1为空时，就是top1等于-1时;而当top2等于n时，即是栈2为空时，那什么时候栈满呢?
想想极端的情况，若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2 等于0时，为栈2满。但更多的情况，其实就是刚才说的，两个栈见面之时，也就是两个指针之间相差1时，即top1 + 1 == top2 为栈
代码实现如下：
typedef struct StackNode { SElemType data; struct StackNode *next; }StackNode, *LinkStackPtr; typedef struct LinkStack { LinkStackPtr top; int count; } LinkStack;
对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下:
/*插入元素e为新的栈顶元素*/ Status Push ( SqDoubleStack *S, SElemType e,int stackNumber ) { if(s->top1+1==s->top2) /*栈已满，不能再push新元素了*/ return ERROR; if ( stackNumber==1 ) /*栈1有元素进栈*/ S->data[++S->top1]=e; /*若栈1则先top1+1后给数组元素赋值*/ else if ( stackNumber==2) /*栈2有元素进栈*/ S->data[--s->top2]=e;/*若栈2则先top2-1后给数组元素赋值*/ return OK; }
因为在开始已经判断了是否有栈满的情况，所以后面的top1+1或top2-1是不担 心溢出问题的。
对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber,
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR */ Status Pop ( SqDoubleStack *S, SElemType *e, int stackNumber ) { if( stackNumber==1 ) { if (s->top1==-1) return ERROR; /*说明栈1已经是空栈，溢出*/ *e=S->data[s->top1--]; /*将栈1的栈顶元素出栈*/ } else↓if( stackNumber==2 ) { if(s->top2==MAXSIZE ) return ERROR; /*说明栈2已经是空栈，溢出*/ *e=S->data[s->top2++]; /* 将栈2的栈顶元素出栈*/ } return OK; }
