什么是单调栈?

2019 精帖
0 1546

对于栈,一般来讲是先进后出。而所谓 单调栈 则是在栈的 先进后出 基础之上额外添加一个特性:从栈顶到栈底的元素是严格递增(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;
        }
    }
}


留言(0)
加载更多
猜你喜欢