数据结构与算法学习笔记（C语言）
栈
1.定义：栈是仅限在表尾进行插入和删除操作的线性表
其实，根据定义，我们已经就能自己按照之前实现线性表的代码来实现栈了，栈是一种特殊的线性表，不过是对插入和删除操作加了位置限制罢了
既然我们都能完成线性表的各种操作了，有些人可能就会问了，还要栈来干什么呢？
继续往下学，就能得到这个问题的答案了！而且我们由定义知道，栈会比线性表学起来更加简单，事实也是如此
栈的特征：后进先出（LIFO：last in first out），最后进去的最先出来。
现实生活中，有很多事物是符合这个特征的，比如一桶羽毛球，最先拿出来的肯定是最上面的那个，而在厂家包装时，它恰巧是最后放进去的。
再比如，浏览器的回退按钮，我们点击一下，回退到刚刚的页面，再次点击会回退到之前的页面，最后回退到的是最早打开的页面。这种设计就是用的LIFO的原则。
我们把允许插入和删除的一端称为栈顶，另一端成为栈底，把不含任何数据元素的栈称为空栈。
栈的插入操作叫做进栈，也叫压栈（push）；栈的删除操作叫做出栈，也叫弹栈（pop）
2.栈的抽象数据类型
ADT Stack {
数据对象：D = {a1, a2, a3, ...}
数据关系：R = {<a1, a2>, <a2,a3>, ...}
/*可见栈的数据关系和线性表是一样的，本来栈就是线性表，只不过基本操作约定在栈顶*/
/*约定a1端为栈底，an端为栈顶*/
基本操作：
InitList(*S)
/*初始化操作，构建一个空栈*/
ClearList(*S)
/*将一个栈的元素清空*/
DestroyList(*S)
/*销毁栈*/
GetTop(S, *e)
/*用e返回栈顶元素的值*/
Push(*S, e)
/*将e插入栈顶*/
Pop(*S, *e)
/*弹出栈顶元素，用e接收*/
StackTraverse(S)
/*遍历栈中的数据元素*/
}ADT Stack
由上面的基本操作的定义可以知道，这就是线性表基本操作的简化版啊，对于线性表的，我们要能获取第 i 位的元素值，现在只需要获取栈顶的元素值，线性表中，我们要能在任何有效的 i 位置插入或者删除元素，现在呢，只需要在栈顶插入删除元素就行了，是不是简单了很多！
3.栈的表示和实现
和线性表类似，栈也有两种存储表示方法：顺序栈和链栈。
顺序栈是用地址连续的存储空间，依次存储栈从栈底到栈顶的元素。
如上图所示，base是连续地址空间的基地址，当栈空时，让top指针指向基址，当元素插入时，top指针指向下一个内存单元，当栈满时，top指针指向动态数组空间的下一个单元！
这时大家肯定会问，你是不是搞错了，在学习指针和数组的时候，一直在强调，指针不能越界，不能越界，不能越界！
很多人可能持有怀疑态度，包括我在内也是，起初非常迷惑，就在网上搜索，搜索到的大多是指针和数组的关系啦等等一些自己都知道的信息，后来，直到一位好兄弟给出了 普拉达所著的《C Primer Plus(第六版)中文版》 中第297页的一句话，让我放心了
“C只能保证指向数组后面的第一个位置的指针有效”
这就是一支强心剂啊，大佬说能保证了就肯定没差了，我虽然知道系统分配的空间实际上要比指针所申请的空间大一点，但是不确定是不是能大一个存储单元，有了这句话，就能递增指针到数组空间的下一个单元了，这样就不需要留空一个申请的存储单元来判断栈满了，就能实现真正的栈满！
另外补充一句，别因为知道指针能指向数组空间的下一个单元就去操作那个单元，违反公序良俗！
下面就给出顺序栈的C语言描述
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10 //存储空间分配增量
typedef struct {
SElemtype *base; //存储空间基址
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间
}SqStack;
基本操作的函数原型说明
Status InitStack(SqStack *S);
/*构造一个空栈*/
Status DestroyStack(SqStack *S);
/*销毁栈S*/
Status ClearStack(SqStack *S);
/*清空栈*/
int StackLength(SqStack S);
/*返回S的元素个数*/
Status GetTop(SqStack S, SElemType *e);
/*返回栈顶元素*/
Status Push(SqStack *S, SElemType e);
/*将元素插入栈顶*/
Status Pop(SqStack *S, SElemType *e);
/*将栈顶元素弹出*/
Status Traverse(SqStack S);
/*遍历栈中的元素*/
下面对上面定义的函数原型进行实现
1.初始化一个栈
Status InitStack(SqStack *S)
{
S->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType));
if (!S->base) exit(OVERFLOW);
S->top = S->base;
S->stacksize = INIT_SIZE;
return OK;
}
2.获取栈顶元素
Status GetTop(SqStack S, SElemType *e)
{
if (S.top == S.base) return ERROR;
/*栈空*/
*e = *(S.top - 1);
return OK;
}
3.插入元素为新的栈顶元素
Status Push(SqStack *S, SElemType e)
{
/*如果栈满*/
if (S->top - S->base == S.stacksize) {
/*这里涉及指针相减，在连续空间上，指针相减得到存储单元的个数，是int型，
有疑问的翻下书再复习一下指针部分*/
SElemType *new_base;
new_base = (SElemType *)realloc(S->base, (S->stacksize + INCREMENT) * sizeof(SElemType));
if(!newbase) exit(OVERFLOW);
/*将栈底和栈顶指针移到新动到的存储空间来*/
S->base = new_base;
S->top = S->base + S->stacksize;
S->stacksize += INCREMENT;
}
*S->top++ = e;
return OK;
}
4.弹出栈顶元素
Status Pop(SqStack *S, SElemType *e)
{
if (S->top == S->base) return ERROR;
*e = *--S->top;
return OK;
}
5.返回栈里面元素的个数
int StackLength(SqStack S)
{
return S.top - S.base;
/*指针相减得连续空间的长度（以元素为单位）*/
}
6.遍历栈里面的元素
void StackTraverse(SqStack S)
{
int i;
for (i = 0; i < StackLength(S); i++)
printf("%c ", S.base[i]);
}
printf("\n");
}
7.清空栈
void ClearStack(SqStack *S)
{
S->top = S->base;
}
8.销毁栈
void DestroyStack(SqStack *S)
{
free(S->base);
/*释放内存*/
S->top = S->base = NULL;
/*改变指针指向*/
}
栈的顺序存储结构就是这么简单，毫无挑战性！那现在该回答一下为什么学习栈的问题了，为什么学习了线性表还要学习栈呢？
因为啊，栈的逻辑对于解决一些问题非常有帮助
我们通过栈这种逻辑结构，去解决比如括号匹配问题，文本编辑器中，经常要检查括号是不是匹配，我们每输入一个左括号 ( [ { 就把它压进栈里，每次输入一个右括号 ) ] }就取栈顶的左括号比对，是一对儿就弹出来，不是一对就可以打印警告语句 “括号不匹配！”，通过栈来思考括号问题非常清晰对不对，这就是栈的魅力！
自己动手尝试实现括号匹配的小程序吧，不然就由我代劳了，代码示例下一章给出
总结一下已经学过的东西：
1、数据结构与算法是什么东西
2、逻辑结构：线性表 和它的 存储结构：顺序表、链表
3、逻辑结构：栈 和它的一种 存储结构：顺序栈
那么下一章学习栈的另一种存储结构：链栈