首页 > 代码库 > 编程之美：队列中的最大最小值
编程之美：队列中的最大最小值
#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.用栈模拟队列
编程之美：队列中的最大最小值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。