queue for max elem, pop, push
个人信息:就读于燕大本科软件工程专业 目前大三;
本人博客:google搜索“cqs_2012”即可;
个人爱好:酷爱数据结构和算法,希望将来从事算法工作为人民作出自己的贡献;
博客内容:queue for max elem, pop, push;
博客时间:2014-4-15;
编程语言:C++ ;
编程坏境:Windows 7 专业版 x64;
编程工具:vs2008 32位编译器;
制图工具:office 2010 ppt;
硬件信息:7G-3 笔记本;
my words
problemDon‘t let shorts beat you, because it doesn‘t worth.
my solutionmake a queue for max elem, pop and push.(problem from beauty from programming)
require fast for getting max elem
two stacks can make true a queue.
sub-problem
ok, my solution for queue max elem followsgetting max elem for the stack is so easy with dp.
my solution for my stack with max elem follows
name of type for elem is int
class Stack_mine { // assume: the data length is not so long, its length <= the max number of int int * data ; int length; int * table; public: // constructor function Stack_mine() { length = 0; data = new int[LENGTH]; table = new int[LENGTH]; } // function: pop int _pop() { if( ! _empty() ) { length--; return data[length]; } else { cout<<"pop error"<<endl; return -1; } } // function: return length int _length( ) { return length; } // function: push void _push(int a) { int * p1,*p2; if(length >= LENGTH) { p1 = (int *)realloc(data,LONGLENGTH * sizeof(int)); p2 = (int *)realloc(table,LONGLENGTH * sizeof(int)); data = p1; table = p2; } data[length] = a; if( length == 0 || data[ table[length-1] ] < a ) table[length] = length; else table[length] = table[length-1]; length ++; } // function: empty bool _empty() { if(length>0) return false; else return true; } // function: max int _max() { if(! _empty()) return data[ table[ length-1 ] ]; cout<<"error: empty stack for _max"<<endl; return -1; } };
class Queue_mine { Stack_mine s1; Stack_mine s2; public: Queue_mine(){}; // function: push void _push(int a) { s1._push(a); }; // function: pop int _pop() { if(s2._empty()) { while(!s1._empty()) { s2._push(s1._pop()); } } return s2._pop(); } // function: length int _length() { return s1._length() + s2._length(); } bool _empty() { if( s1._empty() && s2._empty() ) { return true ; } else return false ; } int _max() { if(! s1._empty() && ! s2._empty()) return ( s1._max() > s2._max() ? s1._max() : s2._max() ); else if( ! s1._empty() && s2._empty()) return s1._max(); else if( s1._empty() && ! s2._empty() ) return s2._max(); else { cout<<"empty for queue"<<endl; return -1; } } };
queue for max elem, pop, push,布布扣,bubuko.com
原文:http://blog.csdn.net/cqs_experiment/article/details/24890349