창고 & 대열 면접 문제 의 실현 창고... (Push, Pop, Min)

하나의 스 택 을 실현 하려 면 Push (스 택), Pop (스 택 나 가기), Min (최소 값 으로 돌아 가 는 작업) 의 시간 복잡 도 는 O (1) 입 니 다.
        우 리 는 스 택 이 후진 에서 먼저 나 오 는 데이터 구조 라 는 것 을 알 고 있 습 니 다. 이런 데이터 구 조 는 스 택 꼭대기 에서 만 삽입 하고 삭제 할 수 있 기 때문에 스 택 이라는 데이터 구 조 를 실현 하 는 가장 좋 은 구 조 는 바로 순서 표 입 니 다. 꼬리 부분 을 많이 삭제 할 때...링크 는 공간 을 개척 하고 공간 을 삭제 하 는 시간 소모 가 존재 하기 때문에 이때 순서 표 는 링크 보다 좋 습 니 다. 구 조 를 선택 한 후에 스 택 요소 의 최소 치 를 어떻게 구 합 니까?
   사고방식 1:
             만약 한 번 에 같은 데 이 터 를 두 번 압축 할 수 있다 면
       1. 압축 할 데이터 가 창고 꼭대기 의 데이터 보다 크다
        (1). 원래 스 택 꼭대기 에 있 던 요 소 를 저장 하고 팝 업 합 니 다.
        (2). 새 원 소 를 창고 에 보관 하고 원래 창고 꼭대기 의 원 소 를 창고 에 보관 합 니 다.
       2. 압축 할 데 이 터 는 창고 꼭대기 의 데이터 보다 작다
        이 데 이 터 를 직접 두 번 저장 합 니 다.
        매번 이렇게 스 택 을 누 르 면 마지막 스 택 꼭대기 까지 의 요 소 는 모든 데이터 에서 가장 작은 요소 이 고 스 택 에 들 어 가 는 순서 도 바 뀌 지 않 습 니 다.
   사고방식 2:
        두 개의 스 택 을 이용 하여 한 스 택 은 정확 한 스 택 순서에 따라 스 택 을 쌓 고 한 스 택 은 최소 값 을 저장 합 니 다.
        (1). Stack 1 이 빈 창고 이거 나 창고 에 들 어 갈 원소 가 Stack 2 보다 작은 창고 꼭대기 원소 라면 이 데 이 터 를 Stack 1 에 눌 러 넣 고 Stack 2 에 눌 러 넣 습 니 다.
        (2). 스 택 에 들 어 가 는 요소 가 Stack 2 의 스 택 상단 요소 보다 크다 면 이 데 이 터 를 Stack 1 에 눌 러 야 합 니 다.
       이때 Stack 2 에 저 장 된 것 은 원래 스 택 요소 의 최소 값 입 니 다.
       상기 두 가지 생각 은 모두 공간 으로 시간 을 바 꾸 고 시간 복잡 도 는 O (1) 이다.
   사고방식 1 의 실현:
       

//       ，        
template<typename T>
class MinStack
{
public:
	void Push(const T& d)
	{
		if(_ptr.empty() || d <= _ptr.top())
			//            
		{
			_ptr.push(d);
			_ptr.push(d);
		}
		else
		{
			T mindata=_ptr.top();
			_ptr.push(d);
			_ptr.push(mindata);
		}
	}
	void Pop()
	{
		assert(!_ptr.empty());
		_ptr.pop();
		_ptr.pop();
	}
	T& MinData()
	{
		return _ptr.top();
	}
	T& top()
	{
		assert(!_ptr.empty());
		T mindata=_ptr.top();
		_ptr.pop();
		T &ret=_ptr.top();
		_ptr.push(mindata);
		return ret;
	}
protected:
	stack<T> _ptr;
};

 
      사고방식 2 의 실현:
           

//     ，         
template<typename T>
class MinStack2
{
public:
	void Push(const T& d)
	{
		if(_ptr1.empty() || d <= _ptr2.top())
		{
			_ptr1.push(d);
			_ptr2.push(d);
		}
		else
		{
			_ptr1.push(d);
		}
	}
	void Pop()
	{
		assert(!_ptr1.empty());
		if(_ptr1.top() == _ptr2.top())
		{
			//                
			_ptr1.pop();
			_ptr2.pop();
		}
		_ptr1.pop();
	}
	T& MinData()
	{
		return _ptr2.top();
	}
protected:
	stack<T> _ptr1;   //    
	stack<T> _ptr2;   //   
};

       주의:
      아이디어 2 의 팝 함수 구현 중ptr 2 도 조정 이 필요 합 니 다. 두 창고 의 꼭대기 요소 가 일치 해 야 조정 할 수 있 습 니 다ptr 2 의 스 택 상단 요소 입 니 다. 그렇지 않 으 면 스 택 의 최소 값 은 원래 의 최소 값 이 므 로 동적 으로 수정 할 수 없습니다.
       test.cpp
         

void testMinStack()
{
	MinStack<int> ms;
	ms.Push(5);
	ms.Push(1);
	ms.Push(2);
	ms.Push(3);
	ms.Pop();
	cout<<ms.top()<<endl;  //3
	cout<<"     :";
	cout<<ms.MinData()<<endl;
}

void testMinStack2()
{
	MinStack2<int> ms2;
	ms2.Push(5);
	ms2.Push(3);
	ms2.Push(6);
	ms2.Push(0);
	ms2.Push(2);
	cout<<"     :";
	cout<<ms2.MinData()<<endl;   //0
	ms2.Pop();
	ms2.Pop();
	cout<<"     :";
	cout<<ms2.MinData()<<endl;   //3
}

int main()
{
	//testMinStack();
	testMinStack2();
	system("pause");
	return 0;
}

 
            
          테스트 를 통 해 상기 두 가지 코드 는 모두 실현 가능 합 니 다.