目录
栈的介绍
一、栈的基本概念
1.1 栈的定义
1.2 栈的常见基本操作
二、栈的顺序存储结构
2.1 栈的顺序储存
2.2 顺序栈
2.3 共享栈
三、栈的链式储存结构
3.1 链栈
3.2 链栈的进出栈操作
四、栈的应用
4.1实现斐波那契数列
一、栈的基本概念
1.1 栈的定义
栈:指只允许在一端进行插入或删除的线性表。栈本身是一种线性表；但栈限定这种线性表只能在某一端进行插入与删除操作。
栈顶：线性表允许进行插入删除的那一段
栈底：固定的，不允许进行插入与删除操作的那一段
空栈：不含任何元素的空表
栈总体上又称作为后进先出的线性表，简称LIFO结构。
1.2 栈的常见基本操作
InitStack(&S)：初始化一个空栈S。
StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false。
Push(&S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
Pop(&S, &x)：出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)：栈销毁，并释放S占用的存储空间（“&”表示引用调用）。
二、栈的顺序储存结构
2.1 栈的顺序储存
采用顺序储存的栈称作为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。
若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定位top等于-1。
示例代码：
#define MAXSIZE 50 //定义栈中元素的最大个数
typedef int ElemType; //ElemType的类型根据实际情况而定，这里假定为int
typedef struct{ElemType data[MAXSIZE];int top; //用于栈顶指针
}SqStack;
2.2 顺序栈
首先介绍顺序栈的初始化，直接上代码：
void InitStack(SqStack *S){S->top = -1; //初始化栈顶指针
}
其次为判断顺序栈栈空的操作：
bool StackEmpty(SqStack S){if(S.top == -1){ return true; //栈空}else{ return false; //不空}
}
介绍进栈操作push函数：
/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S, ElemType e){//满栈if(S->top == MAXSIZE-1){return ERROR;}S->top++; //栈顶指针增加一S->data[S->top] = e; //将新插入元素赋值给栈顶空间return OK;
}
出栈使用pop函数：
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqStack *S, ElemType *e){if(S->top == -1){return ERROR;}*e = S->data[S->top]; //将要删除的栈顶元素赋值给eS->top--; //栈顶指针减一return OK;
}
最后介绍读取栈顶的操作：
/*读栈顶元素*/
Status GetTop(SqStack S, ElemType *e){if(S->top == -1){ //栈空return ERROR;}*e = S->data[S->top]; //记录栈顶元素return OK;
}
2.3 共享栈
共享栈，顾名思义就是两栈共享空间。具体概念是指：利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
接下来介绍共享栈的空间结构，代码如下:
/*两栈共享空间结构*/
#define MAXSIZE 50 //定义栈中元素的最大个数
typedef int ElemType; //ElemType的类型根据实际情况而定，这里假定为int
/*两栈共享空间结构*/
typedef struct{ElemType data[MAXSIZE];int top0; //栈0栈顶指针int top1; //栈1栈顶指针
}SqDoubleStack;
共享栈的出栈与入栈操作：
/*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack *S, Elemtype e, int stackNumber){if(S->top0+1 == S->top1){ //栈满return ERROR;}if(stackNumber == 0){ //栈0有元素进栈S->data[++S->top0] = e; //若栈0则先top0+1后给数组元素赋值}else if(satckNumber == 1){ //栈1有元素进栈S->data[--S->top1] = e; //若栈1则先top1-1后给数组元素赋值}return OK;
}/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqDoubleStack *S, ElemType *e, int stackNumber){if(stackNumber == 0){if(S->top0 == -1){return ERROR; //说明栈0已经是空栈，溢出}*e = S->data[S->top0--]; //将栈0的栈顶元素出栈，随后栈顶指针减1}else if(stackNumber == 1){if(S->top1 == MAXSIZE){return ERROR; //说明栈1是空栈，溢出}*e = S->data[S->top1++]; //将栈1的栈顶元素出栈，随后栈顶指针加1}return OK;
}
三、栈的链式储存结构
3.1 链栈
采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。
注：对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。
链栈的结构代码如下:
/*栈的链式存储结构*/
/*构造节点*/
typedef struct StackNode{ElemType data;struct StackNode *next;
}StackNode, *LinkStackPrt;
/*构造链栈*/
typedef struct LinkStack{LinkStackPrt top;int count;
}LinkStack;
3.2 链栈的进出栈操作
进栈：
/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S, ElemType e){LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));p->data = e;p->next = S->top; //把当前的栈顶元素赋值给新节点的直接后继S->top = p; //将新的结点S赋值给栈顶指针S->count++;return OK;
}
出栈：
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(LinkStack *S, ElemType *e){LinkStackPtr p;if(StackEmpty(*S)){return ERROR;}*e = S->top->data;p = S->top; //将栈顶结点赋值给pS->top = S->top->next; //使得栈顶指针下移一位，指向后一结点free(p); //释放结点pS->count--;return OK;
}
e.g：对比一下顺序栈与链栈,它们在时间复杂度上是一样的,均为O(1)。
对于空间性能,顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便,而链栈则要求每个元素都有指针域,这同时也增加了一些内存开销,但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样,如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。
四、栈的应用
4.1 实现斐波那契数列
题目大意:
说如果兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子 来。假设所有兔都不死,那么一年以后可以繁殖多少对兔子呢?
- 第一个月初有一对刚诞生的兔子
- 第二个月之后（第三个月初）它们可以生育
- 每月每对可生育的兔子会诞生下一对新兔子
- 兔子永不死去
从这个图可以看出，斐波那契数列数列有一个明显的特点，即：前面两项之和，构成了后一项。
如果用数学函数定义斐波那契数列，那就是：F(n) = F(n-1) + F(n-2)（n ≥ 2），其中F(0)=0，F(1)=1。
这个数列的实现，其实解释递归的一个典型例子;代码如下：
/*斐波那契数列的实现*/
int Fib(int n){if(n == 0){return 0; //边界条件}else if(n == 1){return 1; //边界条件}else{return Fib(n-1) + Fib(n-2); //递归表达式}
}
