栈_栈指针 - CSDN
订阅
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。 展开全文
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
信息
外文名
stack
函数的返回地址和参数
又    名
堆栈
种    类
数据结构
中文名
说    法
进栈、出栈
栈基本概念
要搞清楚这个概念,首先要明白”栈“原来的意思,如此才能把握本质。"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈、出栈的说法。首先系统或者数据结构栈中数据内容的读取与插入(压入push和 弹出pop)是两回事!压入是增加数据,弹出是删除数据 ,这些操作只能从栈顶即最低地址作为约束的接口界面入手操作 ,但读取栈中的数据是随便的没有接口约束之说。很多人都误解这个理念从而对栈产生困惑。而系统栈在计算机体系结构中又起到一个跨部件交互的媒介区域的作用 即 cpu 与内存的交流通道 ,cpu只从系统给我们自己编写的应用程序所规定的栈入口线性地读取执行指令, 用一个形象的词来形容它就是pipeline(管道线、流水线)。cpu内部交互具体参见 EU与BIU的概念介绍。栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。栈也称为先进后出表。栈可以用来在函数调用的时候存储断点,做递归时要用到栈!以上定义是在经典计算机科学中的解释。在计算机系统中,栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中,也可以将数据从栈顶弹出。在i386机器中,栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小,弹出的操作使得栈顶的地址增大。栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息,这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息:1.函数的返回地址和参数2. 临时变量:包括函数的非静态局部变量以及编译器自动生成的其他临时变量。
收起全文
  • 系列课程包含11个部分,本课为第3部分和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用...
  • 是数据结构中较为简单的结构体,是一种操作收到限制的线性表.但简单不代表没用,毕竟数组还贼简单呢.谁敢说数组没用?栈栈的理论 是一个先进后出的结构,类似于堆盘子,先放到地上的盘子最后被取走(默认只能取走一个...

    2019/5/22 更新,将颠倒的Push和Pop方法更正,并更换图片。
    栈是数据结构中较为简单的结构体,是一种操作收到限制的线性表.但简单不代表没用,毕竟数组很简单.但谁敢说数组没用呢?

    栈的理论

    • 栈是一个先进后出的结构,类似于堆盘子,先放到地上的盘子最后被取走(默认只能取走一个盘子)
    • 栈其实就是操作受限的线性表,只有一个口,每一次操作时,这个口可以当出口也可以当入口.
    • 例如:水桶,注入水时,水桶的头当做入口,倒水时,水桶的头当做出口

    栈的图解.

    在图解之前,先举一个例子,让大家记住栈 : 栈其实就是吃了一顿饭,然后吐出来.

    • 这是一个空栈,只有上面是入口和出口
      在这里插入图片描述

    • 放入一个元素a

    在这里插入图片描述

    • 接着依次放入B,C元素

    在这里插入图片描述

    • 取出一个元素,由栈只有一个口的特点可以知道取出了C

    在这里插入图片描述

    • 再次放入一个元素D

    在这里插入图片描述

    栈的可用操作

    根据理论环节,可以轻易的看出:栈的基本操作只有两个:

    • 入栈
    • 出栈

    而且样子长得十分像一个水桶。

    但是如果栈已经放满了,就像水桶装满了水一样,不能再放水了,即不能再进行入栈操作,所以要在每次入栈前判断栈满的情况.同理,出栈之前,栈中必须有数据,不然就出现要么空指针,要么野指针.都不是我们想要的结果,所以出栈前要判断栈空,.
    所有一个栈一共有四个功能:

    • 入栈(英文名:push)
    • 判(栈)满(isFull)
    • 出栈(pop)
    • 判(栈)空(isEmpty)

    栈的C语言定义(结构体)

    开篇就说了栈是操作收到限制的线性表,而众所周知的线性表主要有:
    1.顺序存储的数组,
    优点: 节省空间, 操作简单,学习成本较低,易于理解.
    缺点: 栈的大小一开始就声明’死’了,不利于使用.
    2.非顺序存储的链表.
    优缺点:与数组栈正好相反.

    两种栈各有好处,争论是愚蠢的,学习是学不完的,所以赶快开始coding吧

    数组栈

    数组栈,顾名思义,就是基于数组的栈,也是说把一个数组的强大的下标功能阉割掉,并且只能从一头进入(数组头明显更为方便)
    所以结构体为:
    (为了方便学习,存储类型统一使用int,但是我们一般更习惯在头文件下面给int 起一个别名,原因很简单:这样就这样实现简单的多态,需要将int类型栈改成char类型栈时,只需要改定义的别名中的类型即可)

    typedef struct
    {
        int Data[MaxSize];   // 存储元素的数组
        int topIdx;       //栈顶指针
    }SeqStack;
    

    栈的四个基本操作定义:

    //return 0 为false,1为true(下同)
    // 将元素推入栈中
    int Push(SeqStack &L, int e)
    { // 栈已满
    	if(L.topIdx==MaxSize -1)
        {
            return 0;
        }
        // 加入栈中
        L.Data[L.topIdx++] = e;
        // 返回自身
        return e;
    }
    // 移除栈顶元素
    int Pop(SeqStack &L)
    {	// 栈空
         if(L.topIdx == 0)
        {
             //返回失败
             return 0;
        }
        // 打印并返回栈
        int val = L.Data[--L.topIdx];
        printf("%d ",val);
        return val;
    }
    //判断栈s是否为空
    int isEmpty(SeqStack s)
    {
        // 如果下标在0,说明栈中无元素
        if(s.topIdx != 0)
        {
            return 1;
        }
        return 0;
    }
    // 判断栈是否已栈.
    Status isFull(SeqStack s)
    {
        // 已满返回true(1)
        if(s.topIdx != MaxSize -1)//之前的定义数组的最大值的下标
        {
            return 1;
        }
        return 0;
    }
    

    链表栈

    结构体

    typedef struct LNode
    {
        ElemType data;
        struct LNode * next;
    } LNode,*LinkList;
    

    两大功能(链表无需判满,判空也简单,不再单独实现)

    Status Pop(LinkList L)
    {
        if(L->next == NULL)
        {
            return 0;
        }
        LinkList tem = L->next;
        printf("%d ",tem->data);
        L->next = tem->next;
        free(tem);
        return 1;
    }
    Status Push(LinkList L, ElemType e)
    {
        LinkList newNode = (LinkList) malloc(sizeof(LinkList));
        newNode->data = e;
        newNode->next = L->next;
        L->next = newNode;
        return 1;
    }
    

    最后写几个简单的作业(我们老师留给我们的)以及我的代码

    //1、本题要求实现顺序栈,写出Push 、Pop、StackEmpty函数的实现,并用一个简单的main函数测试。
    
    //已有类型定义
    typedef struct
    {
        ElementType Data[MaxSize];   // 存储元素的数组
        Position Top;       //栈顶指针
    }SeqStack;
    
    //函数接口定义:
    Status Push(SeqStack &L, ElemType e);
    Status Pop(SeqStack &L, ElemType &e);
    Status StackEmpty(SeqStack s);  //判断栈s是否为空
    //其中 L 和 e 都是用户传入的参数。 L 是带头结点的头指针; e 是数据元素。
    /**
    * 3、进制转换。
    * 输入一个十进制正整数n和一个目标进制R(1<R<10),将n转换为R进制。要求不使用递归或数组,而使用第1题* 或第2题中定义的栈来实现。 
    */ 
    
    

    我的代码实现:

    #include <stdio.h>
    #include <stdlib.h>
    #define MaxSize 100
    typedef int Status;
    typedef int ElemType;
    typedef int Position;
    //1、本题要求实现顺序栈,写出Push 、Pop、StackEmpty函数的实现,并用一个简单的main函数测试。
    //已有类型定义
    typedef struct
    {
        ElemType Data[MaxSize];   // 存储元素的数组
        Position Top;       //栈顶指针
    } SeqStack;
    
    //函数接口定义:
    Status Push(SeqStack &L,ElemType e);
    Status Pop(SeqStack &L);
    Status StackEmpty(SeqStack s);  //判断栈s是否为空
    Status prinStack(SeqStack &L);
    Status convNum(int n, int R);
    Status pipei();
    void work1();
    //其中 L 和 e 都是用户传入的参数。 L 是带头结点的头指针; e 是数据元素。
    int main()
    {
        //work1();//第一题
        //convNum(8,2);//进制转化
        pipei();
        return 0;
    }
    Status prinStack(SeqStack &L)
    {
        while (StackEmpty(L))
        {
            Push(L);
        }
        return 1;
    }
    void work1()
    {
        SeqStack L;
        L.Top = 0;
        Pop(L, 1);
        Pop(L, 2);
        Pop(L, 3);
        prinStack(L);
    }
    Status Pop(SeqStack &L)
    {
    if(L.Top == 0)
        {
            return 0;
        }
        printf("%d ",L.Data[--L.Top]);
        return 1;
    }
    Status Push(SeqStack &L, ElemType e)
    {
            if(L.Top==MaxSize -1)
        {
            return 0;
        }
        L.Data[L.Top++] = e;
        return 1;
    }
    //判断栈s是否为空
    Status StackEmpty(SeqStack s)
    {
        if(s.Top != 0)
        {
            return 1;
        }
        return 0;
    }
    //3、进制转换。
    //输入一个十进制正整数n和一个目标进制R(1<R<10),将n转换为R进制。要求不使用递归或数组,而使用第1题或第2题中定义的栈来实现。
    Status convNum(int n, int R)
    {
        //声明栈
        SeqStack L;
        L.Top = 0;
        while (n!=0)
        {
            //将每次产生的余数防入栈低
            Pop(L, n%R);
            n/=R;
        }
        prinStack(L);
        return 1;
    }
    

    以下附上Java 代码实现的栈

    public class LinkedStack<T> {
        private Node topNode;
    
        public T push(T newEntry) {
            Node newNode = new Node<T>(newEntry, topNode);
            topNode = newNode;
            T tempData = peek();
            return tempData;
        }
    
        public T pop() {
            T tempData = peek();
            if (tempData == null) {
                return null;
            }
            topNode = topNode.next;
            return tempData;
        }
    
        public T peek() {
            if (isEmpty()) {
                return null;
            }
            return (T) topNode.data;
        }
    
        public boolean isEmpty() {
            return topNode == null;
        }
    
        public void clear() {
            topNode = null;
            // java拥有内存回收,只需要让头结点引用为空即可,GC就可以回收掉所有其他节点。
        }
    
        public LinkedStack() {
            this.topNode = null;
        }
    
        private class Node<T> {
            private T data;
            private Node next;
    
            public Node(T dataPortion) {
                this(dataPortion, null);
            }
    
            public Node(T data, Node next) {
                super();
                this.data = data;
                this.next = next;
            }
    
            public T getData() {
                return data;
            }
    
            public void setData(T data) {
                this.data = data;
            }
    
            public Node getNext() {
                return next;
            }
    
            public void setNext(Node next) {
                this.next = next;
            }
    
        }
    }
    
    展开全文
  • [数据结构与算法]

    2019-06-23 09:04:42
    既可以通过数组实现,也可以通过链表来实现。不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。 你应该可以看出来,这 K 次入栈操作,总共涉及了 K 个数据的搬移,以及 K 次 simple-push操作。将 ...

    栈既可以通过数组实现,也可以通过链表来实现。不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。

      你应该可以看出来,这 K 次入栈操作,总共涉及了 K 个数据的搬移,以及 K 次 simple-push操作。将 K 个数据搬移均摊到 K 次入栈操作,那每个入栈操作只需要一个数据搬移和一个simple-push 操作。以此类推,入栈操作的均摊时间复杂度就为 O(1)。通过这个例子的实战分析,也印证了前面讲到的,均摊时间复杂度一般都等于最好情况时间复杂度。因为在大部分情况下,入栈操作的时间复杂度 O 都是 O(1),只有在个别时刻才会退化为O(n),所以把耗时多的入栈操作的时间均摊到其他入栈操作上,平均情况下的耗时就接近 O(1)。


      栈在函数调用中的应用

    栈作为一个比较基础的数据结构,应用场景还是蛮多的。其中,比较经典的一个应用场景就是函数调用栈。

    我们知道,操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。为了让你更好地理解,我们一块来看下这段代码的执行过程。

    从代码中我们可以看出,main() 函数调用了 add() 函数,获取计算结果,并且与临时变量 a 相加,最后打印 res 的值。为了让你清晰地看到这个过程对应的函数栈里出栈、入栈的操作,我画了一张图。图中显示的是,在执行到 add() 函数时,函数调用栈的情况。


    栈在表达式求值中的应用

    我们再来看栈的另一个常见的应用场景,编译器如何利用栈来实现表达式求值。
    为了方便解释,我将算术表达式简化为只包含加减乘除四则运算,比如:34+13*9+44-12/3。对于这个四则运算,我们人脑可以很快求解出答案,但是对于计算机来说,理解这个表达式本身就是个挺难的事儿。如果换作你,让你来实现这样一个表达式求值的功能,你会怎么做呢?
    实际上,编译器就是通过两个栈来实现的。其中一个保存操作数的栈,另一个是保存运算符的栈。我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较

    如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较

    我将 3+5*8-6 这个表达式的计算过程画成了一张图,你可以结合图来理解我刚讲的计算过程。


    栈在括号匹配中的应用


    除了用栈来实现表达式求值,我们还可以借助栈来检查表达式中的括号是否匹配。

    我们同样简化一下背景。我们假设表达式中只包含三种括号,圆括号 ()、方括号 [] 和花括号{},并且它们可以任意嵌套。比如,{[{}]}或 [{()}([])] 等都为合法格式,而{[}()] 或 [({)] 为不合法的格式。那我现在给你一个包含三种括号的表达式字符串,如何检查它是否合法呢?
    这里也可以用栈来解决。我们用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如“(”跟“)”匹配,“[”跟“]”匹配,“{”跟“}”匹配,则继续扫描剩下的字符串。如果扫描的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式
    当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式。


    实现浏览器的前进和后退功能
     

    当你依次访问完一串页面 a-b-c 之后,点击浏览器的后退按钮,就可以查看之前浏览过的页面b 和 a。当你后退到页面 a,点击前进按钮,就可以重新查看页面 b 和 c。但是,如果你后退到页面 b 后,点击了新的页面 d,那就无法再通过前进、后退功能查看页面 c 了。

    如何实现浏览器的前进、后退功能?其实,用两个栈就可以非常完美地解决这个问题。

    我们使用两个栈,X 和 Y,我们把首次浏览的页面依次压入栈 X,当点击后退按钮时,再依次从栈 X 中出栈,并将出栈的数据依次放入栈 Y。当我们点击前进按钮时,我们依次从栈 Y 中取出数据,放入栈 X 中。当栈 X 中没有数据时,那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据,那就说明没有页面可以点击前进按钮浏览了。
    比如你顺序查看了 a,b,c 三个页面,我们就依次把 a,b,c 压入栈,这个时候,两个栈的数据就是这个样子:

    当你通过浏览器的后退按钮,从页面 c 后退到页面 a 之后,我们就依次把 c 和 b 从栈 X 中弹出,并且依次放入到栈 Y。这个时候,两个栈的数据就是这个样子:

    这个时候你又想看页面 b,于是你又点击前进按钮回到 b 页面,我们就把 b 再从栈 Y 中出栈,放入栈 X 中。此时两个栈的数据是这个样子:

    这个时候,你通过页面 b 又跳转到新的页面 d 了,页面 c 就无法再通过前进、后退按钮重复查看了,所以需要清空栈 Y。此时两个栈的数据这个样子:


    内存中的堆栈和数据结构堆栈不是一个概念,可以说内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象的数据存储结构。
    内存空间在逻辑上分为三部分:代码区、静态数据区和动态数据区,动态数据区又分为栈区和堆区。
    代码区:存储方法体的二进制代码。高级调度(作业调度)、中级调度(内存调度)、低级调度(进程调度)控制代码区执行代码的切换。
    静态数据区:存储全局变量、静态变量、常量,常量包括final修饰的常量和String常量。系统自动分配和回收。
    栈区:存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
    堆区:new一个对象的引用或地址存储在栈区,指向该对象存储在堆区中的真实数据。
     


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

    有效字符串需满足:

    1. 左括号必须用相同类型的右括号闭合。
    2. 左括号必须以正确的顺序闭合。

    注意空字符串可被认为是有效字符串。

    class Solution {
    public:
        bool isValid(string s) {
            if(s.size()==0){
                return true;
            }
            
            std::stack<char> sc;
            
            for(const auto &c: s){
                if(c=='(' || c=='[' || c=='{'){
                    sc.push(c);
                }else if(c==')' || c==']' || c=='}'){
                    if(sc.size()==0){
                        return false;
                    }
                    
                    switch (c){
                        case ')':
                            if(sc.top()!='('){
                                return false;
                            }
                            sc.pop();
                            break;
                        case ']':
                            if(sc.top()!='['){
                                return false;
                            }
                            sc.pop();
                            break;
                        case '}':
                            if(sc.top()!='{'){
                                return false;
                            }
                            sc.pop();
                            break;
                        default:
                            return false;
                    }
                }else{
                    return false;
                }       
            }
            
            return sc.size()==0 ? true:false;
        }
    };
    class Solution {
    public:
        Solution(){
            mappings.insert({ {')','('}, {']','['}, {'}','{'} }); //init list
        }
        
        bool isValid(string s) {
            if(s.size()==0){
                return true;
            }
            
            std::stack<char> sc;
            
            for(const auto &c: s){
                std::unordered_map<char,char>::const_iterator got = mappings.find(c);
                if(got == mappings.end()){
                    sc.push(c);
                }else{
                    if(sc.empty()){
                        return false;
                    }
                    char topchar = sc.top();
                    sc.pop();
                    if(topchar != got->second){
                        return false;
                    }
                }        
            }
            
            return sc.empty() ? true: false;
            
        }
        
    private:
        std::unordered_map<char, char> mappings;
        
    };

    设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

    • push(x) -- 将元素 x 推入栈中。
    • pop() -- 删除栈顶的元素。
    • top() -- 获取栈顶元素。
    • getMin() -- 检索栈中的最小元素。

    示例:

    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.getMin();   --> 返回 -2.
    class MinStack {
    public:
        /** initialize your data structure here. */
    	MinStack() {
    		this->count = 0;
    		this->head = new LinkedNode();
    	}
    
    	~MinStack() {
    		LinkedNode *ptr, *temp;
    		ptr = head;
    		while (ptr->next != nullptr) {
    			temp = ptr->next;
    			ptr->next = temp->next;
    			delete temp;
    		}
    
    		delete head;
    		head = nullptr;
    		count = 0;
    	}
    
    	void push(int x) {
    		LinkedNode *insertNode = new LinkedNode();
    		insertNode->data = x;
    		insertNode->next = head->next;
    		head->next = insertNode;
    		this->count++;
    	}
    
    	void pop() {
    		if (count == 0 || head->next == nullptr) {
    			return;
    		}
    		else {
    			LinkedNode *temp = head->next;
    			head->next = temp->next;
    			delete temp;
    			this->count--;
    		}	
    	}
    
    	int top() {
    		if (count == 0 || head->next == nullptr) {
    			return -1;
    		}
    		else {
    			return head->next->data;
    		}
    
    
    	}
    
    	int getMin() {
    		LinkedNode *temp = head->next;
    		int min = temp->data;
    		while (temp->next != nullptr) {
    			temp = temp->next;
    			if (temp->data < min) {
    				min = temp->data;
    			}
    		}
    
    		return min;
    	}
    
    private:
    	int count; //存放栈的大小,因为是单链表所以这里不规定栈的最大可承载量
    
    	struct LinkedNode
    	{
    		int data;
    		LinkedNode * next;
    		LinkedNode() : data(0), next(nullptr) {}
    	};
    
    	LinkedNode *head; // 哨兵节点
    };
    
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */

    使用栈实现队列的下列操作:

    • push(x) -- 将一个元素放入队列的尾部。
    • pop() -- 从队列首部移除元素。
    • peek() -- 返回队列首部的元素。
    • empty() -- 返回队列是否为空。

    示例:

    MyQueue queue = new MyQueue();
    
    queue.push(1);
    queue.push(2);  
    queue.peek();  // 返回 1
    queue.pop();   // 返回 1
    queue.empty(); // 返回 false

    说明:

    • 你只能使用标准的栈操作 -- 也就是只有 push to toppeek/pop from topsize, 和 is empty 操作是合法的。
    • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
    • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。
    class MyQueue {
    public:
        /** Initialize your data structure here. */
        MyQueue() {
            
        }
        
        /** Push element x to the back of queue. */
        void push(int x) {
            while(!s2.empty()){
                s1.push(s2.top());
                s2.pop();
            }
            s1.push(x);
            while(!s1.empty()){
                s2.push(s1.top());
                s1.pop();
            }
            
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() {
            int a = s2.top();
            s2.pop();
            return a;
        }
        
        /** Get the front element. */
        int peek() {
            return s2.top();
        }
        
        /** Returns whether the queue is empty. */
        bool empty() {
            return s2.empty();
        }
    
    private:
        //用两个栈来实现,使用两个栈互相入栈出栈来取得头或者尾的元素。
        std::stack<int> s1, s2;
        
    };
    
    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue* obj = new MyQueue();
     * obj->push(x);
     * int param_2 = obj->pop();
     * int param_3 = obj->peek();
     * bool param_4 = obj->empty();
     */

    给定 S 和 T 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。

    示例 1:

    输入:S = "ab#c", T = "ad#c"
    输出:true
    解释:S 和 T 都会变成 “ac”。

      示例 2:

    输入:S = "ab##", T = "c#d#"
    输出:true
    解释:S 和 T 都会变成 “”。

    示例 3:

    输入:S = "a##c", T = "#a#c"
    输出:true
    解释:S 和 T 都会变成 “c”。

    示例 4:

    输入:S = "a#c", T = "b"
    输出:false
    解释:S 会变成 “c”,但 T 仍然是 “b”。

    提示:

    1. 1 <= S.length <= 200
    2. 1 <= T.length <= 200
    3. S 和 T 只含有小写字母以及字符 '#'
    class Solution {
    public:
        bool backspaceCompare(string S, string T) {
            for(const auto &c : S){
                if(c!='#'){
                    ss.push(c);
                }else{
                    if(!ss.empty()){
                        ss.pop();
                    } 
                }
            }
            
            for(const auto &c : T){
                if(c!='#'){
                    st.push(c);
                }else{
                    if(!st.empty()){
                        st.pop();
                    }
                }
            }
            
            if(ss.size()!=st.size()){
                return false;
            }else{
                int length = ss.size();
                if(length == 0)
                    return true;
                
                while(length>0){
                    char c1 = ss.top();
                    char c2 = st.top();
                    if(c1!=c2){
                        return false;
                    }
                    ss.pop();
                    st.pop();
                    length--;
                }
                
                return true;
            }
            
            return true;
        }
        
    private:
        std::stack<char> ss, st;
    };

    你现在是棒球比赛记录员。
    给定一个字符串列表,每个字符串可以是以下四种类型之一:
    1.整数(一轮的得分):直接表示您在本轮中获得的积分数。
    2. "+"(一轮的得分):表示本轮获得的得分是前两轮有效 回合得分的总和。
    3. "D"(一轮的得分):表示本轮获得的得分是前一轮有效 回合得分的两倍。
    4. "C"(一个操作,这不是一个回合的分数):表示您获得的最后一个有效 回合的分数是无效的,应该被移除。

    每一轮的操作都是永久性的,可能会对前一轮和后一轮产生影响。
    你需要返回你在所有回合中得分的总和。

    示例 1:

    输入: ["5","2","C","D","+"]
    输出: 30
    解释: 
    第1轮:你可以得到5分。总和是:5。
    第2轮:你可以得到2分。总和是:7。
    操作1:第2轮的数据无效。总和是:5。
    第3轮:你可以得到10分(第2轮的数据已被删除)。总数是:15。
    第4轮:你可以得到5 + 10 = 15分。总数是:30。

    示例 2:

    输入: ["5","-2","4","C","D","9","+","+"]
    输出: 27
    解释: 
    第1轮:你可以得到5分。总和是:5。
    第2轮:你可以得到-2分。总数是:3。
    第3轮:你可以得到4分。总和是:7。
    操作1:第3轮的数据无效。总数是:3。
    第4轮:你可以得到-4分(第三轮的数据已被删除)。总和是:-1。
    第5轮:你可以得到9分。总数是:8。
    第6轮:你可以得到-4 + 9 = 5分。总数是13。
    第7轮:你可以得到9 + 5 = 14分。总数是27。

    注意:

    • 输入列表的大小将介于1和1000之间。
    • 列表中的每个整数都将介于-30000和30000之间。
    class Solution {
    public:
        Solution(): m_ss({"+","D","C"}) {}
        
        int calPoints(vector<string>& ops) {
            if(ops.size()==0){
                return 0;
            }
            
            for(const auto &str : ops){
                if(m_ss.find(str)==m_ss.end()){
                    //该字符串对应的是一个整数,将字符串转int型有两个方法
                    //使用C标准库里面的atoi;  使用C++标准库里面的stringstream。
                    std::stringstream strstream;
                    int score;
                    strstream<<str;
                    strstream>>score;
                    
                    m_stack.push(score);
                    
                }else{
                    if(str.compare("+")==0){
                        if(m_stack.size()>=2){
                            int last1 = m_stack.top();
                            m_stack.pop();
                            int last2 = m_stack.top();
                            m_stack.push(last1);
                            m_stack.push(last1+last2);
                        }else{
                            if(!m_stack.empty()){
                                m_stack.push(m_stack.top());
                            }else{
                                m_stack.push(0);
                            }
                        }
                    }else if(str.compare("D")==0){
                        if(!m_stack.empty()){
                            m_stack.push(2*m_stack.top());
                        }else{
                            m_stack.push(0);
                        }
                    }else if(str.compare("C")==0){
                        if(!m_stack.empty()){
                            m_stack.pop();
                        }
                    }
                }   
            }
            
            int sum = 0;
            while(!m_stack.empty()){
                sum += m_stack.top();
                m_stack.pop();
            }
            
            return sum;
        }
                   
    private:
        std::unordered_set<string> m_ss;
        std::stack<int> m_stack;
    };

    给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

    nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出-1。

    示例 1:

    输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
    输出: [-1,3,-1]
    解释:
        对于num1中的数字4,你无法在第二个数组中找到下一个更大的数字,因此输出 -1。
        对于num1中的数字1,第二个数组中数字1右边的下一个较大数字是 3。
        对于num1中的数字2,第二个数组中没有下一个更大的数字,因此输出 -1。

    示例 2:

    输入: nums1 = [2,4], nums2 = [1,2,3,4].
    输出: [3,-1]
    解释:
        对于num1中的数字2,第二个数组中的下一个较大数字是3。
        对于num1中的数字4,第二个数组中没有下一个更大的数字,因此输出 -1。

    思路:通过Stack、Map解决

    1. 先遍历大数组nums2,首先将第一个元素入栈;
    2. 继续遍历,当当前元素小于栈顶元素时,继续将它入栈;当当前元素大于栈顶元素时,栈顶元素出栈,并将该出栈的元素与当前元素形成key-value键值对,存入Map中, 并继续重复比较下一个栈顶元素和当前元素,按同样操作处理,直到当前元素小于等于栈顶时将当前元素入栈。
    3. 当遍历完nums2后,得到nums2中元素所对应的下一个更大元素的map;
    4. 遍历nums1的元素在Map中去查找‘下一个更大元素’,当找不到时则为-1。
    class Solution {
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
            vector<int> res(nums1.size(), -1);
            for(const auto &num : nums2){
                while(!m_stack.empty() && m_stack.top()<num){
                    m_map.insert(std::make_pair(m_stack.top(),num));
                    m_stack.pop();
                }
                m_stack.push(num);
            }
            
            for(int i=0; i<nums1.size(); i++){
                auto ite = m_map.find(nums1.at(i));
                if(ite!=m_map.end()){
                    res[i] = ite->second;
                }else{
                    res[i] = -1;
                }
            }
            
            return res;
        }
        
    private:
        std::unordered_map<int, int> m_map;
        std::stack<int> m_stack;
    };

     

    实现一个基本的计算器来计算一个简单的字符串表达式的值。

    字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,乘号*, 除号/, 非负整数和空格  

    示例 1:

    输入: "1 + 1"
    输出: 2

    示例 2:

    输入: " 2-1 + 2 "
    输出: 3

    示例 3:

    输入: "(1+(1+2*3)+5*6+1)"
    输出: 39

     

      如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,重复这个操作直到比运算符栈顶元素的优先级高为止。再把计算完的结果压入操作数栈,继续比较。

      对于带括号的情况,左括号直接压入运算符栈,当遇到右括号时,开始从操作数栈取操作数并从运算符栈取运算符进行运算,重复这个操作直到运算符栈的下一个运算符是左括号为止。

      注意点: 连续数字的处理  括号的处理   输入字符串全部是数字的情况  输入字符串中的符号只有括号和数字的情况

     

    class Solution {
    public:
        Solution(): Operator_priority({ {'(',0}, {')',0}, {'+',1},{'-',1},{'*',2},{'/',2} }) {}
        
        //执行一次从运算符栈取操作符,从操作数栈取操作数进行运算并将结果入操作数栈的操作
        bool process_once(){
            int num1 = s1.top();
            s1.pop();
            int num2 = s1.top();
            s1.pop();
    
            //取出运算符
            char opera = s2.top();
            s2.pop();
            switch (opera){
                case '+':
                    s1.push(num1+num2);
                    break;
                case '-':
                    s1.push(num2-num1);
                    break;
                case '*':
                    s1.push(num2*num1);
                    break;
                case '/':
                    if(num1==0)
                        return false;
                    s1.push(num2/num1);
                    break;
                default:
                    return false;
            }
            
            return true;
        }
        
    	int calculate(string s) {
    		//记录用户是否输入过运算符
    		bool has_input_ope = false;
    
    		for (int i = 0; i < s.length(); ++i) {
    			char c = s.at(i);
    
    			//跳过空格
    			if (c == ' ')
    				continue;
    
    			if (isdigit(c)) {
    				//注意连续数字的情况
    				int len = 0;
    				for (int j = i; j < s.length(); j++) {
    					if (s[j] >= '0' && s[j] <= '9')
    						len++;
    					else
    						break;
    				}
    				string num_str = s.substr(i, len);
    				int num = atoi(num_str.c_str());
    				s1.push(num);
    
    				//注意要令i跳过相应数字的个数
    				i = i + len -1;
    			}
    			else {
    				has_input_ope = true;
    
    				if (s2.empty()) {
    					s2.push(c);
    					continue;
    				}
    				else {
    					//运算符栈中已经有运算符了
    					//首先判断当前运算符是不是括号
    					auto ite1 = Operator_priority.find(c);
    
    					//如果是括号
    					if (ite1->second == 0) {
    						if (c == '(') {
    							s2.push(c);
    							continue;
    						}
    						else if (c == ')') {
    							//重复操作直到运算符栈顶为左括号
    							while (s2.top() != '(') {
    								if (!process_once())
    									return -1; //除数为0或者输入非法,返回-1
    							}
    							//把左括号也取出来
    							s2.pop();
    						}
    
    						continue; //注意如果不是下面的不放在else语句里面,则这里一定要用continue
    					}
    
    					//当前运算符不是括号
    					int prio_cur = ite1->second;
    					auto ite2 = Operator_priority.find(s2.top());
    					int prio_top = ite2->second;
    					//如果比运算符栈顶元素的优先级高
    					if (prio_cur > prio_top) {
    						//直接将当前运算符入栈
    						s2.push(c);
    					}
    					else {
    						while (prio_cur <= ite2->second) {
    							if (!process_once())
    								return -1; //除数为0或者输入非法,返回-1
    
    							if (s2.empty())
    								break;
    							ite2 = Operator_priority.find(s2.top());
    						}
    
    						s2.push(c);
    					}
    				}
    			}
    		}
    
    
    		//如果用户没有输入过运算符
    		if (!has_input_ope) {
    			//那么用户输入的字符串中只有数字,没有运算符,则直接返回用户输入的字符串对应的数据
    			return atoi(s.c_str());
    		}
    
    		while (!s2.empty()) {
    			if (!process_once())
    				return -1; //除数为0或者输入非法,返回-1
    		}
    
    		return s1.top();
    	}
        
    private:
        std::stack<int> s1; //数据栈
        std::stack<char> s2; //运算符栈
        std::unordered_map<char, int> Operator_priority;//运算符优先级map
        
    };

     

    展开全文
  • 【线性表】

    2018-12-11 22:29:07
    一、的定义 二、如何实现一个 1、数组实现 2、链表实现 三、的应用场景 1、使用来反转表或集合 2、括号匹配   一、的定义 是一种“操作受限”的线性表。的主要操作有2个:入栈(在栈顶...

    目录

    一、栈的定义

    二、如何实现一个栈

    1、数组实现

    2、链表实现

    三、栈的应用场景

    1、使用栈来反转表或集合

    2、括号匹配

     

    一、栈的定义

    栈:栈是一种“操作受限”的线性表。栈的主要操作有2个:入栈(在栈顶插入一个数据)、出栈(在栈顶删除一个数据)。

    受限一定不好吗?

    非也。从功能上来说,数组/链表可以替代栈,但它们暴露了太多的操作接口,使用时不可控;此外,特定的结构是对特定的场景的抽象,正是因为现实中有某种特殊场景,我们才提出栈这种特殊的结构。

      âçå­å¾çâçå¾çæç´¢ç»æ   âç½ççç­ å¾çâçå¾çæç´¢ç»æ

    那么,什么时候适合使用栈呢?

    当某个数据集合只涉及在一端插入、删除数据,并且满足后进先出、先进后出的特性时,就可以使用栈。

    二、如何实现一个栈

    栈结构有两种实现方式:数组、链表。

    采用数组比较方便,但需要考虑栈的最大容量的问题,大小没有取一个合适的值,既可能申请过多空间造成浪费,又可能使用过程中栈空间不足。后者可以采用动态扩容数组来缓解一下。

    而采用链表无需考虑容量问题,不过因为每个数据多了个地址域,所以一般消耗内存空间更多。

    两种方式没有绝对的好坏,需要视情况而定。有时要用空间换取时间上的高效,有时则尽可能节省空间,跑得慢一点无所谓。

    下面的表格是各种栈的push、pop操作的时间复杂度。其中,动态数组栈在大部分时间做push操作时,都只需常量时间。而当数组满了之后,再做push时,则申请一个更大的数组(一般是原来数组的大小的2倍),然后把原数组的数据都搬过去。这时的时间与原数组的最大容量n相关,即,时间为c*n。但是,由于我们是经过n-1次常数级别的push操作之后,才碰到一次n的一次方级别的操作,所以我们可以把n的一次方级别的push所花的时间,均摊给其他n-1次push操作。这么一来,总体的push操作的时间复杂度仍然是O(1)。这种方法叫做均摊分析法。

      数组栈 链栈 动态数组栈
    push操作       O(1)  O(1)       O(1)
    pop操作       O(1)  O(1)       O(1)

    1、数组实现

    class Stack {
    	private int[] arr;
    	private int top = -1;
    	private int capacity = 5;
    	
    	public Stack() {
    		this.arr = new int[capacity];// 默认的话则创建大小为5的栈
    	}
    	public Stack(int n) {
    		this.arr = new int[n]; // 创建栈时,指定栈的大小
    		this.capacity = n;
    	}
    	
    	// Push
    	public void push(int x) {
    		if (top == capacity - 1) {
    			System.out.println("栈空间不足,压栈失败!");
    		}
    		arr[++top] = x;
    	}
    	
    	// Pop
    	public int pop() {
    		if (top == -1) {
    			System.out.println("栈为空栈,弹栈失败!");
    			return -10000;
    		}
    		return top--;  //注意:我们只是让top往下移而已,事实上该数据还是在原来的位置,只是我们认为它不在逻辑的栈内部。
    	}
    	
    	// 判断栈是否为空
    	public boolean isEmpty() {
    		if (top == -1) {
    			return true;
    		}
    		return false;
    	}
    	
    	// 查看栈顶的元素
    	public int top() {
    		if (top == -1) {
    			System.out.println("栈为空栈,没有栈顶元素");
                            return -10000;
    		}
    		return arr[top];
    	}
    	
    	// 打印、查看栈的所有元素
    	public void printAll() {
    		System.out.print("Stack:  ");
    		for (int i=top; i>=0; i--) {
    			System.out.print(arr[i]+"  ");
    		}
    		System.out.println();
    	}
    }
    
    public class StackTest {
    	public static void main(String[] args) {
    		Stack stack1 = new Stack();
    		Stack stack2 = new Stack(3);
    		
    		//1、
    		stack1.printAll();
    		stack2.printAll();
    		stack1.pop(); // 检查空栈执行pop操作时 是否报错
    		stack2.pop();
    		
    		//2、
    		System.out.print("\n======================================\n");
    		for (int i=0; i<5; i++) {
    			stack1.push(1);
    		}
    		for (int i=0; i<3; i++) {
    			stack2.push(2);
    		}
    		stack1.printAll();
    		stack2.printAll();
    		stack1.push(100); // 检查满栈执行push操作时 是否报错
    		stack2.push(200);
    		
    	}
    }

    注意上面的pop()中,我们只是让top往下移而已,事实上该数据还是在原来的位置,并没有被销毁,只是我们认为它不在逻辑的栈内部而已。如,下面有个空栈,当我们将2、10、5依次push进去后,执行一次pop操作时,5仍然在标号为2的位置,只不过它再也不是栈中的元素了。由此,我们也可以看出,在数组实现的栈中,top的作用是非常关键的。它起到一个边界的作用,在top之内都是栈的空间,在top之外则不是(至于我们申请栈时,指定的空间大小capacity,其实并不是栈的空间大小,而是栈所能达到的最大空间)。top与栈的各种操作紧密联系。

    测试结果如下面所示:

    2、链表实现

    如果采用链表来实现栈的话,由于没有空间限制,我们在做push操作时,就不用再考虑栈是否满的问题了。所以只需要考虑栈为空的问题。

    class StackNode {
    	public int data;
    	public StackNode next;
    	
    	public StackNode() {
    	}
    	public StackNode(int data) {
    		this.next = null;
    		this.data = data;
    	}
    }
    
    class StackBasedOnLinkList {
    	StackNode head = null;// 头引用
    	public int count = 0; // 计数栈的元素个数
    	
    	StackBasedOnLinkList() {
    	}
    	
    	// push
    	public void push(int data) {
    		StackNode node = new StackNode(data);
    		//采用头插法 插入数据
    		node.next = head;
    		head = node;
    		count = count + 1;
    	}
    	
    	// pop
    	public int pop() {
    		if (head == null) {
    			System.out.println("栈为空,弹栈失败");
    			//
    			return -10000;
    		}
    		StackNode p = head;
    		head = head.next;
    		//让要删除的结点p 地址域为null,指向它的引用也为null   这样就可以被垃圾回收器回收了
    		int data = p.data;
    		p.next = null;
    		p = null;   
    		count = count - 1;
    		return data;
    	}
    	
    	// 判断栈是否为空
    	public boolean isEmpty() {
    		if (head == null) { // 判断条件可改为 count == 0
    			return true;
    		}
    		return false;
    	}
    	
    	// 查看栈顶的元素
    	public int top() {
    		if (head == null) {
    			System.out.println("栈为空栈,没有栈顶元素");
    			return -10000;
    		}
    		return head.data;
    	}
    	
    	// 打印、查看栈的所有元素
    	public void printAll() {
    		StackNode pointer = head;  // 新建一个遍历引用,否则head跑到后面,就不便于以后的操作了
    		System.out.print("Stack:  ");
    		while (pointer != null) {
    			System.out.print(pointer.data+"  ");
    			pointer = pointer.next;
    		}
    		System.out.println();
    	}
    }
    
    public class LinkedStackTest {
    	public static void main(String[] args) {
    		StackBasedOnLinkList stack = new StackBasedOnLinkList();
    		
    		//1、
    		stack.printAll();
    		//stack.pop(); 
    		stack.pop();
    		
    		//2、
    		System.out.println();
    		for (int i=0; i<5; i++) {
    			stack.push(i);
    		}
    		stack.printAll();
    		stack.pop();
    		stack.printAll();
    		System.out.println(stack.top());
    	}
    }

    输出结果如下图所示:

    有三个地方需要注意:

    (1)在上面Stack类的push()、pop()中,我们都是在头部插入、删除一个元素,为什么不采用尾插法在尾部插入、删除元素呢?

    这是因为,我们采用的链表是普通的单链表(只带头引用,而没有尾引用),在头部操作由于有头引用,我们的push、pop操作的时间复杂度都为O(1)。而如果在尾部操作的话,由于没有尾引用,我们需要从头遍历到尾部,这样push、pop操作的时间复杂度就变为O(n)了。

    (2)在上面Stack类的printAll()中,我们新建一个引用StackNode pointer = head,然后利用它来遍历整个栈(整条链)。这么做的原因是:栈的绝大部分操作都是围绕栈顶(在数组栈中是top下标,在链栈中是head引用),数组栈中遍历栈的操作printAll()并不会改变top值,而在链栈如果我们用head来遍历,那么遍历完成时head将指向栈中最里面的元素,而我们以后还要经常用指向栈顶的head引用完成各种操作,这样就得不偿失了。所以我们用一个新的引用来代替head引用去遍历。

    写到这里,我突然想到,现实中也有很多这种遍历的场景。比如军训时教官从一排队伍的队头检阅到队尾,这就类似printAll中一个引用不断跑到不同的元素那里。还有,地铁安检时人们排着队通过安检、做纸带实验时纸带通过打点计时器、生产流水线,这些则与前面的场景有所不同:负责检查、打点的部分是静止不动的。但是归根结底,这两种遍历的场景本质上是相同的。

    (3)在Stack类的pop()中,如果我们不返回弹栈时的值,则可以这么写。注意判空之外的其他代码要写在else代码块,否则有可能报出空引用异常。

    public void pop() {
    	if (head == null) {
    		System.out.println("栈为空,弹栈失败");
    	} else {
    		StackNode p = head;
    		head = head.next;
    
    		p.next = null;
    		p = null;   
    		count = count - 1;
    	}
    }

    三、栈的应用场景

    栈可以应用到诸多场景:(1)函数调用、递归(其实是特殊的函数调用);(2)编辑器、浏览器的撤销操作;(3)括号匹配

    下面举几个例子。

    1、使用栈来反转表或集合

    (1)反转字符串(顺序结构)

    初始字符串为“HELLO”,则逆转后的字符串为“OLLEH”。ReverseString类中有两个逆转方法,其中reverseString()采用栈结构(利用其先进后出的特性),reverseString1()采用传统的遍历方法,将首末对应位置的两个元素进行对换。

    import java.util.Stack;
    
    public class ReverseString {
    	public static void main(String[] args) {
    		String string1 = new String("HELLO"); 
    		System.out.println("初始字符串: "+string1);
    		string1 = reverseString(string1);
    		System.out.println("反转后的字符串: "+string1);
    		
    		System.out.println("\n===========================\n");
    		System.out.println("初始字符串: "+string1);
    		string1 = reverseString1(string1);         // 两次逆转,得到最初的字符串
    		System.out.println("反转后的字符串: "+string1);
    	}
    
    	public static String reverseString(String str) {
    		Stack<Character> stack = new Stack<Character>();
    		String str1 = "";
    		for (int i=0; i<str.length(); i++) {
    			stack.push(str.charAt(i));
    		}
    		for (int i=0; i<str.length(); i++) {
    			str1 += stack.pop();
    		}
    
    		return str1;
    	}
    	
    	public static String reverseString1(String str) {
    		char[] arr;
    		arr = str.toCharArray();
    		
    		char temp;
    		for (int i=0; i<arr.length/2; i++) {
    			temp = arr[i];
    			arr[i] = arr[arr.length-i-1];  
    			arr[arr.length-i-1] = temp;
    		}
    		str = new String(arr);
    		
                    return str;
    	}
    }

    输出结果如下图所示,两次逆转之后,字符串变为初始字符串“HELLO”

    (2)反转链表(链式结构)

    初始链表为:1,2,3,4,5 逆转之后为5,4,3,2,1

    import java.util.Stack;
    
    class Node {
    	public int data;
    	public Node next;
    	
    	public Node() {}
    	public Node(int data) {
    		this.data = data;
    		this.next = null;
    	}
    	
    	// 打印链表的所有元素 形参传入的是头结点
    	public static void printAll(Node node) {
    		while(node.next != null) {
    			System.out.print(node.next.data+"  ");
    			node = node.next;
    		}
    	}
    }
    
    public class ReverseLinkedList {
    	public static void main(String[] args) {
    		Node head = new Node();     // 头结点 不含数据
    		for (int i=5; i>=1; i--) {  // 采用头插法,创建一个带头结点的链表:1,2,3,4,5,null
    			Node node = new Node(i);
    			node.next = head.next;
    			head.next = node;
    		}
    		
    		System.out.print("初始链表:  ");
    		Node.printAll(head);
    		System.out.print("\n反转后的链表:  ");
    		head = reverseLinkedList(head);
    		Node.printAll(head);
    	}
    	
    	public static Node reverseLinkedList(Node head) {
    		//Stack<Node> stack = new Stack<Node>();
    		Stack<Node> stack = new Stack<>();
    		
    		if (head.next == null) {   // 如果是空链表,则直接返回null
    			return null;
    		}
    		
    		Node temp = head;
    		while (temp.next != null) {
    			stack.push(temp.next);
    			temp = temp.next;
    		}
    		Node temp2 = head;
    		while (!stack.isEmpty()) { //如果栈不为空,则不断弹栈
    			Node node = stack.pop();
    			temp2.next = node;
    			temp2 = temp2.next;
    			node.next = null;
    		}
    		return head;
    	}
    }
    

    输出结果如下图所示:

    小结:利用栈反转字符串(顺序结构),比较适合那种字符串长度较短、对时间空间使用不敏感的场景。比如上面的reverseString1()方法,我们采用传统的方式(首末对应位置数据交换)的循环只需遍历 n/2次(n是字符串长度),而采用栈的方式,则需要遍历n次。

    而利用栈反转链表,则比较整洁直观,效率也比较高。

    2、括号匹配

    读入一个表达式(字符串形式),判断表达式中的括号是否按照()、{}、[]严格匹配

    我们用字符栈实现,主要利用栈的先进后出特性,步骤如下:

    新建一个字符栈,从头到尾一一读取各个位置的字符

    (1)若该字符是左括号(、{、[,则压入栈;

    (2)若该字符是右括号,

            1)判断栈是否为空栈,若是则提示“该字符串的括号没有匹配”;若否,则将栈顶元素弹栈

            2)判断弹出的栈顶元素是否与该字符匹配,若是则提示“该字符串匹配成功”;否则提示“该字符串的括号没有匹配”

    import java.util.Stack;   // 这里使用jdk自带的栈
    import java.util.Scanner;  
    
    public class BalanceParentheses {
    	public static void main(String[] args) {
    		
    		String string1 = new String("{(1+2)*5+[100*1]}");
    		areParanthesesBalanced(string1);
    		
    		System.out.println();
    		System.out.println();
    		
    		String string2 = new String("{(1+2)*5+]100*1[}");
    		areParanthesesBalanced(string2);
    		
            // 控制台输入第三个表达式 
    		Scanner scan = new Scanner(System.in);
    		String string3;
    		string3 = scan.next();
    		areParanthesesBalanced(string3);
    	}
    	
        // 判断两个括号是否匹配
    	public static boolean arePair(char opening, char closing) {
    		if ( opening=='(' && closing==')' ) {
    			return true;
    		} else if ( opening=='{' && closing=='}' ) {
    			return true;
    		} else if ( opening=='[' && closing==']' ) {
    			return true;
    		} else {
    			return false;
    		}
    	}
    	
        // 判断字符串是否匹配
    	public static boolean areParanthesesBalanced(String expression) {
    		Stack<Character> stack = new Stack<Character>();
    		for (int i=0; i<expression.length(); i++) {
    			if ( expression.charAt(i)=='(' || expression.charAt(i)=='{' || expression.charAt(i)=='[' ) {
    				stack.push(expression.charAt(i));
    			}
    			if ( expression.charAt(i)==')' || expression.charAt(i)=='}' || expression.charAt(i)==']' ) {
    				if( stack.isEmpty() || arePair(stack.pop(), expression.charAt(i)) == false ) {
    					System.out.println("表达式不匹配!");
    					return false;
    				}
    			}
    		}
    		if ( stack.isEmpty() ) {
    			System.out.println("表达式匹配");
    			return true;
    		} else {
    			System.out.println("表达式不匹配");
    			return false;
    		}
    	}
    }

    运行结果如下所示:

     

    展开全文
  • 是一种特殊的线性表—-操作受限的线性表。有两种存储方式,即线性存储和链接存储(链表)。的一个最重要的特征就是的插入和删除只能在栈顶进行,所以每次删除的元素都是最后进栈的元素,故也被称为后进先...

    在这里插入图片描述
    栈是一种操作受限的线性表只允许从一端插入和删除数据。栈有两种存储方式,即线性存储和链接存储(链表)。栈的一个最重要的特征就是栈的插入和删除只能在栈顶进行,所以每次删除的元素都是最后进栈的元素,故栈也被称为后进先出(LIFO)表。每个栈都有一个栈顶指针,它初始值为-1,且总是指向最后一个入栈的元素,栈有两种处理方式,即进栈(push)和出栈(pop),因为在进栈只需要移动一个变量存储空间,所以它的时间复杂度为O(1),但是对于出栈分两种情况,栈未满时,时间复杂度也为O(1),但是当栈满时,需要重新分配内存,并移动栈内所有数据,所以此时的时间复杂度为O(n)。以下举例栈结构的两种实现方式,线性存储和链接存储。
    这里写图片描述

    1、线性存储
    线性存储的方式和线性表基本一致,只不过多了后进先出的限制而已,它是静态分配的,即使用前,它的内存就已经以数组的形式分配好了,所以在初始化时,需要指明栈的节点最大个数。

    #include "stdafx.h"
    #include <iostream>  
    #include <new>  
       
    //定义  
    template<class T>  
    class LineStack  
    {  
    public :  
        LineStack(int MaxListSize=10);  //构造函数
        ~LineStack()                             //析构函数 
        {
            delete[] elements;
        }  
      
        bool IsEmpty() const             //判断是否为空
        {
            return top==-1;
        }  
    
        bool IsFull() const               //判断是否满
        {
            return top==MaxSize-1;
        }  
    
        T pop(); //出栈 
    
        int push(const T& data);  //进栈
    
        T getPop();  //获取栈顶元素值
    
        void clear();  //清空栈
    
        void print() ;  
      
    private:  
        int top;  //栈顶指针
        int MaxSize;  //数组最大长度
        T *elements;//一维动态数组  
      
    };  
    
    //实现...  
    template<class T>  
    LineStack<T>::LineStack(int MaxListSize)  
    {   
        //基于公式的线性表的构造函数  
        MaxSize = MaxListSize;  
        elements = new T[MaxSize];  
        top = -1;  
    }  
      
    template<class T>  
    T LineStack<T>::pop()  
    {  
        if(IsEmpty()) 
        {
            return NULL;  
        }
    
        return elements[top--];  
    }  
      
    template<class T>  
    int LineStack<T>::push(const T& data)  
    {  
        if(IsFull())
        {
            return -1;
        }
        else
        {
            elements[++top] = data;
        }
    
        return 0;  
    }  
      
      
    template<class T>  
    T LineStack<T>::getPop()  
    {  
        if(IsEmpty()) 
        {
            return NULL;  
        }
    
        return elements[top]; 
    }  
      
    template<class T>  
    void LineStack<T>::clear()  
    {  
        top = -1;
        return true;  
    }  
      
    template<class T>  
    void LineStack<T>::print()  
    {  
        for(int i=0;i<=top;i++)
        {
            std:: cout<<elements[i]<<"   ";  
        }
    }  
     
    void LineStackSample()  
    {  
        int j;
        int a = 10,b = 20,c = 30,d = 40;
    
        LineStack<int> S(10);  
        std::cout<<"IsFull  = "<<S.IsFull()<<std::endl;  
        std::cout<<"IsEmpty = "<<S.IsEmpty()<<std::endl;  
      
        S.push(a);
        S.push(b);
        S.push(c);
        S.push(d);
    
        j = S.pop();
        std::cout<<j<<std::endl;
        j = S.pop();
        std::cout<<j<<std::endl;
        j = S.pop();
        std::cout<<j<<std::endl;
        j = S.pop();
        std::cout<<j<<std::endl;
    
        return;
    }  
    
    int main(int argc, _TCHAR* argv[])  
    {  
        LineStackSample();  
      
        //暂停操作  
        char str;  
        std::cin>>str;  
        //程序结束  
        return 0;  
    }  
    
    

    运行结果如下:
    这里写图片描述

    2、链接存储
    实际上只要对单链表类做适当的修改,限制其插入、删除、修改和访问结点的行为,使其符合栈先进后出的规则即可,另外需要单独提供栈访问的接口函数,例如进栈、出栈、获取栈大小等,链表知识可以参考https://blog.csdn.net/Chiang2018/article/details/82730174。

    // 栈动态.cpp : 定义控制台应用程序的入口点。
    //
    
    // 单链表.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <stdlib.h>
    #include <iostream>
    
    template <class T>
    class Node
    {
    public:
        T data;
        Node(T& item);
        Node<T>* next;
    };
    
    template<class T>
    class LinkList
    {
    public:
        LinkList();
        ~LinkList();
        int getSize(void);
        bool IsEmpty(void);
        int gotoNext(void);
        int getPostion(void);
        int InsertNode(T& data);
        int DeleteNode(void);
        void getCurrNodeData(T& data);
        void setCurrNodeData(T& data);
        void clear();
        void print();
    
    private:
        Node<T>* head;
        Node<T>* currNode;
        int size;
        int position;
        void freeNode(Node<T>* p);
    };
    
    /* 链表节点构造函数 */
    template <class T>
    Node<T>::Node(T& item)
    {
        data = item;
        next = NULL;
    }
    
    /* 链表构造函数 */
    template <class T>
    LinkList<T>::LinkList()
    {
        head = NULL;
        currNode = NULL;
        size = 0;
        position = -1;
    }
    
    /* 链表析构函数 */
    template <class T>
    LinkList<T>::~LinkList()
    {
        clear();
    }
    
    /* 获取链表长度 */
    template <class T>
    int LinkList<T>::getSize(void)
    {
        return size;
    }
    
    /* 判断链表是否为空 */
    template <class T>
    bool LinkList<T>::IsEmpty(void)
    {
        return size==0?true:false;
    }
    
    /* 移动到下个节点,返回下个节点的位置值 */
    template <class T>
    int LinkList<T>::gotoNext(void)
    {
        if(NULL == head)
        {
            return -1;
        }
    
        if(NULL == currNode)
        {
            return -1;
        }
        else
        {
            currNode = currNode->next;
            position++
        }
    
        return position;
    }
    
    /* 获取当前节点的位置 */
    template <class T>
    int LinkList<T>::getPostion(void)
    {
        return position;
    }
    
    /* 在当前节点前插入新节点 */
    template <class T>
    int LinkList<T>::InsertNode(T& data)
    {
        Node<T>* p = new Node<T>(data);
    
        if(0 == size)
        {
            head = p;
            head->next = NULL;
            currNode = p;
        }
        else
        {
            p->next = currNode->next;
            currNode->next = p;
            currNode = p;
        }
    
        size++;
        position++;
        return size;
    }
    
    
    /* 删除当前节点 */
    template <class T>
    int LinkList<T>::DeleteNode(void)
    {
        if(0 == size)
        {
            return -1;
        }
        
        Node<T>* p = head;
        Node<T>* tmp;
        for(int i = 0;i < size;i++)
        {
            if(NULL == p)
            {
                return -1;
            }
    
            if(p->next == currNode)
            {
                p->next = currNode->next;
                break;
            }
    
            p = p->next;
        }
    
        tmp = currNode;
    
        if(currNode == head)
        {
            head = currNode->next;
        }
    
        if(NULL == currNode->next)
        {
            position--;
            currNode = p;
        }
        else
        {
            currNode = currNode->next;
        }
        
    
        freeNode(p);
        size--;
        if(0 == size)
        {
           position = -1;
        }
    
        return 0;
    }
    
    /* 释放指定节点的内存 */
    template <class T>
    void LinkList<T>::freeNode(Node<T>* p)
    {
        if(!p)
        {
            delete p;
        }
    
        return;
    }
    
    /* 获取当前节点的数据 */
    template <class T>
    void LinkList<T>::getCurrNodeData(T& data)
    {
        if(currNode)
        {
            data = currNode->data;
        }
    
        return ;
    }
    
    /* 修改当前节点的数据 */
    template <class T>
    void LinkList<T>::setCurrNodeData(T& data)
    {
        if(currNode)
        {
            currNode->data = data;
        }
    
        return ;
    }
    
    /* 清空链表 */
    template <class T>
    void LinkList<T>::clear()
    {
        if(0 == size)
        {
            return;
        }
    
        Node<T>* p = head;
        Node<T>* tmp = head->next;
        while(p)
        {
            freeNode(p);
            p = tmp;
            if(tmp)
            {
                tmp = tmp->next;
            }
        }
    
        head = NULL;
        currNode = NULL;
        size = 0;
        position = -1;
    
        return;
    }
    
    template <class T>
    void LinkList<T>::print()
    {
        if(0 == size)
        {
            return;
        }
    
        Node<T>* p = head;
        Node<T>* tmp = head->next;
        while(p)
        {
            std::cout<<p->data<<std::endl;
            p = tmp;
            if(tmp)
            {
                tmp = tmp->next;
            }
        }
    
        return;
    }
    template <class T>
    class LinkedStack
    {
    private:
        LinkList<T>* link;
    public:
        LinkedStack();
        void push(T& data);
        T pop();
        void ClearStack();
        int getSize();
        bool isEmpty();
    };
    template <class T>
    LinkedStack<T>::LinkedStack()
    {
        link = new LinkList<T>;
    }
    template <class T>
    bool LinkedStack<T>::isEmpty()
    {
        return link->IsEmpty();
    }
    template <class T>
    int LinkedStack<T>::getSize()
    {
        return link->size;
    }
    
    template <class T>
    void LinkedStack<T>::ClearStack()
    {
        link->clear();
    }
    template <class T>
    void LinkedStack<T>::push(T& data)
    {
        link->InsertNode(data);
    }
    
    template <class T>
    T LinkedStack<T>::pop()
    {
        T tmp;
        if(isEmpty())
        {
            return NULL;
        }
        
        link->getCurrNodeData(tmp);
    
        link->DeleteNode();
    
        return tmp; 
    }
    
    int main(int argc, _TCHAR* argv[])
    {
        int j = 0;
        int a = 10,b=20,c=30,d=40,e=50;
        LinkedStack<int> list;
    
        list.push(a);
       
        list.push(b);
        list.push(c);
        list.push(d);
        list.push(e);
    
        j = list.pop();
        std::cout<<j<<std::endl;
    
        j = list.pop();
        std::cout<<j<<std::endl;
    
        j = list.pop();
        std::cout<<j<<std::endl;
    
        j = list.pop();
        std::cout<<j<<std::endl;
    
        j = list.pop();
        std::cout<<j<<std::endl;
    
        std::cin.get();
    	return 0;
    }
    

    运行结果是:
    这里写图片描述在这里插入图片描述

    展开全文
  • 的作用

    2016-06-06 20:56:17
    的作用 计算机里面的其实有着举足轻重的作用。大学刚学c语言的时候,教的是堆栈,传达的是一种后入先出的算法思想。但其实我们知道,堆和是两个截然不同的东西。而这里面说到的,则是更融入到计算机系统...
  • 深入理解堆与

    2020-02-19 13:45:34
    1、用于维护函数调用的上下文,离开函数调用就会无法实现。通常在用户空间的最高地址处分配,通常有数兆字节。 2、堆:堆用来容纳应用程序动态分配的内存区域,我们使用malloc 或者new分配内存时,得到...
  • seid=6709590585276522157 一 算法: : 数据进出,类向箱子放东西和拿东西,先进后出...分为静态和动态两种,静态用数组实现, 动态用链表实现。算法 出栈 入栈(压栈),遍历,清空。 1.创建 ...
  • C++数据结构——

    2020-04-21 23:25:47
    C++数据结构—— 最近计划再复习一遍数据结构,看到一篇博客:https://www.cnblogs.com/QG-whz/p/5170418.html#_label0。 1、(Stack)是一种线性存储结构,它具有如下特点: ...
  • 算法浅谈:

    2018-01-26 05:20:48
    所以说掌握了”“的使用,对我们学习算法还是很有帮助的。   一: 概念  ,同样是一种特殊的线性表,是一种Last In First Out(LIFO)的形式,现实中有很多这样的例子,  比如:食堂中的一叠盘子,我们只能从...
  • 什么是

    2019-05-08 10:57:59
    什么是? ps:文章来自于网络 当提及“”这个概念,很多初学者都会很迷茫。在C语言里,我们有一个内存区域叫做区。在单片机里,我们又常常听到一个操作叫做压栈。而在算法中,我们也有一个同名结构叫做。 ...
  • 与堆栈的区别

    2019-03-06 13:56:02
    和堆栈是一个概念。 队列先进先出,在队头做删除操作,在队尾做插入操作。 先进后出,在栈顶做插入和删除操作。 堆和它们不同,不存在是先进后出还是先进先出。 1.(Stack)是操作系统在建立某个进程时或者...
  • 也是一种特殊的线性表,但不同的是,的操作与传统的线性表不同。传统的线性表可以完成随机位置存取,而的结构决定了它进行操作的特点:仅仅在表尾进行插入或删除操作(后进先出)。表尾端称作栈顶,而与之相对...
  • 小猪的数据结构辅助教程——3.1 与队列中的顺序标签(空格分隔): 数据结构本节学习路线图与学习要点学习要点 1.与队列的介绍,栈顶,底,入栈,出栈的概念 2.熟悉顺序的特点以及存储结构 3.掌握...
  • 小猪的数据结构辅助教程——3.2 与队列中的链栈标签(空格分隔): 数据结构1.本节引言: 嗯,本节没有学习路线图哈,因为我们一般都用的是顺序,链栈还是顺带提一提吧, 因为只是栈顶来做插入和删除操作...
  • 堆与的区别

    2019-10-30 15:37:44
    堆(Heap)与(Stack)是开发人员必须面对的两个概念,在理解这两个概念时,需要放到具体的场景下,因为不同场景下,堆与代表不同的含义。一般情况下,有两层含义: (1)程序内存布局场景下,堆与表示的是...
  • 堆和的概念和区别

    2017-04-27 19:55:34
    在说堆和之前,我们先说一下JVM(虚拟机)内存的划分:  Java程序在运行时都要开辟空间,任何软件在运行时都要在内存中开辟空间,Java虚拟机运行时也是要开辟空间的。JVM运行时在内存中开辟一片内存区域,启动时...
  • 作为一个有着 8 年 Java 编程经验的 IT 老兵,说起来很惭愧,我被 Java 当中的四五个名词一直困扰着:**对象、引用、堆、、堆栈**(可同堆栈,因此是四个名词,也是五个名词)。每次我看到这几个名词,都隐隐...
  • 一、预备知识—程序的内存分配 一个由C/C++编译的程序占用的内存分为以下几个部分 1、区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其 操作方式类似于数据结构中的。 2、堆区...
  • 顺序/链式

    2018-04-09 00:30:44
    是是一种限定性的线性表,它将线性表的插入和删除限定为仅在表的一端进行。将表中允许插入和删除的一端成为栈顶。所以栈顶的位置是不断动态变化的。它具有“后进先出”的特点。因为是由线性表实现的,所以,有...
1 2 3 4 5 ... 20
收藏数 1,008,654
精华内容 403,461
关键字: