数据结构——堆栈

    对于栈，想必大家都十分熟悉了，也能很快的答出栈是一个先进后出的队列。但是在平常编程的生活中应用的十分少。在ACM中，栈是一种十分重要的数据结构（其他领域也一样），我们可以用这种数据结构解决一些十分棘手的问题，大大提高了程序的效率。
有这样一道名为Software BUGs 的题。题目的意思简要来说就是去除一篇文章中的所有 ”BUG” 字段。
　　　有些人可能认为这是一道水题，直接扫描文章，将其中的 ”BUG” 去掉就行。这样很容易就落进了陷阱。例如对于一个字符串 “ BBUBUGGG” 直接扫描过去得到 “BBUGGG” ,我们发现字符串中还有 ”BUG”(解决了一个BUG，又出现了一个BUG)，他们马上又提出解决方法，我们可以将字符串扫描两遍，但是一样的会有BUG出现.......那我们扫描到不在出现BUG为止，这的确不失为一个方法，但是经过计算后我们发现这个算法的时间复杂度是O(n^2)。在数剧比较大的情况下，这是不可能在规定时间里出结果的！！！
　　　若我们采用堆栈这种数据结构。算法原理如下：若栈中元素小于两个或压入的字符不为’ G’，则将字符压入栈中，否则判断栈顶的两个元素是否为’B’和’U’，若不是则将’G’压入栈中，否则将栈顶的两个元素弹出。
　　　这样似乎没有什么区别，让我们举个例子看看，对于字符串 “BBUBUGG”,下面模拟栈中的情况。
　　　栈                      即将要压入的元素
　　　                             B
　　　B                       B
　　　B B                     U
　　　B B U                   B
　　　B B U B                 U
　　　B B U B U               G   //符合条件，栈顶的两个元素将被弹出
　　　B B U                   G   //符合条件，栈顶的两个元素将被弹出
　　　B                       G
　　　B G
　　　所以最后的答案就是BG，不管嵌套多少层，这个数据结构都能以O(n)的时间复杂度计算出答案，下面贴出c++代码

#include<iostream>
#include<stack>
using namespace std;
int main(){
    char s[1000],stk[1000];
    cin >> s;
    while(s!="0"){
        int top = -1;
        for(int i=0;s[i]!='\0';i++){
           if(top<1||s[i]!='G'){
              top++;
              stk[top]=s[i];                     
           }else if(stk[top-1]=='B'&&stk[top]=='U'){
              top-=2;                                 
           }else{
              top++;
              stk[top]=s[i]; 
           }   
        }
        for(int i=0;i<=top;i++)
           cout << stk[i];
        cout << endl;
        cin >> s;
    }
    return 0;    
}

　　　同样的，我们可以利用这个数据结构做表达式求值，布尔表达式求值。POJ2106-Boolean Expressions就是这个类型的题目。