다음 작업을 지원하는 최대 스택을 만들고 싶다고 가정해 보겠습니다. -
-
MaxStk() 최대 스택의 새 인스턴스를 구성합니다.
-
push(val)는 스택에 val을 삽입합니다.
-
top() 스택에서 최상위 요소를 가져옵니다.
-
max() 스택에서 최대 요소를 가져옵니다.
-
pop()은 스택에서 최상위 요소를 제거하고 반환합니다.
-
popmax()는 스택에서 최대 요소를 제거하고 반환합니다.
이제 MasStk()를 호출하여 최대 스택을 구성한 다음 5, 15, 10과 같은 세 개의 값을 푸시한 다음 각각 top(), max(), popmax(), max() pop(), top() 함수를 호출하십시오. 그러면 초기 스택 상태는 [5, 15, 10]이고 함수에 대한 해당 출력:10, 15, 15, 10, 10, 5
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
pos_index :=0
-
한 세트 stk 다른 세트 보조 정의
-
생성자를 정의하십시오. 이것은 특별한 작업을 수행하지 않습니다.
-
push() 함수를 정의하면 val이 필요합니다.
-
pos_index, val을 stk에 삽입
-
aux에 val, pos_index 삽입
-
(pos_index를 1만큼 증가)
-
함수 정의 top()
-
stk가 비어 있으면 -
-
반환 -1
-
-
stk의 첫 번째 항목의 두 번째 값을 반환
-
max()
함수 정의 -
aux가 비어 있으면 -
-
반환 -1
-
-
aux의 첫 번째 항목의 첫 번째 값을 반환
-
함수 정의 pop()
-
stk가 비어 있으면 -
-
반환 -1
-
-
id :=stk의 첫 번째 항목의 첫 번째 값, ret =stk의 첫 번째 항목의 두 번째 값
-
stk에서 stk의 첫 번째 요소 삭제
-
aux에서 쌍(ret, id) 삭제
-
리턴 렛
-
popmax()
함수 정의 -
aux가 비어 있으면 -
-
반환 -1
-
-
ret :=aux의 첫 번째 항목의 첫 번째 값, id =aux의 첫 번째 항목의 두 번째 값
-
aux에서 aux의 첫 번째 요소 삭제
-
stk에서 쌍(id, ret) 삭제
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class MaxStk {
int pos_index = 0;
set<pair<int, int>, greater<>> stk, aux;
public:
MaxStk() {}
void push(int val) {
stk.emplace(pos_index, val);
aux.emplace(val, pos_index);
pos_index++;
}
int top() {
if (stk.empty())
return −1;
return stk.begin()−>second;
}
int max() {
if (aux.empty())
return −1;
return aux.begin()−>first;
}
int pop() {
if (stk.empty())
return −1;
int id = stk.begin()−>first, ret = stk.begin()−>second;
stk.erase(stk.begin());
aux.erase({ret, id});
return ret;
}
int popmax() {
if (aux.empty())
return −1;
int ret = aux.begin()−>first, id = aux.begin()−>second;
aux.erase(aux.begin());
stk.erase({id, ret});
return ret;
}
};
int main(){
MaxStk max_stk;
max_stk.push(5);
max_stk.push(15);
max_stk.push(10);
cout << max_stk.top() << endl;
cout << max_stk.max() << endl;
cout << max_stk.popmax() << endl;
cout << max_stk.max() << endl;
cout << max_stk.pop() << endl;
cout << max_stk.top() << endl;
} 입력
max_stk.push(5) max_stk.push(15) max_stk.push(10) max_stk.top() max_stk.max() max_stk.popmax() max_stk.max() max_stk.pop() max_stk.top()
출력
10 15 15 10 10 5