什么是单调栈?

硅谷探秘者 3065 0 0

对于栈,一般来讲是先进后出。而所谓 单调栈 则是在栈的 先进后出 基础之上额外添加一个特性:从栈顶到栈底的元素是严格递增(or递减)

那么具体的进栈过程如下:

1.对于单调递增栈,若当前进栈元素为 e,从栈顶开始遍历元素,把小于 e 或者等于 e 的元素弹出栈,直接遇到一个大于 e 的元素或者栈为空为止,然后再把 e压入栈中。
2.对于单调递减栈,则每次弹出的是大于 e 或者等于 e 的元素。

案例:

3,1,2,9,7,6,8,4依次入栈情形如下


image.png


代码示例:c#描述

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            MonotonousStack m = new MonotonousStack();
            m.push(3);
            m.push(1);
            m.push(2);
            m.push(9);
            m.push(7);
            m.push(6);
            m.push(8);
            m.push(4);
            int a;
            Console.Write("栈中剩余数据:");
            while ((a=m.pop())!=0)
            {
                Console.Write(a+" ");
            }

            Console.Read();
        }
    }

    //单调栈,基于链表实现
    class MonotonousStack
    {
        public int count;//节点总数
        public Node first;//头节点
        public Node last;//尾节点
        //添加函数
        public void push(int t)
        {
            while (first != null && first.t < t)//检查栈顶元素是否大于插入元素
            {
                int a = first.t;
                int p = pop();
                Console.WriteLine(a+"出栈");
            }
            if (first == null)//空栈
            {
                first = new Node(t);
                last = first;
            }
            else//非空
            {
                Node node = new Node(t);
                node.next = first;
                first.prev = node;
                first = node;
            }
            Console.WriteLine(t + "进栈");
            count++;
        }
        
        /**
         * 获取并删除第一个元素
         * **/
        public int pop()
        {
            Node fir = first;
            if (first != null)//栈中还有元素
            {
                count--;//元素数量减一
                if (first == last)//栈中只有一个元素
                {
                    last = null;
                    first = last;
                    return fir.t;
                }
                else//栈中不止一个元素
                {
                    first = first.next;
                    fir.next = null;
                    first.prev = null;
                    return fir.t;
                }
            }
            else
            {
               return  0;
            }
        }
    }
    //节点类
    class Node
    {
        public Node next;//指向下一个节点
        public Node prev;//指向下一个节点
        public int t;//数据
        public Node(int t)
        {
            this.t = t;
            next = null;
            prev = null;
        }
    }
}



评论区
请写下您的评论...
暂无评论...
猜你喜欢
official 557   BeanFactory一种“Spring容器”,BeanFactory翻译过来就Bean工厂,顾名思义,它可以用来创建Bean、获取Bean,BeanFactorySpring中非常核心的
official 621 ,BeanDefinitionSpring中非常核心的概念。BeanDefinition定义Bean的配置元信息接口,包含:Bean的类名设置父bean名称、否为primary、Bean行为配置信息,作用域、自动绑定模式
算法基础 862 Varint一种紧凑的表示数字的方法。它用一个或多个字节来表示一个数字,值越小的数字使用越少的字节数。这能减少用来表示数字的字节数。比如对于int32类型的数字,一般需要4个byte来表示。但
算法基础 1163 一、protobuf?在移动互联网时代,手机流量、电量最为有限的资源,而移动端的即时通讯应用无疑必须得直面这两点。解决流量过大的基本方法就使用高度压缩的通信协议,而数据压缩后流量减小带来的
official 580   Bean生命周期描述的Spring中一个Bean创建过程和销毁过程中所经历的步骤,其中Bean创建过程重点。程序员可以利用Bean生命周期机制对Bean进行自定义加工。
java基础 1581 1.先看一下线程的生命周期转换图(学java的此图必背)本篇文章的主要目的不分析线程的各种状态之间的转换,而主要研究一下线程之间的通讯机制,以及Object的wait方法和notify方法。所以
official 704 《操作系统》系统用?有作用操作系统作为用户和计算机硬件之间的接口,需要向上提供一些简易用的服务。主要包括命令接口和程序接口。其中,程序接口由一组系统用组成。“系统用”操作系统提供
weblog 4158 从计算机程序出现的第一天起,对效率的追求就程序天生的信仰,这个过程犹如一场没有终点,永不停歇的F1方程式竞赛,程序员车手,技术平台则在赛道上飞驰的赛车。---深入理解java虚拟机现在
归档
2018-11  12 2018-12  33 2019-01  28 2019-02  28 2019-03  32 2019-04  27 2019-05  33 2019-06  6 2019-07  12 2019-08  12 2019-09  21 2019-10  8 2019-11  15 2019-12  25 2020-01  9 2020-02  5 2020-03  16 2020-04  4 2020-06  1 2020-07  7 2020-08  13 2020-09  9 2020-10  5 2020-12  3 2021-01  1 2021-02  5 2021-03  7 2021-04  4 2021-05  4 2021-06  1 2021-07  7 2021-08  2 2021-09  8 2021-10  9 2021-11  16 2021-12  14 2022-01  7 2022-05  1 2022-08  3 2022-09  2 2022-10  2 2022-12  5 2023-01  3 2023-02  1 2023-03  4 2023-04  2 2023-06  3 2023-07  4 2023-08  1 2023-10  1 2024-02  1 2024-03  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy srs 音视频 webrtc javascript
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。