问题出处：《编程之美》3.7队列中取最大值操作问题
假定有这样一个拥有3个操作的队列：
1. EnQueue(v): 将v加入队列中
2. DeQueue(): 使队列中的队首元素删除并返回此元素
3. MaxElement(): 返回队列中的最大值
请设计一种数据结构和算法，让MaxElement()操作的时间复杂度尽可能的低。
常规思路：利用一个数组或者链表来存储队列的元素，利用两个指针分别指向队列的队首和队尾。如果采用这种方法，那么MaxElement()操作需要遍历队列中的所有元素。在队列的长度为N的条件下，时间复杂度为O(N).
下面的方法是在编程之美上看到的，能够实现MaxElement()的操作时间复杂度为O(1), 并且入队和出队的操作也很简单。
该队列使用两个栈stackA, stackB来实现的，stack有两个数组：stackItem[ ] 和 link2NextMaxItem[ ], stackItem 用于维护队列中的元素，link2NextMaxItem 用于维护栈中最大值的状态。入队操作是在stackB中执行入栈操作完成，出队操作是用stackA来完成，当stackA中没有元素时，将stackB中的所有元素都pop到stackA中，这样stackB中先入队的元素就会在stackA中的顶部，这样在stackA上执行pop操作，返回的元素就是最先入队的元素。
堆栈的程序描述如下，它实现了堆栈的入栈，出栈，维护栈中最大值状态，栈中元素打印的功能：
#define MAXN 100
class Stack
{
public:
//构造函数，初始化堆栈：
//|stackTop|指向当前堆栈的顶部元素，
//|maxStackItemIndex|存储当前堆栈中最大元素的index
Stack(){
stackTop = -1;
maxStackItemIndex = -1;
}
//判断当前堆栈是否为空
bool isEmpty() {
return stackTop == -1;
}
//判断当前堆栈是否满
bool isFull() {
return stackTop == MAXN - 1;
}
//向堆栈中push元素，
void push(int x) {
if(this->isFull()) { //首先检测堆栈空间是否满
cout<<"the stack is full now."<<endl;
}
else {
stackItem[++stackTop] = x;
//如果压入堆栈的值比之前记录的最大值大，那么那之前的最大值记录在
//link2NextMaxItem[stackTop]的位置，把当前最大值在堆栈stackItem
//中的位置用maxStackItemIndex保存
if(x > maxValue()) {
link2NextMaxItem[stackTop] = maxStackItemIndex;
maxStackItemIndex = stackTop;
}
else
link2NextMaxItem[stackTop] = -1;
}
}
int pop(){
int ret;
if(this->isEmpty()) {
cout<<"the stack is empty."<<endl;
}
else {
ret = stackItem[stackTop];
//如果pop出的值是当前的最大值，那么则需要将之前保存到link2NextMaxItem[stackTop]
//中的最大值取出，更新maxStackItemIndex的值
if( stackTop == maxStackItemIndex )
{
maxStackItemIndex = link2NextMaxItem[stackTop];
}
}
--stackTop;
return ret;
}
//取出堆栈中当前的最大值
int maxValue(){
if(maxStackItemIndex >= 0)
return stackItem[maxStackItemIndex];
else{
return INT_MIN;
}
}
void printItems() {
for (int i = 0; i <= stackTop; ++i) {
cout<<" "<<stackItem[i];
}
}
void reversePrintItems() {
for (int i = stackTop; i >= 0; --i) {
cout<<" "<<stackItem[i];
}
}
private:
int stackItem[MAXN];
int stackTop;
int link2NextMaxItem[MAXN];
int maxStackItemIndex;
};
使用上面的栈结构的两个栈对象就可以实现队列的结构了，并使MaxElement()操作的时间复杂度为O(1), 程序描述如下：
class Queue
{
public:
int maxValue(int x, int y) {
if(x>y)
return x;
else
return y;
}
//返回队列中最大值
int max() {
return maxValue(stackA.maxValue(), stackB.maxValue());
}
void printQueue() {
stackA.reversePrintItems();
stackB.printItems();
cout<<endl;
}
//在队列末尾插入元素
void insertQueue(int x) {
stackB.push(x);
}
//删除并返回队首元素,
//如果stackA中是空，则先将stackB中的所有元素pop到stackA中，
//这样stackB中先插入的元素就会pop到stackA中的顶部
int deQueue() {
if(stackA.isEmpty()) {
while(!stackB.isEmpty())
stackA.push(stackB.pop());
}
return stackA.pop();
}
private:
Stack stackA; //维护出队列操作
Stack stackB; //维护入队列操作
};
调试代码如下：
int main()
{
Queue queue;
int a[] = {909, 2, 3, 4, 9, 4, 5, 10, 6};
for(int i = 0; i < sizeof(a)/sizeof(int); ++i) {
queue.insertQueue(a[i]);
}
queue.insertQueue(101);
cout<<"queue maxvalue = "<<queue.max()<<endl;
queue.insertQueue(590);
cout<<"queue maxvalue = "<<queue.max()<<endl;
queue.printQueue();
int deq = queue.deQueue();
cout<<"deq = "<<deq<<endl;
cout<<"queue maxvalue = "<<queue.max()<<endl;
}
当前得自己加上头文件。