精华内容
下载资源
问答
  • 是一个后进先出的数据结构。后进先出的意思就是后来进来的先出去。现实生活中有很多后进先出的例子,比如打印机的纸,餐馆的盘子等等。栈可以基于线性表或者链表创建。栈是一种特殊的线性表,其插入(入栈,压栈)与...
    f37d252c5ae5250cffa5328ce7468a4c.png什么是栈?栈与线性表类似,栈是他们的限制版本。栈只能够从一段插入一段删除。是一个后进先出的数据结构。后进先出的意思就是后来进来的先出去。现实生活中有很多后进先出的例子,比如打印机的纸,餐馆的盘子等等。栈可以基于线性表或者链表创建。栈是一种特殊的线性表,其插入(入栈,压栈)与删除(出栈,弹栈)都在同一段操作。作者自己写了一些东西来实现栈,但奇妙的是作者写的东西与C++的标准模板库冲突了。所以,我就干脆只用标准模板库的stack了。
    // 使用栈#include // 新建栈stack<int> A// 判断栈是否为空A.empty()// 压栈(添加一个数)A.push(i)// 弹栈(删除顶部的数)A.pop()// 返回栈的空间A.size()// 返回栈顶的元素A.top()
    以下是栈的测试
    // 栈的测试void Stack_A(){   stack<int> A;   // 判断栈是否为空   cout << A.empty() << endl;   for (int i = 1; i <= 10; i++)    {       cout << "压栈,数:" << i<< endl;       A.push(i);    }   // 输出栈的空间数量   cout << A.size() << endl;   for (int i = 1; i <= 10; i++)    {       cout << "弹栈,数:" << A.top()<< endl;       A.pop();    }}
    接下来讲一些奇奇怪怪的例题来使用栈f37d252c5ae5250cffa5328ce7468a4c.png第一、匹配括号
    “(()))(()(((()(()(()((()((())))()()”“((1+2)*3/5+(16*8)-1)”
    给你以上这么一组括号或一组字符串,判断他们的括号是否一一匹配。(())    这样就算匹配(()     这样就不算匹配()()  这样也算匹配这时候栈就变得非常实用。首先我们开始遍历数组,先寻找“(”,每找到一个就将其加入栈。如果找的数不是“(”,而是其他符号,则忽略。如果是“)”,则要弹栈,将前面的“(”弹出,说明匹配完成一个括号。最后,如果栈为空,则说明所有括号匹配完成。若栈还有,则就没有匹配完成。当然在过程中,若栈已经空了,又找到了“)”,那肯定也是没有匹配完成的。
    // 匹配括号void Match_Brackets(string strs){    stack<int> s;    int length = (int)strs.size();    // 扫描strs寻找左括号和有括号    for (int i = 0; i < length; i++)    {        // 左括号,压栈        if (strs.at(i) == '(')            s.push(i);        // 为右括号        else if (strs.at(i) == ')')        {            // 如果为右括号同时栈不为空            if (!s.empty())            {                s.pop();            }            else            {                cout << "括号不匹配!" << endl;                return;            }        }    }    // 遍历结束,栈不为空    if (!s.empty())    {        cout << "括号不匹配!" << endl;    }}
    f37d252c5ae5250cffa5328ce7468a4c.png这是一个小标题关于这个汉诺塔奇奇怪怪的神话就不提了……就是有三根柱子,一根柱子上有三个盘子要把第一根柱子的东西全部搬到第三根去,其中小盘子必须在大盘子上面,一次只能搬一个。这个貌似是有规律的,然后么,次数也是有规律的。次数:f(n)=2f(n-1)+1f(0)=0但不考虑次数,只考虑方法。如果我们要搬2个盘子那搬的顺序是:1->21->32->3那如果要搬n个呢?我们可以把n个分为1个与n-1个,那个1就是最大的那个。然后根据搬2个盘子的顺序来就行。那n-1怎么搬?那就把n-1分为n-2与1。以此类推,推到1为止,再把每一步都展示出来,就完成了。听起来真的很简单,但…………想起来真的很难不能多想不能多想一切关于递归的问题不能多想,越想越复杂。如果想弄清递归的每一步,那是不可能的,要看递归到底是什么,到底在解决什么。而不是去探究每一步都在做什么。(说实话我就是没有好好学递归…………经典问题都没研究过…………)我先上递归实现代码。
    // 递归解决汉诺塔问题void Towers_Of_Hanoi(int n, int x, int y, int z){    if (n > 0)    {        // 将n-1从塔1搬到塔2        Towers_Of_Hanoi(n - 1, x, z, y);        // 将最底下的盘子从塔1搬到塔3        cout << "移动顶端的盘子从" << x << "到" << y << endl;        // 将n-1从塔2搬到塔3        Towers_Of_Hanoi(n - 1, z, y, x);    }}

    如果想要数据可视化,就可以用到栈来储存每一步的数据。
    上代码
    // 全局变量stack<int> tower[4];void moveAndShow(int, int, int, int);// 使用栈解决汉诺塔问题void towersOfHanoi(int n){    for (int d = n; d > 0; d--)     // 塔的空间        tower[1].push(d);           // 加入盘子    // 开始移动,将盘子由1,依赖3移动到2    moveAndShow(n, 1, 2, 3);}// 此处注意是将x移动到y塔上,而不是z塔上void moveAndShow(int n, int x, int y, int z){    // 将n个盘子从x塔依赖z塔移动到y塔,并且显示状态    if (n > 0)    {        moveAndShow(n - 1, x, z, y);        int d = tower[x].top();   // 移动顶端        tower[x].pop();           // 弹栈        tower[y].push(d);         // 压栈        // showState();              // 展示        // 展示移动过程        cout << "移动盘子" << d << "从塔" << x << "到塔" << y << endl;        moveAndShow(n - 1, z, y, x);    }}

    018fa0d46da592750fb199809e389301.png

    展开全文
  • 本文转载于 SegmentFault 社区作者:打了个冷颤有效的括号编写程序时, 一个类, 函数, 表达式, 都需要括号匹配,如果括号没有正确匹配,编译器就会报错, 这其实一种是数据结构--栈的应用。栈(Stack)是一种线性结构只能...

    本文转载于 SegmentFault 社区

    作者:打了个冷颤


    有效的括号

    编写程序时, 一个类, 函数, 表达式, 都需要括号匹配,如果括号没有正确匹配,编译器就会报错, 这其实一种是数据结构--栈的应用。

    栈(Stack)


    是一种线性结构

    只能从一端添加元素,也只能从同一端取出元素,这一端称为栈顶

    后进先出的特性(LIFO-last in first out):最后插入的元素最先出来.

    这种后进先出的特性十分有用,便于理解栈的实际应用,举如下两个例子:

    • 无处不在的Undo操作(撤销)

    编辑器中的撤销原理就是运用了栈先进后出的特性,栈顶存放了你最近一次的操作,撤销会将这次操作的内容弹出栈顶

    • 程序调用的系统栈

    程序在进行子过程调用的时候,当一个子过程执行完成之后,可以自动的回到上层调用中断的位置继续执行下去

    b9defddcea963e5766d65aff52fe50d3.png

    1. 函数A()在执行到第2行时调用了函数B(),中记录下A2(表示函数A()在第2行时中断);

    2. 进入函数B(),执行到第2行时调用函数C(),栈中记录下B2(表示函数B()在第2行时中断);

    3. 进入函数C()一直到执行完毕,cpu不知道下一步该执行哪行代码,到系统栈中查看,最近一次中断的地方是函数B()第2行,返回去执行,到函数A()也是如此,执行完毕.

    下面说说括号匹配的题目


    leetcode有这样一题,我们可以参照它来理解这个概念

    leetcode第20题:有效的括号

    题目:

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

    有效字符串需满足:

    左括号必须用相同类型的右括号闭合。

    左括号必须以正确的顺序闭合。

    来源:力扣 (LeetCode)

    b760d3905922fccce86de891fd4c42ce.png

    首先声明一个栈,然后逐一遍历这个括号字符串,如果是左括号就将它压入栈;

    如果是右括号,此时查看栈顶的元素是否与之匹配,如果匹配成功,栈顶的元素就要出栈;

    如果最后栈中的元素被清空,证明这串括号是有效的;

    如果匹配失败,那么就证明了这串括号是错误的.

    栈顶元素反应了在嵌套的层次关系中,最近的需要匹配的元素

    标准答案代码实现:

    import java.util.HashMap;

    import java.util.Stack;

    //有效的括号

    public class Solution {

        //负责映射的哈希表

        private HashMap mappings;
        //构造时初始化哈希表,使代码更具可读性
        public Solution(){
            this.mappings = new HashMap<>();
            this.mappings.put(')''(');
            this.mappings.put('}''{');
            this.mappings.put(']''[');
        }
        public boolean isValid(String s){
            //声明一个栈
            Stack stack = new Stack<>();
            //遍历字符串for (int i = 0; i 
                char c = s.charAt(i);
                //如果当前字符串是右括号if (this.mappings.containsKey(c)){
                    //获取栈的顶部元素。如果栈是空的,设置一个哑值'#'
                    char topElement = stack.empty() ? '#' : stack.pop();
                    //如果此括号的映射与栈的顶部元素不匹配,则返回falseif (topElement != this.mappings.get(c)){return false;
                    }
                }else {
                    //如果当前字符是左括号,push到栈中
                    stack.push(c);
                }
            }
            //如果堆栈仍然包含元素,那么它是一个无效的表达式。return stack.isEmpty();
        }
    }

    简易版:

    import java.util.Stack;

    //有效的括号

    public class Solution {



        public boolean isValid(String s){

            //声明一个栈

            Stack stack = new Stack<>();for (int i = 0; i 
                char c = s.charAt(i); //转存为charif (c == '(' || c == '[' || c == '{'){
                    //如果是左括号就push进去
                    stack.push(c);
                }else {//否则检查是否与栈顶元素匹配if (stack.isEmpty())return false;
                    //将栈顶元素弹出
                    char topChar = stack.pop();
                    //如果并不能匹配返回falseif (c == ')' && topChar != '(')return false;if (c == ']' && topChar != '[')return false;if (c == '}' && topChar != '{')return false;
                }
            }
            //最后检查栈是否为空return stack.isEmpty();
        }
    }

    结合自己的理解记录了学习的过程。


    - END -

    7b6a38f11c302f73539254db38bbf700.png

    展开全文
  • 什么是数据结构栈是一种数据结构。那什么是数据结构呢?我这里不给出严格的定义,因为对于完全没有基础的新人而言,严格的定义说了等于没说。我只从一个简单的角度举例说明一下。在初学阶段,你可以认为数据结构就是...

    我们的目标是写一个表达式求值的计算器。我今天先介绍一种做法,那就是使用栈来完成表达式求值。

    什么是数据结构

    栈是一种数据结构。那什么是数据结构呢?我这里不给出严格的定义,因为对于完全没有基础的新人而言,严格的定义说了等于没说。我只从一个简单的角度举例说明一下。在初学阶段,你可以认为数据结构就是关于数据在计算机中如何组织的一门课程。

    比如,我要往一个数组中,存1,3,2这三个整数,那么,我实际存的时候,是按照从小到大排着存呢,还是从大到小存,还是没有顺序随便存,这要根据实际的需求来决定。根据需求决定数据存储的方式。这就是数据结构要研究的内容。

    什么是栈

    以前打了粮食,会放到一个筒形的容器里,这个筒形的容器,大家叫它栈。它的特点是先放进去的粮食要最后才能取出来,后放进去的粮食是最先被取出来。所以中文就用栈这个词翻译英文的stack了。

    想一想,生活中,还有很多栈的例子。比如叠在一起的碗盘,叠的时候我们是从底往高处叠,但是取的时候,我们是从最上面的一个依次向下取。这也是一个典型的栈:后进先出,先进后出。

    那么Java语言中如何模拟这一个过程呢?首先,我们定义一个名叫Stack的类:

    public 

    因为我们的课程里还没有涉及到泛型,为了简单起见,我先用整型代替了。如果有些同学,已经有一定的基础了,也可以看一下泛型版的代码:

    import java.util.ArrayList;
    
    public class Stack<T> {
        private ArrayList<T> list;
        private int size;
    
        public Stack(int size) {
            this.size = size;
            this.list = new ArrayList<T>(size);
        }   
    
        public static void main(String args) {
            Stack<Integer> s = new Stack<Integer>(10);
        }   
    }

    本文中后面的例子,我还是会使用简单版本的。

    OK,接下来,就是要往类里添加相关的操作了。先定义一个可以往栈里写数据的函数,叫做push:

    public 

    这个函数的意义就是,把数据num存到数组里,并且把游标向后指一位。逻辑比较简单。

    相对应的,我们还可以继续定义以下三个方法,分别是取栈顶元素(getTop),出栈(pop),判断栈是否为空(isEmpty)。

    public 

    好了,一个栈就定义完了(当然,这里是有问题的,因为我们在push里,没有检查top是否越过了size规定的数组,出栈的时候,也没有判断top是否等于0。这个做为今天的第一个作业,请读者自行添加。)

    栈的应用

    这个数据结构看上去好简单啊。肯定有很多人会这样想,但其实,栈在计算机编程中可以说是最基础也是最重要的数据结构了。其功能之强大,可能出乎很多人的意料。我们先通过一个小例子来体会一下。看这样一道题目:

    输入一组括号,请判断这些括号的匹配是否合法。例如

    (()],不合法,左边的小括号与右边的中括号不能匹配。

    {[()]},合法的,所有的括号都可以正确匹配。

    {(}),不合法,顺序是错的。

    ((()),不合法,右括号少了一个。

    大家可以先自己想一下,这个问题怎么解决,自己写一写,看看能不能搞得定。如果不使用栈,自己穷举所有情况,逐个去处理的话,好像有点麻烦。

    我们来分析一下。如果遇到第一个右括号,那与之配对的一定是离它最近的那个左括号,如果离它最近的左括号的类型与这个右括号的类型是一样的(比如都是小括号),那这就是一次成功的配对。把一组成功配对的括号从括号序列中删去,不会影响原来序列是否合法这个属性,就是说原来合法的,仍然合法,原来不合法的,仍然不合法。通过这样的办法就可以化简题目了。

    算法是有了,怎么实现呢?遇到右括号,只去检查离它最近的,如果匹配上了,就把左右括号一起删掉,这不就是栈吗?每次都只检查栈顶的左括号,如果与右括号匹配上了,就把左括号出栈(删掉)。

    好了,数据结构有了,算法有了,写成程序就太简单了:

    public 

    虽然代码很长,但其实逻辑非常简单易懂。这里漏了一种情况,那就是左括号少,右括号多的情况。这个也留做作业(其实就是getTop和pop的时候要做检查)

    Java虚拟机的实现是基于栈的

    Java虚拟机规范里定义了Java所使用的字节码。我们知道Java文件要先编译成字节码文件,也就是class文件,但是大家有没有想过,class文件里都是些什么呢?class文件的结构,我以后会专门讲。今天只演示一个简单的例子,让大家有个初步的感觉。先看这样一个源文件:

    public class Main { // Main.java
        public static int add(int a, int b){ 
            return a + b;
        }   
    }
    

    执行以下命令:

    javac Main.java
    javap -c Main

    可以看到这样的输出:

      public static int add(int, int);
        Code:
           0: iload_0
           1: iload_1
           2: iadd
           3: ireturn
    

    add 函数被编成了四条字节码指令,这四条字节码是什么意思呢?

    你可以认为Java的每一个函数都有一个操作数栈,每条指令就是在对这个操作数栈进行操作。比如 iload_0,就代表把第一个参数 push 进操作数栈,iload_1代表把第二个参数 push 进操作数栈,而 iadd 代表,从栈上连续pop两次,取两个数,将其相加,再把结果送到栈上。ireturn 则表示把栈顶的值做为返回值传给调用者。Java字节码的整个执行过程都是在这样一个栈上的。如果用图来表示,这四个步骤就是:

    iload_0,使a先进栈

    03a967b88832dbed05645c1a5a5fb068.png

    iload_1, 使b进栈

    f1f42caac624d048de13b37cd55ae1fd.png

    iadd,做了三件事情,b 和 a 出栈,计算 a+b,将计算结果入栈:

    25e6e48df0b338845af680bf4da44166.png

    ireturn 将当前栈顶的值返回出去。

    最后一节看不懂也没有关系。我们后面会有Java虚拟机的专门讲解。好了,今天的课程就到这里了。

    作业:

    1. 实现完整版的 stack

    2. 完善文章中的代码,使得(()))这种情况也能正确执行。

    3. 后缀表达式是这样的一种表达式:

    不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:(2 + 1) * 3 , 即2 1 + 3 *

    请结合上一节课的TokenStream的基础上,用栈实现后缀表达式求值 ,例如,输入是

    8 5 - 4 2 - *

    输出值是6,计算过程是8-5为3,4-2为2,3与2相乘得6

    上一节:Java中的设计模式:适配与装饰

    下一节:

    目录:课程目录

    展开全文
  • 这次又重新学习python的数据结构及算法(中国MOOC上的公开课),就好好做个笔记吧。栈是一种只能在一端进行插入和删除的线性数据结构。一般来说,栈主要有两个操作:一个是进栈(PUSH),又叫作入栈、压栈;另一个是出栈...
    以前学习的时候都没怎么好好的做过笔记,总是东记一点,西写一点,甚至都不做笔记,导致后面找的时候找不到,最后还是求助搜索引擎浪费掉很多时间。好脑筋不如个烂笔头呀。这次又重新学习python的数据结构及算法(中国MOOC上的公开课),就好好做个笔记吧。栈是一种只能在一端进行插入和删除的线性数据结构。一般来说,栈主要有两个操作:一个是进栈(PUSH),又叫作入栈、压栈;另一个是出栈(POP),或者叫作退栈。栈遵循的原则是后进先出,即LIFO(Last In First Out)。下面使用python的基本结构列表实现栈:
    ## 使用列表的末尾作为栈顶## 也可使用列表的开头作为栈顶,其实这两种方法的性能是不同的## 列表开头作为栈顶,复杂度为 O(n)## 列表末尾作为栈顶,复杂度为 O(1)class Stack:    def __init__(self):        self.items = []            def isEmpty(self):        return self.items == []            def push(self, item):        self.items.append(item)            def pop(self, item):        return self.items.pop()            def peek(self):        return self.items[len(self.items) - 1]            def size(self):        return len(self.items)
    栈的应用:领扣上有个题是关于括号匹配的。基本思想就是:从左至右扫描括号串,最新打开(Most recent)的左括号,应该匹配最先遇到的右括号。这样,第一个左括号(最早打开),就应该匹配最后一个右括号(最后遇到)。这种次序反转的识别,正好符合栈的特性。

    0705cb404eda0010c248a803ef0a8ad7.png

    c4d474576a1c2b7472cc1a3781f80feb.png

    代码的实现有一个简单版的(只检查小括号)和一个普通版的(同时检查小括号,中括号及大括号),现实中遇到更多的自然是普通版的。这里就只贴下普通版了。
    ## Stack()是上面写好的类def matches(open, close):    opens = '([{'    closes = ')]}'    return opens.index(open) == closes.index(close)def check(strings):    s = Stack()    balance = True    index = 0    while index and         symbol = strings[index]        if symbol in '([{':            s.push(symbol)        else:            if s.isEmpty():                balance = False            else:                top = s.pop()                if not matches(top, symbol):                    balance = False        index += 1    if balance and s.isEmpty():        return True    else:        return False        
    展开全文
  • 你是否快要被C语言进阶版的数据结构秃光了头呢?在紧张的考试之前,精英计划团快马加鞭地为大家整理出了考试的重点,快来吃安利吧!!数据结构第一次测验大复习※数据的组织方式四种基本的数据结构为集合、树、...
  • 数据结构中的栈不要与 Java 中的栈混淆,他们俩...在开发中,我们有特定的场景,根据特定的场景去选用数据结构,栈的适用场景非常多,比如浏览器的前进与后退、字符串括号的合法性等,我们使用栈来实现就比较好,...
  • 注:本文如涉及到代码,均经过Python 3.7实际运行检验,保证其严谨性。本文阅读时间约为4分钟。栈的编程练习题1:有效的括号给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。有效字符串...
  • 所以这篇文章主要是写如何使用代码来描述栈,当然也是让大家很容易理解的语言。还是先给出这篇文章的大致脉络。首先,对栈有一个基本认识接下来,用代码实现栈,以及栈的常用操作然后,介绍栈的几种应用场景最后,小...
  • 点击上方蓝字,关注:无量测试之道 作者...这就要用到我们今天要讲的“栈”这种数据结构。带着这个问题,我们来学习今天的内容。2.如何理解“栈”?关于栈,有一个非常贴切的游戏--汉诺塔。玩这个游戏的时候,我们都...
  • 为大家讲解 LeetCode 第 20 题,是一道结合数据结构常考察的算法题目。每日一笑 朋友打算跳绳减肥,我想提醒他注意别伤到膝盖,但考虑他肯定坚持不到三天,不提醒也行。题目描述 给定一个只包括 '(',')','{','}'...
  • 有效括号(Valid-Parentheses)题干如下:给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。有效字符串需满足: 1.左括号必须用相同类型的右括号闭合。 2.左括号必须以正确...
  • 临时起意想对数据结构做的一些练习(当然是新手向的)进行总结,于是这篇文章就这么产生了。1. 在链接存储结构下,将线性表 ,以 m 位置为分界点的前后两部分元素换位成 。注:这里的线性表下标从1开始这题是相对...
  • 数据结构括号匹配

    2018-07-04 14:22:50
    数据结构试验代码 数据结构试验代码数据结构试验代码数据结构试验代码
  • 数据结构的作业,可以借鉴一下阿,同时可以解决一时的需要阿,谢谢朋友们的支持!
  • 数据结构 括号匹配

    2018-10-31 01:10:28
    /*括号匹配问题*/ #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #include&lt;string.h&gt; #define stack_init_size 100 #define stackincrement 10 #define error ...
  • 基于数据结构括号匹配问题,有源代码,文档,执行文件等
  • 数据结构》中的括号匹配问题的C#语言代码实现,供参考。
  • 括号匹配代码

    2013-05-13 21:25:32
    括号匹配代码利用堆栈数据结构算法的括号匹配实验!
  • ``` ```#include #include #define MI 100; #define MX 1000; typedef struct { int *base; int *top; int stacklist; }sqstack; int InitStack(sqstack *s) { s->base = (int *)malloc(MI *sizeof(int))...
  • 3.6.简单括号匹配我们现在把注意力转向使用栈解决真正的计算机问题。你会这么写算术表达式(5+6)*(7+8)/(4+3)其中括号用于命令操作的执行。你可能也有一些语言的经验,如 Lisp 的构造(defun square(n)(* n n))这段...
  • 数据结构括号匹配(附源代码已测试)

    千次阅读 2012-09-26 21:28:09
    // 2.1.1如果栈顶元素与右括号匹配则continue比较下一个 switch(temp) { case '(': if(a[i] == ')') {Pop(&s); continue;} case '[': if(a[i] == ']') {Pop(&s); continue;} case '{': if(a[i] == '}') {Pop(&...
  • 程序写完了,但是一运行就崩了,我不知道错误在哪,求大神指教!下面贴出我的代码: #include #include #include using namespace std;...StackEmpty(S)&& flag) cout括号匹配"; else cout括号不匹配"; }
  • 声明:括号匹配的实现使用的是.cpp文件。 由于我使用的是vs2010,vs2010的编译器不支持函数返回值bool类型,并且不能这样定义for(int i= 0; i < 10; i++),必须在函数的开头声明i=0。为了编写的方便,我使用的是...
  • 输入数据保证只含有"[","]","(",")"四种字符输出如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No 代码如下 #include #include #define SIZE 20 #define CREMENT 10 ...
  • 阅读本文章前先阅读java实现数据结构02.01(栈详解代码之数组栈) 括号匹配类 /** * @description: 对一组括号进行匹配看是都符合正确匹配,如:{[]}合法,{[}]不合法,返回true则合法,返回false则不合法 * @...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 510
精华内容 204
关键字:

数据结构括号匹配代码

数据结构 订阅