【严蔚敏版数据结构】你分得清顺序栈和链栈吗

一、顺序栈和链栈的存储结构

顺序栈的存储结构图如下：

由图可知，顺序栈是由两个指针，即栈顶top指针、栈底base指针来掌控大局的。同时，还有栈长度stacksize这个辅助。

因此，顺序栈的结构体定义如下：

type struct {// 栈顶top指针、栈底base指针SElemType *top;SElemType *base;// 栈长度stacksizeint stacksize;
}SqStack;

明明已经有栈顶top指针、栈底base指针分别指着栈的栈底首元素和栈顶末元素了，为什么还需要栈长度stacksize呢？

因为只有根据栈长度stacksize，我们才能晓得整个顺序栈的总长度是多少，不至于出现上溢（栈满了，你特么还往里头塞新的元素）或下溢（栈空了，你还傻乎乎的想要继续弹出元素）的风险。

而，链栈的存储结构图如下：

看到没，链栈只有一个头指针S，而且这个头指针一直指向栈顶的元素。它就像监狱长，永远站在队伍的最末端，盯着最后一个新来的元素。

链栈每个节点都有两部分，一是存储数据的data部分，一是指向前一个元素的指针*next部分。

因此链栈的结构体定义如下：

// 定义结构体
typedef struct StackNode {// data部分和指针部分SElemType data;struct StackNode *next;
}StackNode, *LinkStack;// 这个就是头指针大哥。
LinkStack S;

二、顺序栈和链栈的初始化

好，既然有了结构体，那么就可以初始化了。

顺序栈说白了，就是一个数组，既然是数组，就得在最开头分配内存空间了。（分配好内存后，栈底指针就不为空了）

由于新创建好的顺序栈，里头是没有任何一个元素的，因此，栈顶指针top和栈底指针base挨在一起腻歪。

与此同时，这个顺序栈的栈长度stacksize已经领下圣旨，获得了它的长度。

// 初始化
Status InitStack(SqStack &S) {// 分配内存 S.base = new SElemType[MAXSIZE];// 判断是否栈底为空，！S.base表示为空 if(!S.base) exit(OVERFLOW); S.top = S.base;S.stacksize = MAXSIZE;return OK;
}

那么，链栈呢？

链栈是可以无止尽的新增新元素的，所以它的内存空间不能在一开始就确定好。（只能在每次一压栈（塞入新元素）时，才立刻给它安排个内存空间）

同样的，新创建好的链栈也是没有任何一个元素的，头指针大哥S只能百无聊赖的盯着一片虚无。

// 初始化
Status InitStack(LinkStack &S) {S = NULL;return OK; 
}

三、顺序栈和链栈的判断是否栈空

栈空，顾名思义，就是里面没有任何一个元素。

对于顺序栈来说，栈空，就意味着栈顶指针top和栈底指针base腻歪，

// 判断是否栈空
Status EmptyStack(SqStack S) {if(S.top == S.base)return TRUE;elsereturn ERROR;
}

对于链栈来说，栈空，就意味着头指针大哥S百无聊赖的盯着一片虚无。

// 判断是否栈空
Status EmptyStack(LinkStack S) {if(S == NULL) return TRUE;else return FALSE;
}

四、顺序栈和链栈的入栈

梦里寻他千百度，蓦然回首，那元素却在灯火阑珊处。

很快，顺序栈迎来了它的一个新元素。

栈顶指针top骂骂咧咧，走到上一层的楼房，把原来待着的好位置让给了新来的。

如果栈顶指针不断上移，直到它站在了整层楼的楼顶（达到栈长度stacksize的值），这说明栈满了，无法再进来新元素。

// 入栈 
Status PushStack(SqStack &S, SElemType e) {// 判断是否栈满if(S.top - S.base == S.stacksize) return ERROR;// 栈顶指针的内容更新为e，且往上增1 *S.top ++= e; return OK; 
}

链栈的头指针大哥S也是迎来它的新元素。

刚刚就在初始化的时候讲过了，链栈在初始化时不会先分配内存给元素，因此这里就要分配内存了。

这里需注意，对于栈顶最末元素来说，S->data存储着是它，S->next指向的是它的前一个节点。

// 入栈
Status PushStack(LinkStack &S, SElemType e) {// 动态分配内存p = new StackNode;p->data = e;p->next = S;S = p;return OK; 
}

五、顺序栈和链栈的弹栈

虽然有新元素进来，可是它可能萌生了想离开的想法，那么就得弹栈，把它除去了。

对于顺序栈来说，弹栈之前先检查一下是否空栈，免得尴尬。

然后，栈顶指针top往下走一个楼层，最末一个新来的元素出栈。

// 弹出栈顶元素 
Status PopStack(SqStack &S, SElemType &e) {// 判断是否栈空if(S.top == S.base) return ERROR;// S.top下移，出栈元素被赋值给了ee = *--S.top;return OK; 
}

链栈在出栈之前，同样需要检查是否空栈。

临时一个节点代替头指针大哥S，等待头指针大哥S重新盯梢出栈元素的前一位元素之后，它就被删除了（释放内存）。

要出栈的元素从它所处节点的data部分被e带走了，头指针大哥S也重新盯梢出栈元素的前一位元素。

// 弹出栈顶元素 
Status PopStack(LinkStack &S, SElemType &e) {// 判断是否空栈if(S == NULL) return ERROR;p = S;e = S->data;	S = S->next;delete p;return OK; 
}

六、顺序栈和链栈的取栈顶元素

取栈顶元素之前，顺序栈和链栈同样都要检查是否空栈。

由于顺序栈的栈顶指针top永远站在栈顶元素的上一层，因此，要往下一层才能获得栈顶元素。

// 查询栈顶元素 
Status GetStackParm(SqStack S) {// 判断是否栈空if(S.top != S.base) // 因为栈顶指针永远在栈顶元素的上一位，因此要返回（S.top - 1）指针所指的内容 return *(S.top - 1);	 
}

链栈的头指针大哥S最喜欢的就是盯梢了，因此，在不空栈的情况下，直接返回它的data部分即可获得栈顶元素。

// 查询栈顶元素 
Status GetStackParm(LinkStack S) {if(S!=NULL)return S->data;
}