栈的定义

栈就是操作受限的线性表，先进后出 FILO（First In Last Out）

一般设立栈顶指针初值为 top = -1（栈空）

⭐ 从栈顶出队，从栈顶进队

进栈：top ++;

出栈：top --;

共享栈

一般设初值为 top1 = -1 (栈空)，top2 = n (栈空)，用 S[0:n-1] 表示

当且仅当 top2-top1 = 1 时共享栈满（即两个栈顶指针相邻）

出栈序列

若元素的进栈序列为 ABCDE, 运用栈操作，能否得到出栈序列 BCAED 和 DBACE？

• BCAED 正确
• DBACE 不可能：若 D 为首先出栈元素，已知 ABC 先于 D 入栈， C 不可能后于 AB 出栈

实际应用举例

设计算法判断单链表（字符型data域)的全部n个字符是否中心对称。

ex: xyx, xyyx

思路：利用栈的先进后出的特点，将链表前一半元素依次进栈，然后将栈中元素出栈，与链表的后半元素依次进行比较。

int dc(LinkList L, int n){
  char s[n/2]; //字符栈，同数组实现栈的功能
  p = L->next;
  for(int i = 0; i < n/2; i++){ //链表前一半元素进栈
    s[i] = p->data;
    i++;
  }
  i--; //恢复最后的i值
if(n%2!=0) //若n为奇数，后移过中心结点
    p = p->next;
  while(p!=NULL && s[i]=p->data){ //检测是否中心对称
    i --; //i充当栈顶指针
    p = p->next;
  }
if(i = -1) //空栈
    return 1;
  else
    return 0;
}

将中缀表达式转化为后缀表达式

核心思想 ：栈外字符加入栈内时，要保证栈外字符的优先级比栈内所有字符的优先级都要低，否则，弹出栈内优先级较高的字符，并加入后缀表达式。

步骤 ：

• 遇到字母或数字直接入栈；

• 遇到运算符时：

• • 若为'(', 直接入栈；
  • 若为')', 依次把栈中运算符加入后缀表达式，直到出现‘(’, 并从栈中将‘(’删除；
  • 若为其他运算符，根据优先级表依次弹出比当前处理的运算符优先级高的运算符，并将其加入后缀表达式，直到遇到一个比它优先级低的或遇到了一个'('为止。

运算符优先级表

操作符	#	（	*，/	+，-	）
栈内优先级	0	1	5	3	6
栈外优先级	0	6	4	2	1

栈在递归中的应用

ex：斐波拉契数列 0 1 1 2 3 5 ...

int Fib(int n){
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1;
  else c
    return Fib(n-1) + Fib(n-2);
}

递归必要的两个条件：

• 递归表达式（递归体）
• 递归出口（边界条件）

采用非递归方式重写递归程序时必须使用栈。该说法是错误的！

ex: 计算斐波拉契数列可用循环实现

函数调用时，系统要用栈保存必要的信息；递归次数过多容易造成栈溢出