CareerCup-3.2

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

微软实习生一面就遇到了这个问题，当时想到的是笨办法。但是面试官一点点引导，终于想出来这么做。

#include <iostream>
using namespace std;
typedef int Data;
// Creating a Linked List:
struct Node
{
    Node(Data d=0):data(d){next = NULL;};
    Data data;
    Node* next;
};

class Stack
{
public:
    Stack():top(NULL){minNode = NULL;};
    void pop()
    {
        if(top != NULL)
        {
            Node* p = top;
            top = top->next;
            delete p;
            Node* m = minNode;
            minNode = minNode->next;
            delete m;
        }
    };
    Data peek()
    {
        if(top != NULL)
        {
            return top->data;
        } else {
            throw "Empty Stack";
        }
    };
    void push(Data data)
    {
        Node* d = new Node(data);
        d->next = top;
        top = d;
        if(minNode != NULL && minNode->data < data)
            data = minNode->data;
        Node *m = new Node(data);
        m->next = minNode;
        minNode = m;
    };
    Data min()
    {
        if(minNode == NULL)
            throw "Empty Stack";
        else
            return minNode->data;
    }; 
    bool isEmpty(){return top == NULL;};
private:
    Node* top;
    Node* minNode;
};

int main()
{
    Stack stack;
    stack.push(3);
    cout<<stack.min()<<endl;
    stack.push(2);
     cout<<stack.min()<<endl;
    stack.pop();
    cout<<stack.min()<<endl;
    system("pause");
};