스 택 의 최소 요 소 를 가 져 옵 니 다.

CSDN 학원 데이터 구조 알고리즘 예제. 예 를 들 어 스 택 의 데이터 구 조 를 정의 합 니 다. 이 유형 에서 스 택 을 얻 을 수 있 는 최소 요소 min 함 수 를 실현 하 십시오. 이 스 택 에서 min / push / 그리고 pop 을 호출 하 는 시간 복잡 도 는 모두 O (1) 입 니 다. 스 택 에서 최소 요 소 를 출력 합 니 다. 1. 스 택 으로 최소 요 소 를 보조 적 으로 저장 합 니 다.. 팝 업 을 통 해 최소 요 소 를 얻 을 수 있 습 니 다. 2. 스 택 1 에 하나의 수 를 추가 합 니 다. 스 택 2 에 현재 1 의 최소 치 를 추가 합 니 다. 예 를 들 어 스 택 1 중 3, 현재 최소 치 는 3 보조 스 택 에 3 스 택 1 push 4 를 추가 할 때 보조 스 택 에 최소 요 소 를 추가 합 니 다.보조 스 택 에 최소 요소 1 스 택 1: 3, 4, 2 1 스 택 2: 3, 3, 2, 1 스 택 에서 꺼 낼 때: 스 택 1 팝 업 1, 보조 스 택 팝 업 1 최소 최소 요 소 를 가 져 옵 니 다.
/ / 스 택 1 과 보조 스 택 2 는 size 크기 가 일치 합 니 다.
MinIn Stack. cpp 파일: 콘 솔 프로그램의 입구 점 을 정의 합 니 다.

#include "StackWithMin.h"
#include <stdlib.h>

void Test(char* testName, const StackWithMin<int> & stack, int expected)
{
    if (testName != NULL)
    {
        printf("%s begins.
", testName);
    }
    if(stack.min() == expected)
    {
        printf("Passed!
");
    }
    else
    {
        printf("Failed 
");
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    StackWithMin<int> stack;
    stack.push(3);
    Test("Test1", stack, 3);

    stack.push(4);
    Test("test2", stack, 3);

    stack.push(2);
    Test("test3", stack, 2);

    stack.push(3);
    Test("test4", stack, 2);

    stack.pop();
    Test("test5", stack, 2);

    stack.pop();
    Test("Test6", stack, 3);

    stack.push(0);
    Test("test7", stack, 0);

    system("pause");
    return 0;
}

StackWithMin. h 파일

#pragma once

#include <stack>
#include <assert.h>

template<typename T> class StackWithMin
{
public:
    StackWithMin(){}
    virtual ~StackWithMin(){}

    T& top();
    const T& top() const;
    void push(const T& value);
    void pop();

    const T& min() const;
    bool empty() const;
    size_t size() const;

private:
    std::stack<T> m_data;
    std::stack<T> m_min;
};

template<typename T> void StackWithMin<T>::push(const T& value)
{
    m_data.push(value);
    if (m_min.size() == 0|| value < m_min.top())//  push   min  top  ,    
    {
        m_min.push(value);
    }
    else
        m_min.push(m_min.top());  //       ,  min         min      
}

template<typename T> void StackWithMin<T>::pop()
{
    assert(m_data.size() > 0 && m_min.size() > 0);
    m_data.pop();
    m_min.pop();
}

template<typename T> const T& StackWithMin<T>::min() const
{
    assert(m_data.size() > 0 && m_min.size() > 0);
    return m_min.top();
}

template<typename T> T& StackWithMin<T>::top()
{
    return m_data.top();
}

template<typename T>const T& StackWithMin<T>::top() const
{
    return m_data.top();
}

template<typename T>bool StackWithMin<T>::empty() const
{
    return m_data.empty();
}

template<typename T> size_t StackWithMin<T>::size() const
{
    return m_data.size();
}

StackWithMin. cpp 파일

#include "StackWithMin.h"