队列和栈的应用

队列和栈的使用

标签(空格分隔): algorithm


队列和栈的应用

1.队列的应用

  • 队列是一种常见的数据结构,主要的特性先进来的元素会先出去,也就是First In First Out:FIFO ,所以适合具有这个特性的算法来使用,比如图的广度优先搜索二叉树的层次遍历等。
  • 所以队列和生活中的排队非常相似,先来的先服务,后来的后服务。

2.栈的应用

  • 栈和队列的特性不一样,队列的特性是先进先出先进后出
  • 栈的出口和入口只有一个,都是从一个地方进入或者出去,所以进去的时候,就不能出来,而且出来的时候,只有最后进入的能够出来
  • 比较适合于先进来等着,等到满足某种条件的时候,才按照后来的先处理
  • 想起了进电梯的场景,一般都是先进电梯的最后出来(考虑到同一楼层的)

5.栈使用举例

  • 这里有个题目说的是如何判断一个括号字符串包含的括号对:'{','}','[',']','(',')' 是否合理
  • 假设有个字符串"{}{}(){}[]{][",其实括号的匹配是有一定的规律的,']',')','}' 只要出现右括号的地方,那么它前面必须要有一个其对应的左括号才行,如果不是对应的左括号,那么就是不合理的括号串。类似消消乐,只是条件是最近的括号匹配可以消除
  • 具体的就是,再扫描字符串的过程中,首先把左括号存起来,遇到右括号的时候,看看离这个右括号最近的左括号(栈顶的左括号)是否合理,把合理的括号对匹配上,不合理的直接返回整个括号字符串不合理。
  • 最后如果是完全匹配,那么栈为空,只要栈非空,那么说明不是完全匹配
  • 从上面的描述中能看出来,后扫描到的左括号要存起来,但是有需要在遇到右括号的时候,匹配最近的左括号,有后进先出的特性吧,这就是一个很典型的栈的应用。
public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(int i= 0; i < s.length(); ++i){
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') { // 左括号放入栈中,等待匹配
                stack.push(c);
            }else { // 右括号,进行匹配 
                /**1.栈为空,无法匹配false
                 * 2.匹配上则把左括号匹配出栈
                 * 3.没有匹配上那么false
                 * */
                if(stack.empty()) 
                    return false;
                char ch = stack.peek();
                if(c - ch == '}' - '{' || c - ch == ']' - '[' || c - ch == ')' - '(')
                    stack.pop();//把匹配的左括号出栈
                else
                    return false;
            }
        }
        /**如果栈为空,那么完全匹配*/
        return stack.empty();
    }


  • 值得提的是,栈的应用非常广泛,例如:函数调用函数调用,从CPU角度来看,CPU首先会保存调用者A的现场内容(变量等情况),这个时候会把这个现场情景进栈(也就是数据信息),保存在栈中。然后去执行A调用的函数B,如果这个时候B还调用了函数C,那么在CPU转去执行C的时候,还是会类似的把B的现场进栈,一直到C函数执行完,再从栈中把B现场出栈,继续执行B,然后B执行完,把A的现场出栈,执行A,直到所有的程序执行结束。
/**main ->
 *      A -> 
 *              B ->
 *                  C 执行完
 *                  <-C
 *              <- B
 *      A <-  
 * 执行A ->调用 B ->调用C   c返回->执行B  B返回->执行A
 * |    |   |    |  |    |      |    |      |    |
 * |    |   |    |  |    |      |    |      |    |
 * |    |   |    |  | B  |      |    |      |    |
 * |    |   | A  |  | A  |      | A  |      |    |
 * |main|   |main|  |main|      |main|      |main|
 * 
 * 
 * **/


  • 从上面的调用可以看出来,函数的调用也是有成本的,如果函数嵌套调用的越多所消耗的资源,栈数据也就越大
  • 如果上面的函数B,C都是A函数的话,那么就会出现A调用自己的情况,这就是函数的递归调用
  • 所以函数的递归是通过栈这种数据结构来实现的,后面大多数的递归,都能通过使用栈的方式来实现。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 222,946评论 6 518
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 95,336评论 3 399
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 169,716评论 0 364
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 60,222评论 1 300
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 69,223评论 6 398
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 52,807评论 1 314
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 41,235评论 3 424
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 40,189评论 0 277
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,712评论 1 320
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,775评论 3 343
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,926评论 1 353
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 36,580评论 5 351
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 42,259评论 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,750评论 0 25
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,867评论 1 274
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 49,368评论 3 379
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,930评论 2 361

推荐阅读更多精彩内容

  • 第2章 基本语法 2.1 概述 基本句法和变量 语句 JavaScript程序的执行单位为行(line),也就是一...
    悟名先生阅读 4,153评论 0 13
  • 第3章 基本概念 3.1 语法 3.2 关键字和保留字 3.3 变量 3.4 数据类型 5种简单数据类型:Unde...
    RickCole阅读 5,132评论 0 21
  • 第5章 引用类型(返回首页) 本章内容 使用对象 创建并操作数组 理解基本的JavaScript类型 使用基本类型...
    大学一百阅读 3,238评论 0 4
  • 大学对于我来说就是我离开父母进入到独立生活的地方,但从我离开家到大学的那天起,我的大学之旅就正式开始了! 我所在的...
    半梦鸢尾阅读 439评论 5 7
  • 2017年12月8日 星期五 晴 今天上午,要跑操比赛了,我高兴地蹦蹦跳跳,手舞足蹈的,开始了,我在后面压住步,...
    夏之雨_a326阅读 94评论 0 0