队列中取最大值操作问题

分析：

这个问题和设计一个在O(1)时间内取最大值的堆栈看似比较相似，但实现难度要比最大值的堆栈困难一些，开始想模仿最大值堆栈的思想来设计取最大值的堆栈都失败了。实际上这个问题可以拆分成两个问题：

 1)设计一个在O(1)时间内取最大值的堆栈；

 2)如何使用堆栈来实现一个队列；

如果这两个问题解决了，O(1)时间取最大值的队列也就解决了，这体现了把一个困难的问题，分解为几个比较简单的问题，分步骤处理的思想。

    首先看第一个问题：设计一个在O(1)时间内取最大值的堆栈是比较容易的，我们可以使用两个堆栈来保存数据，其中一个保存正常的数据，另一个保存最大值，最大值堆栈在压栈前需要比较待压栈的元素与栈顶元素的大小，如果比栈顶大，那么是一个新的最大值，应该压入栈，否则保持当前最大值不变，也就是不压栈。弹出数据时，如果弹出的值和最大值栈的栈顶元素相同，说明最大值被弹出，此时最大值栈也应该跟着出栈，这样可以保持最大值的更新。

    再看第二个问题，可以使用两个栈来实现一个队列，队列push时，将数据压入A栈中，Pop数据时，如果B栈为空，将A栈的数据Pop出来，压入B栈中，再Pop B栈的数据；当队列Pop时，如果B栈的数据不为空，则直接Pop B栈的数据。

    取队列的Max就是取A栈和B栈的Max，而A、B栈都是我们刚才实现的最大值栈，他们取最大值的时间都是O(1)，因此队列取最大值复杂度也是O(1)。但实现是要注意A、B栈有可能为空，在我们的实现中，对于空栈取最大值是未定义的，因此在对A、B栈取最大值时要先判断是否为空栈。

   最后从复杂度来说，队列的Pop操作最坏情况是将A栈的数据都压入B栈，在Pop B栈的数据，最差是O(n)，实际多数情况都是O(1)。

   总结一下：这个问题，非常明显的体现了如何将一个新问题转成两个已知的简单问题，同时MyStack的实现封装了复杂性，使得后面的实现更加简单。

代码如下：

MyStack.h:

#pragma once
#define MAXN 10000
class MyStack
{
public:
 MyStack(void);
 ~MyStack(void);
 void push(int x);
 int pop();
 int Max();
 bool empty();
private:
 int stackItem[MAXN];
 int stackTop;
 int link2NextMaxItem[MAXN];
 int maxStackItemIndex;
};

MyStack.cpp:

#include "MyStack.h"
#include<iostream>
using namespace std;
MyStack::MyStack(void)
{
 stackTop=-1;
    maxStackItemIndex=-1;
}

MyStack::~MyStack(void)
{
}
void MyStack::push(int x)
{
 
     stackTop++;
  if(stackTop>=MAXN)
 {
     cout<<"栈已满，无法进行弹入操作"<<endl;
  return ;
 }
  stackItem[stackTop]=x;
  if(x>Max())
  {
      link2NextMaxItem[stackTop]=maxStackItemIndex;
         maxStackItemIndex=stackTop;
  }
  else
  {
     link2NextMaxItem[stackTop]=-1;
  }
}
int MyStack::pop()
{
 if(stackTop<0)
 {
      cout<<"无法对空队进行弹出操作"<<endl;
   return -1;
 }
     int x=stackItem[stackTop];
  if(stackTop==maxStackItemIndex)
  {
        maxStackItemIndex=link2NextMaxItem[stackTop];
  }
  stackTop--;
  return x;
}
int MyStack::Max()
{
     if(maxStackItemIndex>=0)return stackItem[maxStackItemIndex];
  else return -1;
}
bool MyStack::empty()
{
     return stackTop==-1;
}

MyQueue.h:

#pragma once
#include"MyStack.h"
class MyQueue
{
public:
 MyQueue(void);
 ~MyQueue(void);
 int MaxValue(int x,int y);
 void EnQueue(int v);//将v加入队列中
 int DeQueue();      //使队列中的队首元素删除并返回此元素
 int MaxElement();//返回队列中的最大元素
 bool empty();    //判断队列是否为空
private:
 MyStack stackA;
    MyStack stackB;
};

MyQueue.cpp

#include "MyQueue.h"
#include<iostream>
using namespace std;
MyQueue::MyQueue(void)
{
}

MyQueue::~MyQueue(void)
{
}
void MyQueue::EnQueue(int v)
{
 stackB.push(v);
}
int MyQueue::DeQueue()
{
 if(stackA.empty())
 {
  if(stackB.empty())
  {
       cout<<"无法对空队进行操作"<<endl;
    return -1;
  }
  while(!stackB.empty())
  {
   stackA.push(stackB.pop());
  }
 }
 stackA.pop();
}
int MyQueue::MaxValue(int x, int y)
{
 return (x>y)?x:y;
}
int MyQueue::MaxElement()
{
 return MaxValue(stackA.Max(),stackB.Max());
}
bool MyQueue::empty()
{
 if(stackA.empty()&&stackB.empty())return true;
 return false;
}

main.cpp:

#include<iostream>
//#include"MyStack.h"
#include"MyQueue.h"
using namespace std;

int main()
{
    MyQueue q;
 q.EnQueue(1);
 q.EnQueue(4);
 q.EnQueue(2);
 q.EnQueue(8);
 q.EnQueue(6);
 q.EnQueue(7);
 q.EnQueue(5);
 cout<<"max= "<<q.MaxElement()<<endl;
 q.DeQueue();
    cout<<"max= "<<q.MaxElement()<<endl;
 q.DeQueue();
    cout<<"max= "<<q.MaxElement()<<endl;
 q.DeQueue();
    cout<<"max= "<<q.MaxElement()<<endl;
 q.DeQueue();
    cout<<"max= "<<q.MaxElement()<<endl;
    system("pause");
 return 0;
}