快速得到栈、队列的最大值

#include <iostream>
#include <climits>
#define MAX 100
using namespace std;

class stack
{
    public:
        stack() : stackTop(-1), maxValueIndex(-1) {}    
        void push(int val);
        int pop();
        int max();
        int size() { return stackTop + 1; }
        int empty() { return stackTop < 0 ? 1 : 0; }
    private:
        int stackItem[MAX];
        int link2NextMaxValueIndex[MAX];
        int stackTop;
        int maxValueIndex;
};

void stack::push(int val)
{
    ++stackTop;
    if(stackTop == MAX)
    {
        cout << "The stack has been full!" << endl;
        return;
    }
    else
    {
        stackItem[stackTop] = val;
        if(max() < val)
        {
            link2NextMaxValueIndex[stackTop] = maxValueIndex;
            maxValueIndex = stackTop;
        }
        else
            link2NextMaxValueIndex[stackTop] = -1;
    }
}
int stack::pop()
{
    int ret; 
    if(stackTop == -1)
    {
        cout << "The stack is empty!" << endl;
        return -1;
    }
    else
    {
        ret = stackItem[stackTop];
        if(stackTop == maxValueIndex)
            maxValueIndex = link2NextMaxValueIndex[stackTop];
        --stackTop;
        return ret;
    }
}
int stack::max()
{
    if(maxValueIndex >= 0)
        return stackItem[maxValueIndex];
    else
        return INT_MIN;
}


int main()
{
    stack s;
    cout << "s.empty():" << s.empty() << endl;
    s.push(3);
    s.push(4);
    cout << "s.top():" << s.pop() << endl;
    cout << "s.top():" << s.pop() << endl;
    cout << "s.top():" << s.pop() << endl;
    cout << "s.size():" << s.size() << endl;
    cout << "s.empty():" << s.empty() << endl;
}

#include <iostream>
#include <climits>
#define MAX 100
using namespace std;

class stack
{
    public:
        stack() : stackTop(-1), maxValueIndex(-1) {}    
        void push(int val);
        int pop();
        int max();
        int size() { return stackTop + 1; }
        int empty() { return stackTop < 0 ? 1 : 0; }
    private:
        int stackItem[MAX];
        int link2NextMaxValueIndex[MAX];
        int stackTop;
        int maxValueIndex;
};
class queue
{
    public:
        void enQueue(int val);
        int deQueue();
        int size() { return stackIn.size() + stackOut.size(); }
    private:
        stack stackIn;
        stack stackOut;
};

void stack::push(int val)
{
    ++stackTop;
    if(stackTop == MAX)
    {
        cout << "The stack has been full!" << endl;
        return;
    }
    else
    {
        stackItem[stackTop] = val;
        if(max() < val)
        {
            link2NextMaxValueIndex[stackTop] = maxValueIndex;
            maxValueIndex = stackTop;
        }
        else
            link2NextMaxValueIndex[stackTop] = -1;
    }
}
int stack::pop()
{
    int ret; 
    if(stackTop == -1)
    {
        cout << "The stack is empty!" << endl;
        return -1;
    }
    else
    {
        ret = stackItem[stackTop];
        if(stackTop == maxValueIndex)
            maxValueIndex = link2NextMaxValueIndex[stackTop];
        --stackTop;
        return ret;
    }
}
int stack::max()
{
    if(maxValueIndex >= 0)
        return stackItem[maxValueIndex];
    else
        return -100;
}

void queue::enQueue(int val)
{
    stackIn.push(val);
}

int queue::deQueue()
{
    if(stackOut.empty() and !stackIn.empty())
    {
        while(!stackIn.empty())
            stackOut.push(stackIn.pop());
    }
    return stackOut.pop();
}

int main()
{
    stack s;
    cout << "s.empty():" << s.empty() << endl;
    s.push(3);
    s.push(4);
    cout << "s.top():" << s.pop() << endl;
    cout << "s.top():" << s.pop() << endl;
    cout << "s.top():" << s.pop() << endl;
    cout << "s.size():" << s.size() << endl;
    cout << "s.empty():" << s.empty() << endl;
    queue q;
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    cout << "q.size()" << q.size() << endl;
    q.deQueue();
    cout << "q.size()" << q.size() << endl;
}