min 함 수 를 포함 하 는 스 택 [마이크로소프트 면접 100 문제 두 번 째 문제]

제목 요구: 스 택 의 데이터 구 조 를 정의 합 니 다. 이 유형 에서 스 택 의 최소 요 소 를 얻 을 수 있 는 min 함 수 를 실현 하 십시오.이 스 택 에서 min, push 및 pop 을 호출 하 는 시간 복잡 도 는 모두 O (1) 입 니 다.
참고 문제: 검 지 offer 21 번.
제목 분석:
1. 대상 을 대상 으로 하 는 사상 을 사용 하여 StackWith Min 을 정의 하고 min, push 와 pop 등 방법 을 포함한다.
2. Stack With Min 류 에는 두 개의 스 택 이 포함 되 어 있 습 니 다. 하나의 데이터 스 택, 하나의 보조 스 택 입 니 다.데이터 스 택 에 서 는 매번 누 르 는 실제 데이터 이 고 보조 스 택 에 서 는 데이터 스 택 에 대응 하 는 현재 결산 점 의 최소 값 입 니 다.
설명: 데이터 스 택 이 stackdata 라 고 가정 하고 보조 스 택 은 stackmin 입 니 다.스 택 압축 데 이 터 를 5 - 3 - 4 - 1 - 2 로 순서대로 합 니 다.
5: stackdata: 5, stackmin: 5
눌 러 3: --- > stackdata: 5 - 3, stackmin: 5 - 3
압착 4: --- > stackdata: 5 - 3 - 4, stackmin: 5 - 3 - 3
압착 1: --- > stackdata: 5 - 3 - 4 - 1, stackmin: 5 - 3 - 3 - 1
압착 2: --- > stackdata: 5 - 3 - 4 - 1 - 2, stackmin: 5 - 3 - 4 - 1 - 1
stackdata 는 압축 된 실제 데이터 입 니 다. stackmin 에서 매번 압축 된 데이터 와 이전 stackmin 의 입력 을 비교 하고 이전 보다 작 으 면 현재 로 누 르 고 이전 보다 크 면 이전 데이터 로 누 릅 니 다.

#include <iostream>

#include <stack>

#include <cassert>



using namespace std;



template<class T>

class stackWithMin

{

public:

    stackWithMin(){}

    ~stackWithMin(){}

    void push(const T& value);

    void pop();

    const T& min() const;

    void printStack();

private:

    stack<T> stackData;

    stack<T> stackMin;

};

template<class T>

void stackWithMin<T>::push(const T& value)

{

    stackData.push(value);



    //                      ，       ；        

    if(stackMin.empty() || stackMin.top()>value)

        stackMin.push(value);

    else

        stackMin.push(stackMin.top());

}

template<class T>

void stackWithMin<T>::pop()

{

    assert(stackData.size()>0 && stackMin.size()>0);



    stackData.pop();

    stackMin.pop();

}

template<class T>

const T& stackWithMin<T>::min() const

{

    assert(stackData.size()>0 && stackMin.size()>0);



    return stackMin.top();

}

template<class T>

void stackWithMin<T>::printStack()

{

    stack<T> tmp;

    

    cout << "       ：";

    while(stackData.size())

    {

        tmp.push(stackData.top());

        stackData.pop();

    }

    

    while(tmp.size())

    {

        stackData.push(tmp.top());

        cout << tmp.top();

        tmp.pop();

    }

    cout << endl;

}

int main(void)

{

    stackWithMin<int> minStack;



    minStack.push(5);

    minStack.printStack();

    cout << "     ：" << minStack.min() << endl;



    minStack.push(3);

    minStack.printStack();

    cout << "     ：" << minStack.min() << endl;



    minStack.push(4);

    minStack.printStack();

    cout << "     ：" << minStack.min() << endl;



    minStack.push(1);

    minStack.printStack();

    cout << "     ：" << minStack.min() << endl;



    minStack.push(2);

    minStack.printStack();

    cout << "     ：" << minStack.min() << endl;



    return 0;

}