在上一篇,简单入门栈,学习了栈的基本操作,那么栈作为一个操作受限制的数据结构,能做什么呢?

栈的应用举例 1

栈最大的特点就是先进后出,当然我们可以利用这个特性,我们可以解决不少问题。

进制转换

高进制向低进制转换,我们一般如下计算,以十进制向八进制转换为例子。

image-20210319172924464

我们的最终结果是我们计算结果逆序,使用栈存储结果,这样输出的时候就是我们要求最终结果了。

算法

void Conversion(int n)
{
	SqStack S;
	int e;
	if (!Init_SqStack(S))
		return;
	while (n)
	{
		Push(S, n % 8);
		n = n / 8; //自动取整
	}
	printf("\n8进制:  ");
	while (!(S.base == S.top)) //所有元素出栈完成
	{
		Pop(S, e);
		printf("%d", e);
	}
	printf("\n");
    FreeStack(S);
}

image-20210319211326266

计算阶乘

计算阶乘,曾经我们使用阶乘或者循环打法,如今得到栈这个好用的法宝,我们来分析一下。

int factorial(int n) //factorial 阶乘
{
    if(n<=1)
        return 1;
    return factorial(n-1)*n;
}

上面是简单使用递归实现,

欲求得 n的阶乘 必须知道 n-1 的阶乘

欲求得 n-1的阶乘 必须知道 n-2 的阶乘

.....

直到 计算到n==1时,1的阶乘为1

我们知道了 1的阶乘 就可以得到 2,3 ,4.....n的阶乘

其实不难发现递归就和栈一样,先执行的却是最后一个得出结果的。

当然我要打破我一个误区就是,递归算法时间复杂度不一定是最高的,该递推关系式为an+1−an=f(n),使用累加法计算时间复杂度, 也就是调用了 f(n)了 n次,故时间复杂度为 O(n).

如何计算递归的时间复杂度? --- 算法导论------递归算法的时间复杂度求解

栈实现阶乘

当然,从某种意义上,递归就是栈。那么栈如何实现呢?

从上面递归实现来看,递归每次求得的就是 n-1的值,那么我们每次将 n-1推入栈,最后保存每次出栈数值的乘积即可。

int factorial(int n)
{
	SqStack S;
	int e;
	if (!Init_SqStack(S))
		return 0;
	while (n > 0)
	{
		Push(S, n--);
	}
	int sum=1;
	while (!(S.base == S.top))
	{
		Pop(S, e);
		sum = sum * e;
	}
    FreeStack(S);
	return sum;
}

image-20210320000821581

使用栈实现括号匹配检验

括号检测,我们写代码的时候,ide会自动帮我们检测括号是否匹配。这个功能在用栈来实现,颇为简答。

假设 : 如果表达式中只有 “[]“ 和 "()" 两种括号, 输入如下

[      (   [       ]     [     ]    )     ]

1      2    3       4     5     6    7     8

处理

当遇到 左 [ 的时候,为了确保表达式正确,我们最希望输入 右 ] , 此时称 右 ] 的 期待值最高;当我们输入 左 (,那么 我们最期望输入的是 右 (右 ] 的期待就靠别站一站

以此类推,这种特性和栈的先进后出,高度吻合。

  1. 当输入第一个括号 左 [ 的时候,那么就把他推入栈中,作为栈顶,栈顶就是最期待得到的括号的左半边
  2. 当输入第二个括号, 左 ( 的时候 就把他推入栈中,最为栈顶
  3. 。。。。
  4. 当输入到 第四个括号的时候,就发现和第三个 左 [ 匹配,那么就将 左 [ 推出栈,此时栈顶为 左 ( ~~ , 右 ) 期待值最高!
  5. 。。。
  6. 以此类推如果,表达式括号匹配那么栈应当是空栈

当然我们还需要考虑 输入的右括号是错误的情况 输入的右括号和栈顶的左括号不匹配的时候,那么就是错误的

总结一下,具体算法是 ,

  1. 遍历表达式中每一个字符
  2. 如果是括号,那么进行下一步
  3. 如果是左括号就推入栈中
  4. 如果是右括号,进行判断,如果和栈顶元素匹配,进行出栈操作;如果不匹配,本表达式括号无法匹配
  5. 进行2-4 操作,遍历每一个字符。遍历完成之后,判断此栈是不是为空栈,如果为空本,表达式正确;如果不为空,那么本表达式错误

代码

本来用c的,但是c语言没有字符串型非常难受,所以我就混合用啦。

当然栈实现,我是用上一篇的代码啦

#define Bcount 3 // 判断括号种类数量
//括号集合  
// [ ( { ] ) }
// 0 1 2 3 4 5
const char bracket[Bcount*2] = { '[','(','{',']',')','}' };
int IsBracket(char c)
{
	for (int i = 0; i < Bcount * 2; i++)
		if (c == bracket[i])
			return i;
	return -1;
}
bool BracketMatcher(string s)
{
	SqStack S;
	if (!Init_SqStack(S))
		exit(0);//分配内存失败退出程序
	int i = 0; //遍历字符
	int tmp;//临时变量
	int e;//接出栈的元素
	int flag = 0;
	while (i < s.length())
	{
		tmp = IsBracket(s[i]);
		if (tmp!=-1)//如果为括号那么就进行判断
		{
			//输入的为左括号  入栈
			if (tmp<Bcount)
			{
				Push(S, tmp);

			}//输入右括号的情况 判断是否可以出栈
			else
			{
				GetTop(S, e);
				if ((tmp-Bcount)==e) //判断括号是否匹配
					Pop(S, e);
				else
					break;
			}
		}
		i++;
	}
	if (EmptyStack(S))//遍历完之后发现是 空 那么则匹配
		flag = 1;
	DestoryStack(S);
	if (flag)
		return true;
	return false;
}

image-20210321222140760

结语

栈的作用远远不及如此。

本文由 越行勤 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://blog.yxqin.top/2021/03/21/stack-apply
最后更新于:  213  天前,内容可能已经不具有时效性,请谨慎参考。

Q.E.D.


努力学习的小菜鸟