《算法实战策略》-chaper19-队列、栈和双端队列

时间:2021-02-04 06:37:03

对于计算机专业的学生来说,他们一定会很熟悉一句话:程序设计 = 算法 + 数据结构。而根据笔者的理解,所谓程序设计其实就是为了编程解决实际问题,所谓算法是一种解决问题某种思维的方法,但是思维需要得到编程实践,这就需要基于数据结构。一个好的数据结构能够让我们更快更高效得处理数据,有些模拟性、数学背景并不深厚的的问题,仅仅基于高效的数据结构就可以解决。那么这一章节,我们就单独将队列、栈、双端队列拿出来,结合具体的题目,看看它们是如何灵活的运用到解题策略当中的。

考虑到笔者在《入门经典》和《啊哈算法》中对几种简单的线性结构已经有所介绍,这里便不再赘述其概念和STL的用法。主要通过具体的题目来进行提高运用的能力。

不匹配括号问题:

小括号:().

中括号:[]

大括号:{}

现在给出一个由三种括号组成字符串,请编程判断三种括号是否匹配。

示例输入值:

3

()()

({[}])

({}[(){}])

示例输出值:

YES

NO

YES

分析:如果进行模拟,过程会变得非常麻烦而且非常不好设计。但是如果我们基于栈的数据结构,会发现会使问题变得异常简便。因为括号匹配的法则和栈“后入先出”的特点刚好吻合。我们只需要将所有的左括号依次入栈,一旦遇到右括号,我们将之与栈顶元素进行匹配,如果匹配,栈顶元素出栈,否则,完成判断。

简单的参考代码如下。

bool wellMatched(const string& formula)
{
const string opening("({["),closing(")}]"); stack<char> openStack;
for(int i = ;i < formula.size();++i)
{
if(opening.find(formula[i]) != -)
openStack.push(formula[i]);//左括号,压栈
else//右括号,进行匹配
{
if(openStack.empty()) return false;//此时栈空,匹配失败
if(opening.find(openStack.top()) != closing.find(formula[i])) return false;//不匹配 openStack.pop();//弹出栈顶元素
} return openStack.empty();//遍历字符串所有字符,如果栈空,匹配成功
}
}