编程之美：队列中的最大最小值-白红宇

编程之美：队列中的最大最小值

阅读量：5360 次

发布时间：2019-06-15

本文共 3911 字，大约阅读时间需要 13 分钟。

#include "iostream"#include "memory.h"#include "stdio.h"#include "limits.h"typedef int Type;const int MAXN=15;const int MIN=INT_MIN;class stack{public:    stack()    {        stacktop=-1;        maxItemIndex=-1;    }    void push(Type x)    {        ++stacktop;        if (stacktop>=MAXN)            ;        else        {            stackItem[stacktop]=x;            if (x>maxItem())            {                link2NextMaxItem[stacktop]=maxItemIndex;                maxItemIndex=stacktop;            }            else link2NextMaxItem[stacktop]=-1;        }    }    Type pop()    {        if (stacktop<0)            ;        else        {            Type x=stackItem[stacktop];            if (maxItemIndex==stacktop)            {                maxItemIndex=link2NextMaxItem[stacktop];            }            --stacktop;            return x;        }    }    Type maxItem()    {        if (maxItemIndex>=0)        {            return stackItem[maxItemIndex];        }        else return MIN;    }    Type empty()    {        return stacktop==-1;    }private:    Type stackItem[MAXN];    Type link2NextMaxItem[MAXN];    Type maxItemIndex;    Type stacktop;};class Queue{public:    inline Type max(Type x,Type y)    {        return x>y?x:y;    }    Type deque()    {        if (stackOut.empty())        {            while (!stackIn.empty())                stackOut.push(stackIn.pop());        }        return stackOut.pop();    }    void inque(Type x)    {        stackIn.push(x);    }    Type maxItem()    {        return max(stackIn.maxItem(),stackOut.maxItem());    }private:    stack stackIn,stackOut;};int main(int argc, char const *argv[]){    Queue q;    q.inque(3);    printf("%d\n", q.maxItem());        q.inque(2);    printf("%d\n", q.maxItem());    q.deque();    q.inque(1);    printf("%d\n", q.maxItem());        stack s;    s.push(3);    printf("%d\n", s.maxItem());            s.push(2);    printf("%d\n", s.maxItem());    s.pop();        s.push(1);    printf("%d\n", s.maxItem());        return 0;}

push(Type x)    {        ++stacktop;        if (stacktop>=MAXN)            ;        else        {            stackItem[stacktop]=x;            if (x>maxItem())            {                link2NextMaxItem[stacktop]=maxItemIndex;                maxItemIndex=stacktop;            }            else link2NextMaxItem[stacktop]=-1;        }    }    Type pop()    {        if (stacktop<0)            ;        else        {            Type x=stackItem[stacktop];            if (maxItemIndex==stacktop)            {                maxItemIndex=link2NextMaxItem[stacktop];            }            --stacktop;            return x;        }    }    Type maxItem()    {        if (maxItemIndex>=0)        {            return stackItem[maxItemIndex];        }        else return MIN;    }    Type empty()    {        return stacktop==-1;    }private:    Type stackItem[MAXN];    Type link2NextMaxItem[MAXN];    Type maxItemIndex;    Type stacktop;};class Queue{public:    inline Type max(Type x,Type y)    {        return x>y?x:y;    }    Type deque()    {        if (stackOut.empty())        {            while (!stackIn.empty())                stackOut.push(stackIn.pop());        }        return stackOut.pop();    }    void inque(Type x)    {        stackIn.push(x);    }    Type maxItem()    {        return max(stackIn.maxItem(),stackOut.maxItem());    }private:    stack stackIn,stackOut;};int main(int argc, char const *argv[]){    Queue q;    q.inque(3);    printf("%d\n", q.maxItem());        q.inque(2);    printf("%d\n", q.maxItem());    q.deque();    q.inque(1);    printf("%d\n", q.maxItem());        stack s;    s.push(3);    printf("%d\n", s.maxItem());            s.push(2);    printf("%d\n", s.maxItem());    s.pop();        s.push(1);    printf("%d\n", s.maxItem());        return 0;}

代码与思路见原书236页

简单的来说：求队列中的最大值过程由两部分组成

1.求取栈的最大值

2.用栈模拟队列

转载于:https://www.cnblogs.com/mintmy/p/4199284.html

你可能感兴趣的文章

Luogu P1141 01迷宫【搜索/dfs】By cellur925