스 택 의 데이터 구조 정의 <2>

스 택 의 데이터 구 조 를 정의 합 니 다. min 함 수 를 추가 하면 스 택 의 최소 요 소 를 얻 을 수 있 습 니 다.요구 함수 min, push 및 pop 의 시간 복잡 도 는 모두 O (1) 입 니 다.
링크 를 사용 하 든 배열 로 이 루어 진 스 택 을 사용 하 든 push 와 pop 작업 의 시간 복잡 도 는 모두 O (1) 입 니 다.그래서 어 려 운 점 은 min 을 실현 하여 시간 을 복잡 하 게 하 는 것 도 O (1) 이다.이 스 택 은 요소 minPoint 지침 을 추가 해 야 합 니 다.현재 minPoint 포인터 가 최소 요 소 를 가리 키 고 push (data) 를 가리킨다 고 가정 하면 data 가 minPoint 가 가리 키 는 요소 보다 작 으 면 minPoint 는 data 를 가리킨다.재 pop (), 이때 minPoint 가 가리 키 는 최소 요 소 는 스 택 에 존재 하지 않 습 니 다. minPoint 지침 을 수정 해 야 합 니 다.따라서 하나의 minPoint 지침 만 으로 는 기능 이 제대로 이 루어 지지 않 는 다.다른 스 택 minStack 으로 minPoint 포인터 가 순서대로 가리 키 는 요 소 를 저장 하 는 것 을 고려 합 니 다. 그 중에서 minStack 의 첫 번 째 요 소 는 현재 의 최소 요 소 를 가리 키 고 있 습 니 다.push (data) 와 data 가 최소 요소 보다 시간 이 많 을 때 새 노드 도 minstack 에 Push 합 니 다.그렇지 않 으 면, 직접 데 이 터 를 창고 에 넣 습 니 다.pop () 일 때 현재 팝 업 할 요소 가 스 택 의 최소 요소 라면 minStack 에서 동시에 스 택 을 나 와 최소 요 소 를 변경 합 니 다.그렇지 않 으 면 현재 스 택 에 있 는 요소 만 팝 업 됩 니 다.
사고: Push 의 첫 번 째 요 소 는 A 에 들 어 가 는 동시에 Push 도 보조 스 택 B 에 들 어 갑 니 다. A 에 있 는 Push 의 요소 가 B 에 있 는 요소 보다 작 을 때 이 요 소 를 Push 를 B (즉, 업데이트 B) 에 넣 습 니 다. 그렇지 않 으 면 B 스 택 은 움 직 이지 않 습 니 다 (즉, Push 포인터 minPoint 가 가리 키 는 값).
스 택 A push 요 소 를 향 할 때 순 서 는 아래 에서 위로 갑 니 다.
보조 창고 B 에는 항상 가장 작은 요소 가 저장 되 어 있 습 니 다.

 1 #include<iostream>
 2  #include<stack>
 3  
 4  using namespace std;
 5  
 6  //      
 7  template<class T> 
 8  class Stack{ 
 9      private:
10          stack<T> s; //  
11          stack<T> minS; //   
12      public:
13         bool empty(void);
14          T pop(void);
15          void push(T elem);
16          T min(void);
17      };
18  
19  template<class T> 
20  T Stack<T>::pop(void){
21      T elem=s.top();
22      s.pop();
23      minS.pop();
24      return elem;
25      }
26  
27  template<class T> 
28  T Stack<T>::min(void){
29      return minS.top();
30      }
31  
32  template<class T> 
33  void Stack<T>::push(T elem){ //  
34      s.push(elem);
35      if(minS.empty())
36          {minS.push(elem);} //          
37      else{ //             
38         T temp=minS.top();
39          if(temp<elem) minS.push(temp);
40          else minS.push(elem);
41          }
42      }
43  
44  
45  template<class T>
46  bool Stack<T>::empty(void){
47      return s.empty();
48      }
49  
50  
51  int main(void)
52  {
53      Stack<int> my;
54      my.push(4);
55      cout<<my.min()<<endl;
56      my.push(8);
57      cout<<my.min()<<endl;
58      my.push(0);
59      cout<<my.min()<<endl;
60      my.pop();
61      cout<<my.min()<<endl;
62  
63      return 0;
64  }

 
클래스 템 플 릿 설명 및 사용:
(1) 먼저 실제 클래스 를 작성 한다.그 의미 가 명확 하고 의미 가 명확 하기 때문에 일반적으로 실 수 를 하지 않 는 다.
(2) 이러한 변 화 를 준비 하 는 형식 이름 (예 를 들 어 int 가 float 나 char 로 바 꾸 려 면) 을 자신 이 지정 한 가상 형식 이름 (예 를 들 어 numtype) 으로 바 꿉 니 다.
(3) 클래스 성명 앞 에 한 줄 을 추가 합 니 다. 형식 은:
template < class 가상 형식 매개 변수 >, 예 를 들 어
　　template    //본 줄 의 끝 에 분점 이 없 도록 주의 하 시 오
　　class Compare
　　{…};     //유형 체
(4) 클래스 템 플 릿 으로 대상 을 정의 할 때 다음 과 같은 형식 을 사용 합 니 다.
클래스 템 플 릿 이름 < 실제 형식 이름 > 대상 이름;
클래스 템 플 릿 이름 < 실제 형식 이름 > 대상 이름 (실제 참조 표 열);
예 를 들 어 Compare < int > cmp;
　　Compare cmp(3,7);
(5) 클래스 템 플 릿 밖에서 구성원 함 수 를 정의 하려 면 클래스 템 플 릿 형식 으로 써 야 합 니 다.
template < class 가상 형식 매개 변수 >
함수 형식 클래스 템 플 릿 이름 < 가상 형식 매개 변수 > * 8759 ° 구성원 함수 이름 (함수 형 참조 표 열) {…}
설명:
(1) 클래스 템 플 릿 의 유형 매개 변 수 는 하나 이상 이 있 을 수 있 습 니 다. 모든 유형 앞 에 class 를 추가 해 야 합 니 다.
예 를 들 어 template < class T1, class T2 >
　　class someclass
　　{…};
대상 을 정의 할 때 실제 유형 명 을 각각 대 입 합 니 다. 예 를 들 어
　　someclass obj;
(2) 클래스 를 사용 하 는 것 과 마찬가지 로 클래스 템 플 릿 을 사용 할 때 그 역할 영역 에 주의 하고 효과 적 인 역할 영역 에서 만 대상 을 정의 할 수 있 습 니 다.
(3) 템 플 릿 은 차원 이 있 고 하나의 템 플 릿 은 기본 클래스 로 파생 템 플 릿 류 를 파생 시 킬 수 있다.
 
 
본문 ，감사합니다. 의 공유.