包含MIN函數的棧+一個數組實作兩個堆棧+兩個數組實作MIN棧

1.題目描述

定義棧的資料結構，請在該類型中實作一個能夠得到棧最小元素的min函數。

思路：利用一個輔助棧來存放最小值

    棧  3，4，2，5，1

    輔助棧 3，2，1

每入棧一次，就與輔助棧頂比較大小，如果小就入棧，如果大就不入棧目前的輔助棧；當出棧時，輔助棧元素相等時也要出棧。

class Solution {
public:
    stack<int> mystack1;//輔助棧
    stack<int> minstack;//最小棧
    void push(int value) {
        if(minstack.empty()){
            minstack.push(value);
        } else if(minstack.top()>value){
            minstack.push(value);
        }
        mystack1.push(value);
    }
    void pop() {
        if(mystack1.top()==minstack.top()) minstack.pop();
        mystack1.pop();     
         
    }
    int top() {
        return mystack1.top();
    }
    int min() {
       // if(!minstack.empty())
        return minstack.top();       
    }
};      

2.兩個數組實作MIN棧問題

題目：定義棧的資料結構，請在該棧中實作一個能夠得到棧中最小元素的MIN函數。在該棧中，調用MIN、PUSH、POP的時間複雜度均是O（1）。 

      根據題目可以看出，本次我們涉及的資料結構是棧(Stack),先看一下棧的介紹：棧又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和删除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧删除元素又稱作出棧或退棧，它是把棧頂元素删除，使其相鄰的元素成為新的棧頂元素。 

     上面的描述很詳細，簡單點說就是一句話，棧是一種先入後出的資料結構，基于這個特點，每次先壓入棧的元素，總是最後才被彈出的，而每次彈出的元素，也肯定是最後被壓入的元素，基于這種特點，對棧做排序是比較麻煩的，同時也注意到，題目中要求的時間複雜度是O(1)，也就是說不能利用周遊去得到這個最小值，哪有人會說了，我們可以記錄一個全局變量，初始值為壓入棧中的第一個元素，然後每次壓棧都比較該變量中的元素和壓棧元素的大小，保證該全局變量中存的就是最小數值，這樣的思路倒是滿足時間複雜度為O(1)的要求，但如果做了彈棧操作呢？如果把棧中最小的元素彈出怎麼辦？這個時候你這個全局變量就廢了，是以這種辦法也是行不通滴。 

那該怎麼辦呢？事實上在壓棧操作時就把最小元素存起來的思路是沒有問題的，但是卻隻考慮了 一個最小元素，沒有考慮第二小元素，第三小元素等等，而為了保證在最小元素彈出的情況下，可以立馬得到第二小元素，我們要借助一個輔助的存儲空間來完成這件事。 

     假如我們存儲元素的棧是DATA棧，用來存儲最小元素的輔助結構是TEMP棧(選用棧是為了和DATA棧保持一緻，也友善了解)，這樣我們就有兩個棧，大家也應該注意到我們的标題就是“兩個數組來實作MIN棧”。現在數組就可以排上用場了。 

數組應該是大家接觸最多，使用最廣的資料結構了，其定義簡單，了解起來容易，直接通過下标通路資料，可以達到O(1)的時間複雜度，但同時數組也存在諸多缺陷，比如說大小一旦确定，就無法改變，使用過程中如果稍有不慎，就有可能越界帶來不可預知的錯誤。但在我們這道題中，首先就是要做到利用一個數組來實作兩個棧，有以下兩種思路： 

     1、定義兩個下标index1和index2，初始值index1 = 0， index2 = length - 1 ，其中length為數組長度，每次向棧1壓入元素時，index1增1，每次向棧2壓入元素時，index2減1，彈棧時相反，棧的最大深度為length的一半，這樣相當于索引值都是指向了棧頂，滿足要求； 

     2、同樣還是定義兩個索引值index1和index2，初始值index1 = 0， index2 = 1， 每次壓棧時，相應的索引值都增2，彈棧時減2，相當于把一個數組一分為二，偶數位作為一個棧，奇數位作為一個棧，兩個棧互不幹擾，獨立使用，也可以滿足要求。 

比較上述兩種方法可以看到思路1更為靈活，且幾乎不會浪費數組空間，假設兩個棧的深度為M和N，若用思路2，則無論M和N的關系如何，都必然會浪費|M-N|個空間，而思路1則不會有這種問題，不過在我們這道題中，DATA棧和TEMP棧大小一樣，實際上用那種思路都可以

reference:  資料結構與算法（三）兩個數組實作MIN棧問題

3. 用一個數組實作兩個堆棧，最大化利用空間

 注意了解下标的關系。

/*****************************************************
* \file 數組實作兩個堆棧.cpp
* \date 2017/03/17 23:02
* \author ranjiewen
* \contact: [email protected] 
* \問題描述：
用一個數組實作兩個堆棧，要求最大利用數組空間，使數組隻要有空間
入棧操作就可以成功。
* \問題分析：
兩個棧分别從數組的兩頭開始向中間生長，當兩個棧的棧頂指針相遇時，表示兩個棧都滿了

*****************************************************/

#include<stdio.h>
#include <stdlib.h>

#define MAXSIVE 20
typedef int ElementType;
typedef struct DStack *DStack_;
struct DStack
{
    ElementType Data[MAXSIVE];
    int top1;  //棧1的棧頂指針
    int top2;  //棧2的棧頂指針
};

void Push(struct DStack *ptrs, ElementType item, int Tag)
{
    /*Tag作為區分兩個堆棧的标志，取值為1/2*/
    if (ptrs->top2-ptrs->top1==1)
    {
        printf("棧滿！"); return;
    }
    if (Tag==1)
    {
        ptrs->Data[++(ptrs->top1)] = item;
    }
    else
    {
        ptrs->Data[--(ptrs->top2)] = item;
    }
}

ElementType Pop(struct DStack *ptrs,int Tag)
{
    if (Tag==1)
    {
        if (ptrs->top1==-1)
        {
            printf("棧1空！");
            return NULL;
        }
        else
        {
            return ptrs->Data[(ptrs->top1)--];
        }
    }
    else
    {
        if (ptrs->top2==MAXSIVE)
        {
            printf("棧2空！");
            return NULL;
        }
        else
        {
            return ptrs->Data[(ptrs->top2)++];
        }
    }
}

int main()
{
    //struct DStack *S=(DStack_)malloc(sizeof(struct DStack));
    struct DStack stack;
    DStack_ S = &stack;
    S->top1 = -1;
    S->top2 = MAXSIVE;

    for (int i = 0; i < 8;i++)
    {
        Push(S, i, 1);
        Push(S, 8 - i, 2);
    }

    for (int i = 0; i <= S->top1;i++)
    {
        printf("%d ",S->Data[i]);
    }
    printf("\n");
    for (int i = MAXSIVE-1; i >= S->top2; i--)
    {
        printf("%d ", S->Data[i]);
    }
    printf("\n");
    return 0;
}      

C/C++基本文法學習

STL

C++ primer