[Algo][July][Homework]设计一个队列支持求最大值，要求O(1)

栈和队列的基本概念：

存放数据的线性表。

操作：入栈/入队，出栈/出队，判断满/空

空间复杂度：O(n)

单次操作时间复杂度：O(1)

栈：先进后出 FILO；队：先进先出 FIFO

reference website:

http://blog.csdn.net/caryaliu/article/details/8097209

解题思路：

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

---------update at 2018-3-20 ------------

时隔半年，再看这道题目，觉得首先要清楚一个类可以称之为堆栈，需要具备那些功能。

1.1）最简单，堆栈可以用一个数组来存储。

1.2）需要实现push（压栈）方法，还有pop（出栈）方法。

1.3）堆栈的特性是先进后出。

---------update end --------------------

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

---------update at 2018-3-20 ------------

2.1）队列也可以是一个数组

2.2）队列是先进先出的

2.3）可以用两个堆，构造一个队列。元素从A依次压栈。出栈时，如果B为空，就把A中元素依次出栈，这样最先进入A的元素在B的顶部，再从B出栈。实现先进先出

---------update end --------------------

关于问题1：

用一个变量记录当前最大数的位置maxStackItemIndex。用一个数组来记录上一个最大数的位置link2NextMaxItem[]。

每一个数压栈，跟当前最大值比较，如果这个数比之前那个数大，那么就把上一个最大值的index保存到link2NextMaxItem[currentIndex]中，这个数的在栈的位置currentIndex记录在maxStackItemIndex中。

push x;

stackItem[stackTop] = x //栈顶

if x> stackItem[maxStackItemIndex]

　　link2NextMaxItem[stackTop] = maxStackItemIndex; //因为新压栈的元素比之前的最大值要大，L2NM这个数组保存上一个最大值的index

　　maxStackItemIndex = stackTop; //更新最大值的index

else

　　link2NextMaxItem[stackTop] = -1； //表示这个x不是之前压栈元素的最大值

pop x;

if stackTop == maxStackItemIndex //说明弹出的是最大值

　　maxStackItemIndex = link2NextMaxItem[stackTop] //最大值弹出，那么最大值的index更新为数组里保存的上一个最大值的index

栈的O(1)求最大值：

#include <iostream>
using namespace std;
#define MAXN 100
class Stack{
public:
    Stack(){ //构造函数
        stackTop = -1;
        maxStackItemIndex = -1;
    }
    bool isEmpty(){
        return stackTop == -1; 
    }
    bool isFull(){
        return stackTop == MAXN -1;
    }
     //元素压栈
    void push (int x){
        if(isFull()){
            cout<<"this stack is full!"<<endl;
        }
        else{
            stackItem[++stackTop] = x;
            if(x>maxValue()){
                link2NextMaxIndex[stackTop] = maxStackItemIndex;  //把上一个最大值index记录到数组中
                maxStackItemIndex = stackTop; //更新最大值index
            }
            else{
                link2NextMaxIndex[stackTop] = -1; //这个index不是最大值
            }         
        }    
    }
    int maxValue(){
        if(maxStackItemIndex >= 0){
            return stackItem[maxStackItemIndex]; //返回当前最大值
        }
        else{
            return INT_MIN;
        }
    } 
    int pop(){
        int ret;
        if(isEmpty()){
            cout<<"this stack is empty"<<endl;
        }
        else{ 
            ret = stackItem[stackTop];
                if(stackTop == maxStackItemIndex){  //弹出的是最大值
                    maxStackItemIndex = link2NextMaxIndex[stackTop]; //更新最大值index为上一个最大值的index
            }
        }
        stackTop--;
        return ret;
    }
private:
    int link2NextMaxIndex[MAXN];
    int stackItem[MAXN];
    int stackTop;
    int maxStackItemIndex;       
};

关于问题2：

创建两个栈。栈A和栈B。

入队操作：往栈A压栈。

出队操作：如果栈B为空，则把栈A元素依次出栈，压到栈B。栈A元素全部出栈位置。最后，栈B元素从栈顶pop。

如果栈B不为空，则从栈B栈顶pop。

O(1)的求最大值：max(stackA, stackB)

用两个栈实现队列，并且求队列最大值：

class Queue{
public:
    int maxValue(int x, int y){
        return x>y?x:y;
    }
    int max(){
        return maxValue(stackA.maxValue(),stackB.maxValue());
    }
    void enQueue(int x){
        if(stackA.isFull()){
            cout<<"the queue is full!"<<endl;
        }
        else{
            stackA.push(x);
        }
    }
    int deQueue(){
        if(stackB.isEmpty())
        {
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
        }
        return stackB.pop();
    }
private:
    Stack stackA;
    Stack stackB;
};

小结：

python写多了，写C++老是记不得加“;”[捂脸]。并且老是莫名其妙想加“:”

还有class大括号的右括号后要加";"