定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧的最小元素的min函數(shù)。在該棧中，調(diào)用min、push、及pop的時(shí)間復(fù)雜度都是O(1)。

創(chuàng)新互聯(lián)建站：從2013年創(chuàng)立為各行業(yè)開拓出企業(yè)自己的“網(wǎng)站建設(shè)”服務(wù)，為近千家公司企業(yè)提供了專業(yè)的網(wǎng)站設(shè)計(jì)、成都網(wǎng)站設(shè)計(jì)、網(wǎng)頁(yè)設(shè)計(jì)和網(wǎng)站推廣服務(wù)， 按需策劃由設(shè)計(jì)師親自精心設(shè)計(jì)，設(shè)計(jì)的效果完全按照客戶的要求，并適當(dāng)?shù)奶岢龊侠淼慕ㄗh，擁有的視覺效果，策劃師分析客戶的同行競(jìng)爭(zhēng)對(duì)手，根據(jù)客戶的實(shí)際情況給出合理的網(wǎng)站構(gòu)架，制作客戶同行業(yè)具有領(lǐng)先地位的。

  首先，棧的特點(diǎn)是“先進(jìn)后出，后進(jìn)先出”，因此，對(duì)于pop和push兩個(gè)操作自然都是直接放入棧頂和直接在棧頂刪除元素，那么如果要找棧中的最小值min，因?yàn)橐髸r(shí)間復(fù)雜度為O(1)，因此肯定不能遍歷棧找出最小元素，這里可以想到使用在這個(gè)棧的數(shù)據(jù)結(jié)構(gòu)中使用兩個(gè)棧，一個(gè)棧用來正常的存放刪除數(shù)據(jù)，另一個(gè)棧就用來存放當(dāng)前棧中的最小值；

  當(dāng)?shù)谝淮蝡ush進(jìn)棧的時(shí)候，就將數(shù)據(jù)也push進(jìn)min棧中，并且min棧中的棧頂元素為當(dāng)前棧的最小值，當(dāng)push的數(shù)據(jù)比min棧中的棧頂元素小的時(shí)候，就將push的數(shù)據(jù)也放進(jìn)min棧中，當(dāng)push的數(shù)據(jù)比min棧中的棧頂元素大的時(shí)候，就在再次將min棧中的棧頂元素再壓進(jìn)棧，因此，這樣下去，min棧中棧頂元素始終為當(dāng)前數(shù)據(jù)棧的最小值；而進(jìn)行pop數(shù)據(jù)的時(shí)候，在pop數(shù)據(jù)棧的棧頂元素時(shí)也pop出min棧的棧頂元素，這樣的話還是保證了min棧中棧頂元素為最小值，且時(shí)間復(fù)雜度為O(1)；

上述內(nèi)容可畫圖如下：

程序設(shè)計(jì)如下：

#include 
#include 
using namespace std;

template 
class my_stack
{
public:
    my_stack()//棧的默認(rèn)構(gòu)造函數(shù)，開始時(shí)指針為空且將容量設(shè)計(jì)為3
        :_data(NULL)
        ,_min(NULL)
        ,_size(0)
        ,_capacity(3)
    {}  

    void my_push(T data)//push數(shù)據(jù)
    {   
        if(_data == NULL)//當(dāng)?shù)谝淮畏艛?shù)據(jù)時(shí)
        {
            _data = new T[_capacity];
            _min = new T[_capacity];
            _data[_size] = data;
            _min[_size++] = data;
            return;
        }
     
        _CheckCapacity();//檢查容量
        _data[_size] = data;
        if(data < _min[_size-1])//若果要放入的數(shù)據(jù)比棧頂元素小，直接放入，否則，再次放入棧頂元素
            _min[_size] = data;
        else
            _min[_size] = _min[_size-1];

        ++_size;
    }

    void my_pop()//pop數(shù)據(jù)
    {
        if(_data == NULL)
            return;

        --_size;
    }

    T& min()//取出最小值
    {
        if(_data == NULL)
        {
            cout<<"no data..."< stack;
    stack.my_push(3);
    stack.my_push(5);
    stack.my_push(1);
    stack.my_push(2);
    stack.my_push(0);
    stack.my_push(6);
    stack.print_stack();

    cout<<"min data: "<
運(yùn)行程序：
可以看到，每pop一次數(shù)據(jù)，都能輸出當(dāng)前棧中的最小值，且時(shí)間復(fù)雜度都為O(1)。
《完》
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。
            

            網(wǎng)站名稱：包含min函數(shù)的?！?1-創(chuàng)新互聯(lián)            

            文章URL：http://weahome.cn/article/ijecs.html