当前位置:首页 > 开发 > 编程语言 > 数据结构 > 正文

数据结构——堆栈

发表于: 2013-08-08   作者:追梦--   来源:转载   浏览:
摘要:     对于栈,想必大家都十分熟悉了,也能很快的答出栈是一个先进后出的队列。但是在平常编程的生活中应用的十分少。在ACM中,栈是一种十分重要的数据结构(其他领域也一样),我们可以用这种数据结构解决一些十分棘手的问题,大大提高了程序的效率。 有这样一道名为Software BUGs 的题。题目的意思简要来说就是去除一篇文章中的所有 ”BUG” 字段。    有些人可
    对于栈,想必大家都十分熟悉了,也能很快的答出栈是一个先进后出的队列。但是在平常编程的生活中应用的十分少。在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就是这个类型的题目。

数据结构——堆栈

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
Java的集合类库是最常用的类库之一。栈的后进先出机制可以在很多地方派上用场,比如,表达式预估/语
维基百科: 堆栈(英语:stack),也可直接称栈。台湾作堆叠,在计算机科学中,是一种特殊的串行形
java 数据结构——堆栈和队列  队列的基本概念   队列(简称队)也是一种特殊的线性表,队列的数
数据结构~~队列、堆栈和哈希表(二) 原文链接:Part 2: The Queue, Stack, and Hashtable 本文是
链式存储结构特点:   在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是
【摘要】链表存储结构的内存地址不一定是连续的,但顺序存储结构的内存地址一定是连续的;链式存储
程序员:左正康 发表时间:2013年12月16日 0:56 代号:与老鼠共处一室的日子 算法设计思想:算法中
原文链接:Part 2: The Queue, Stack, and Hashtable 本文是"考察数据结构"系列文章的第二部分,考
/* * 程序头部注释开始 * 程序的版权和版本声明部分 * Copyright (c) 2011, 烟台大学计算机学院学生
栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号