栈
- 栈（Stack）：只允许在一端进行插入或删除操作的线性表。
- 栈顶（Top）：线性表允许进行插入和删除的那一端。
- 栈底（Bottom）：固定的，不允许进行插入和删除的另一端
- 特点：
1.栈是受限的线性表，所以自然具有线性关系。
2.栈中元素后进去的必然先出来，即后进先出LIFO（Last In First Out）
* 栈中元素后进去的必然先出来，即后进先出LIFO（Last In First Out）顺序栈
- 栈是线性表的特例，那栈的顺序存储也是线性表顺序存储的简化。栈的顺序存储结构也叫作顺序栈。
顺序栈的操作
- 1.判空：
- 2.进栈：
- 3.出栈：
- 4.读取栈顶元素：
共享栈
- 顺序栈的存储空间大小需要事先开辟好，很多时候对每个栈各自单独开辟存储空间的利用率不如将各个栈的存储空间共享
- 示意图
- 共享栈的结构
- 共享栈的操作：（进栈）
链式栈
- 栈是线性表的特例，线性表的存储结构还有链式存储结构，所以也可以用链表的方式来实现栈。栈的链式存储结构也叫作链栈。
- 特点
1.链栈一般不存在栈满的情况。
2.空栈的判定条件通常定为top==NULL；
* 结构
* 链式栈的操作
* 1.进栈
* 2.出栈
栈的应用
1、括号匹配：假设有两种括号，一种圆的()，一种方的[]，嵌套的顺序是任意的。
- 算法思想：若是左括号，入栈；若是右括号，出栈一个左括号判断是否与之匹配；检验到字符串尾，还要检查栈是否为空。只有栈空，整个字符串才是括号匹配的。
2、表达式求值：
- 规则：从左到右扫描表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈然后跟这个符号进行运算，最后将运算结果进栈，直到最终获得结果。
3、递归：
- 要理解递归，你要先理解递归，直到你能理解递归。
如果在一个函数、过程或数据结构的定义中又应用了它自身，那么这个函数、过程或数据结构称为是递归定义的，简称递归。递归最重要的是递归式和递归边界。
* 1.阶乘
* 时间复杂度：O(NlogN)
* 2.斐波那契数列
* 时间复杂度 O(2^n)概要: 如何将中缀表达式转换成后缀表达式？
- 1.按运算符优先级对所有运算符和它的运算数加括号。(原本的括号不用加)
- 2.把运算符移到对应的括号后。
- 3.去掉括号。
栈的基本操作：
Status InitStack_Sq(SqStack *S)
{
(*S).base = (SElemType_Sq *)malloc(STACK_INIT_SIZE*sizeof(SElemType_Sq));
if(!(*S).base)
exit(OVERFLOW);
(*S).top = (*S).base;
(*S).stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestroyStack_Sq(SqStack *S)
{
free((*S).base);
(*S).base = NULL;
(*S).top = NULL;
(*S).stacksize = 0;
return OK;
}
Status ClearStack_Sq(SqStack *S)
{
(*S).top = (*S).base;
return OK;
}
Status StackEmpty_Sq(SqStack S)
{
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
int StackLength_Sq(SqStack S)
{
return S.top - S.base;
}
Status GetTop_Sq(SqStack S, SElemType_Sq *e)
{
if(S.top==S.base)
return ERROR;
*e = *(S.top - 1); //并不破坏栈
return OK;
}
Status Push_Sq(SqStack *S, SElemType_Sq e)
{
if((*S).top-(*S).base>=(*S).stacksize) //栈满，追加存储空间
{
(*S).base = (SElemType_Sq *)realloc((*S).base, ((*S).stacksize+STACKINCREMENT)*sizeof(SElemType_Sq));
if(!(*S).base)
exit(OVERFLOW); //存储分配失败
(*S).top = (*S).base + (*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*(S->top) = e; //进栈先赋值，栈顶指针再自增
(S->top)++;
return OK;
}
Status Pop_Sq(SqStack *S, SElemType_Sq *e)
{
if((*S).top==(*S).base)
return ERROR;
(*S).top--; //出栈栈顶指针先递减，再赋值
*e = *((*S).top);
return OK;
}
Status StackTraverse_Sq(SqStack S, void(Visit)(SElemType_Sq))
{ //遍历不应该破坏栈
SElemType_Sq *p = S.base;
while(p<S.top)
Visit(*p++);
return OK;
} 栈的进制转换 10 => 8
void conversion(int i)
{
SqStack S;
SElemType_Sq e;
InitStack_Sq(&S);
printf("十进制数 %d 转换为八进制数后为：0", i);
while(i)
{
Push_Sq(&S, i%8); //进栈时从低位到高位
i = i/8;
}
while(!StackEmpty_Sq(S))
{
Pop_Sq(&S, &e); //出栈时从高位到低位
printf("%d", e);
}
} 
