首页 > 代码库 > 编程之美——队列中取最大值操作
编程之美——队列中取最大值操作
为实现O(1)的时间复杂度完成取队列中最大元素，使用maxStackItemIndex记录队列（使用两个栈实现）中最大元素下标，使用数组link2NextMaxItem[]记录数组中次大值的下标，这也就是使用两个栈（先进后出）模拟队列二不是直接使用队列（先进先出）的原因：先进后出可以保证当执行pop操作（pop出最大值）时可以更新maxStackItemIndex=link2NextMaxItem[stackTop]；而队列则不具有这种回溯特性；
代码：
1 #include<iostream> 2 using namespace std; 3 const int INF=10000; 4 const int MAXN=100; 5 6 class maxStack 7 { 8 private: 9 int stackItem[MAXN]; 10 int stackTop; 11 int link2NextMaxItem[MAXN]; //记录栈中第二大数字的下标 12 int maxStackItemIndex; //记录站中最大数字下标 13 14 public: 15 maxStack() 16 { 17 stackTop=-1; 18 maxStackItemIndex=-1; 19 } 20 21 void push(int x); 22 int pop(); 23 int max() 24 { 25 if(maxStackItemIndex>=0) 26 return stackItem[maxStackItemIndex]; 27 else 28 return -INF; 29 } 30 bool empty() 31 { 32 return stackTop==-1; 33 } 34 }; 35 36 void maxStack::push(int x) 37 { 38 ++stackTop; 39 if(stackTop>MAXN) 40 //throw new Exception("stack is full!"); 41 cout<<"stack is full!"<<endl; 42 else 43 { 44 stackItem[stackTop]=x; 45 if(x>max()) 46 { 47 //更新过程 48 link2NextMaxItem[stackTop]=maxStackItemIndex; 49 maxStackItemIndex=stackTop; 50 } 51 else 52 link2NextMaxItem[stackTop]=-1; 53 } 54 } 55 56 int maxStack::pop() 57 { 58 if(stackTop==-1) 59 //throw new Exception("stack is empty!"); 60 cout<<"stack is empty!"<<endl; 61 62 int value=http://www.mamicode.com/stackItem[stackTop]; 63 if(value=http://www.mamicode.com/=max()) 64 { 65 //回溯第二大数字下标 66 maxStackItemIndex=link2NextMaxItem[stackTop]; 67 } 68 --stackTop; 69 return value; 70 } 71 72 //使用两个栈模拟队列 73 class maxQueue 74 { 75 private: 76 maxStack A,B; 77 public: 78 void enQueue(int x) 79 { 80 B.push(x); 81 } 82 int deQueue() 83 { 84 if(A.empty()) 85 while(!B.empty()) 86 A.push(B.pop()); 87 return A.pop(); 88 } 89 int maxValue() 90 { 91 return A.max()>B.max() ? A.max():B.max(); 92 } 93 }; 94 95 int main() 96 { 97 maxQueue queue; 98 for(int i=5;i>0;--i) 99 queue.enQueue(i);100 for(int i=0;i<5;++i)101 {102 cout<<queue.maxValue()<<ends;103 queue.deQueue();104 }105 return 0;106 }
上面是以栈为基础构造队列实现O(1)的取队列中最小元素，当然也可以直接使用队列实现，这里使用效率较高的循环队列；
具体：若入对元素大于队尾元素，则将队尾元素弹出，入队，这样可以保证队尾元素始终为最大值，直接返回即可；
代码：
1 #include<iostream> 2 using namespace std; 3 4 class maxQueue 5 { 6 private: 7 int *queueItem; 8 int front,rear; 9 int maxSize;10 public:11 maxQueue(int size=5)12 {13 queueItem=new int[size];14 maxSize=size;15 front=rear=1;16 }17 int rearValue()18 {19 return queueItem[rear];20 }21 void doubleSpace();22 void enQueue(int x);23 int deQueue();24 int maxValue()25 {26 return queueItem[front];27 }28 bool isEmpty()29 {30 return front==rear;31 }32 ~maxQueue()33 {34 delete [] queueItem;35 }36 };37 38 void maxQueue::enQueue(int x)39 {40 if((rear+1)%maxSize==front)41 doubleSpace();42 43 while(x>=rearValue())44 {45 --rear;46 }47 rear=(rear+1)%maxSize;48 queueItem[rear]=x;49 }50 51 int maxQueue::deQueue()52 {53 if(front==rear)54 cout<<"the queue is empty"<<endl;55 56 int value=http://www.mamicode.com/queueItem[front];57 front=(front+1)%maxSize;58 return value;59 }60 61 void maxQueue::doubleSpace()62 {63 int *tmp=queueItem;64 65 queueItem=new int[2*maxSize];66 for(int i=1;i<maxSize;++i)67 queueItem[i]=queueItem[front+i];68 69 maxSize*=2;70 delete tmp;71 }72 73 int main()74 {75 maxQueue queue;76 int arr[9]={4,3,2,1,5,4,3,2,1};77 for(int i=0;i<9;++i)78 {79 queue.enQueue(arr[i]);80 cout<<"max:"<<queue.maxValue()<<endl;81 }82 cout<<endl;83 while(!queue.isEmpty())84 {85 86 cout<<"max:"<<queue.maxValue()<<endl;87 queue.deQueue();88 }89 90 return 0;91 }
编程之美——队列中取最大值操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。