数据结构栈的应用举例 1|越行勤‘s Blog

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

栈的应用举例 1

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

进制转换

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

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

算法

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);
}

计算阶乘

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

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;
}

使用栈实现括号匹配检验

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

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

[      (   [       ]     [     ]    )     ]

1      2    3       4     5     6    7     8

处理

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

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

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

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

总结一下，具体算法是，

遍历表达式中每一个字符
如果是括号，那么进行下一步
如果是左括号就推入栈中
如果是右括号，进行判断，如果和栈顶元素匹配，进行出栈操作；如果不匹配，本表达式括号无法匹配
进行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;
}