最小栈实现-支持最小值的返回

时间：2010-12-12 来源：李土鳖

下满是C++实现:

// 设计一个堆栈， 堆栈除了支持push, pop 以外，还支持min，
// 并且他们的时间复杂度都是O(1)

#ifndef MIN_STACK_H
#define MIN_STACK_H

#include<cstdlib>

template<typename T>
class MinStack
{
public:
    void Push(T value);
    T Pop();
    T Min() { return this->_min->value; }
    bool Empty() { return _head == NULL; }

    MinStack() : _head(NULL), _min(NULL) {}
private:
    struct Entry
    {
        Entry() : lastMin(NULL), nextEntry(NULL)
        { }
        T value;
        Entry* lastMin;
        Entry* nextEntry;
    };
    
    Entry* _head;
    Entry* _min;
};

template<typename T>
void MinStack<T>::Push(T value)
{
    Entry* pEntry = new Entry();
    pEntry->value = value;
    pEntry->nextEntry = this->_head;
    this->_head = pEntry;
    if(this->_min == NULL)
        this->_min = pEntry;
    else if(pEntry->value < this->_min->value)
    {
        pEntry->lastMin = this->_min;
        this->_min = pEntry;
    }
}

template<typename T>
T MinStack<T>::Pop()
{
    T val = this->_head->value;
    if(this->_head->lastMin != NULL)
        this->_min = this->_head->lastMin;
    Entry* head = this->_head;
    this->_head = head->nextEntry;
    delete head;
    return val;
}

#endif

下面是测试代码：

代码

#include "MinStack.h"

#include<iostream>
using namespace std;

void test(int vals[], int len)
{
    MinStack<int> stack;
    for(int i = 0; i < len; i++)
        stack.Push(vals[i]);

    while(!stack.Empty())
    {
        cout << "min:" << stack.Min() << endl;
        cout << "pop:" << stack.Pop() << endl;
    }
}

int main()
{
    int arr1[] = {6, 3, 4, 7};
    test(arr1,4);
    cout << endl;
    int arr2[] = { 1, 2, 3, 4 };
    test(arr2,4);
    cout << endl;
    int arr3[] = { 4, 3, 2, 1 };
    test(arr3,4);
}