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

有时候我们在使用堆栈时需要增加一些额外功能，例如返回栈中的最小值。本例实现了这样的操作，而且Push,Pop和返回最小值都能在常量时间内完成。

下满是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);}

原文链接: https://www.cnblogs.com/alala666888/archive/2010/12/12/1903775.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍