数据结构·精简复习·栈与队列的应用

核心点

• 自己创建栈来实现非递归程序。避免函数栈的使用。

• 字符栈的使用

• 中缀-后缀表达式

• 应用

栈和队列的应用

知识点：

• 栈的应用：表达式求值，中缀表达式，后缀表达式，递归，迷宫（DFS），进制转换。
• 队列： 层次遍历（数的层次遍历），宽度遍历BFS,缓冲区，页面替换算法。

非递归程序：

题目：实现以下函数的非递归版本

int fun1(int n,int x)
{
if(n==0)return 0;
if(n==1)return  2*x;
return 2*x(fun1(n-1,x))-2*(n-1,x);
}

解答：

#Define Maxsize 1024；

typedef strct
{
int no;
float val;
}mystack[Maxsize];

float funP(int n,float x)
{
int top=0；
float out1=1,out2=2*x;
while(n-top>=2) { mystack[top].no=n-stack;top++; }
while(top>=0)
{
  mystack[top].val=2*x*out2-2*(mastack[top.no]*out1);
  out1=out2;
  out2=mystack[top].val;
  top--;
}
if(n==0)return out1;
else return out2;
}

上述代码的思路为：

• 输入一个n阶函数，放入最底层，依次加上n-1阶，n-2阶。
• 到了2阶和1阶时计算出结果，向下返回结果。

while(n-top>=2) { mystack[top].no=n-stack;top++; }

改为

for(int i=n;n>=2;i--){mystack[top++].no=i;}

更好理解

字符栈的使用：

题目：判断链表是否中心对称
不用栈的算法：快慢指针找到中点，尾部翻转，两个子链同步检查
王道给出了使用字符栈的算法

bool symmetry（L）
{
  int len=len(L);
  int i=0
  char cstack[len/2];
  p=p->next;
  while(;i<n/2;i++)
  {
    cstack[i]=p->data;  
    p=p->next;
  }
  n个元素，则i为n；
  if(len%2==1)p=p->next;
  while(p!=null&&p->data==cstack[--i])
  {
    p=p->next;
  }
   return i==0?true:false;
}

补充：switch+case实现共享栈

bool Pop(int i,elemtype &e)
{
if(i!=0&&i!=1)return false;
if(s.top[1]-s.top[0]=maxsize+1)return false;栈空
switch(i)
{
case 0:
{
if(s.top[0]=-1)return false;
e=s.data[s.top[0]--];
return true;
}
}
case 1:
{
if(s.top[0]=maxsize)return false;
e=s.data[s.top[1]++];
return true;
}
}

中缀-后缀表达式(转换的思想和代码这一块，天勤真是讲的明明白白）

• 新加入的元素是数字则直接输出
• 新加入的元素如果是左括号则直接入栈
• 新加入的元素是右括号则出栈直到遇到匹配的左括号
• 新加入的元素是+-*/操作符，则小于等于栈顶元素，出栈+当前元素继续和新栈顶比较；优先级大于栈顶元素或栈空或栈顶为（，则入栈。
• */优先级大于+-

• 如下所示，需要一个辅助字符栈记作S1。存入操作符。而所谓的输出，指的是输出到预输出栈中，记作S2。

  
  
  image.png

代码：

void In2Post(char *str,stack &s2)
{
char s1[Maxsize];
int top1=-1,i=0;
while(str[i]!='\n')
{
  if(str[i]<='9'&&str[i]>-'10') { s2[++s2.top]=str[i++]; }
  else if(str[i]='(') { s1[++top1]=str[i++] }
  else if(str[i]=')')
  {
    while(s1[top1]!=')')
    {
      s2[++s2.top]=s1[top1--];
      top1--;  //删除掉‘(’
    }
    i++;
  }
  else
  {
    if(GetPrior(str[i])>GetPrior(s1[top]))) { s1[++top1]=str[i]; }
    else if(GetPrior(str[i])<=GetPrior(s1[top1]))) 
    {
         s2[++s2.top]=s1[top1];
         while(GetPrior(s1[--top1])<=GetPrior(str[i])&&s1[--top1]!='('&&top1>=0)
        {
          s2[++s2.top]=s1[top1];
        }
        s1[++top1]=str[i]
     }
    i++:
  }
  }
}
while(top1!=-1)
{
s2[++s2.top]=s1[top--];
}
}