Giả sử chúng ta muốn tạo một ngăn xếp tối đa, hỗ trợ các hoạt động sau -
-
MaxStk () này sẽ tạo một phiên bản mới của ngăn xếp tối đa
-
push (val) chèn val vào ngăn xếp
-
top () lấy phần tử cao nhất từ ngăn xếp
-
max () lấy phần tử lớn nhất từ ngăn xếp
-
pop () xóa và trả về phần tử trên cùng nhất khỏi ngăn xếp
-
popmax () xóa và trả về phần tử tối đa khỏi ngăn xếp
Bây giờ, hãy xây dựng ngăn xếp tối đa bằng cách gọi MasStk (), sau đó đẩy ba giá trị như 5, 15, 10, sau đó gọi các hàm top (), max (), popmax (), max () pop (), top () tương ứng. thì trạng thái ngăn xếp ban đầu sẽ là [5, 15, 10] và đầu ra tương ứng cho các hàm:10, 15, 15, 10, 10, 5
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
pos_index:=0
-
Xác định một bộ stk một bộ aux khác
-
Xác định hàm tạo, hàm này không thực hiện bất kỳ tác vụ đặc biệt nào
-
Xác định một hàm push (), điều này sẽ lấy val,
-
chèn pos_index, val vào stk
-
chèn val, pos_index vào aux
-
(tăng pos_index lên 1)
-
Xác định một hàm top ()
-
nếu stk trống, thì -
-
trả về −1
-
-
trả về giá trị thứ hai của mục đầu tiên của stk
-
Xác định một hàm max ()
-
nếu aux trống, thì -
-
trả về −1
-
-
trả về giá trị đầu tiên của mục đầu tiên của aux
-
Xác định một hàm pop ()
-
nếu stk trống, thì -
-
trả về −1
-
-
id:=giá trị đầu tiên của mục đầu tiên của stk, ret =giá trị thứ hai của mục đầu tiên của stk
-
xóa phần tử đầu tiên của stk khỏi stk
-
xóa cặp (ret, id) khỏi aux
-
trả lại ret
-
Xác định một hàm popmax ()
-
nếu aux trống, thì -
-
trả về −1
-
-
ret:=giá trị đầu tiên của mục đầu tiên của aux, id =giá trị thứ hai của mục đầu tiên của aux
-
xóa phần tử đầu tiên của aux khỏi aux
-
xóa cặp (id, ret) khỏi stk
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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;
} Đầu vào
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()
Đầu ra
10 15 15 10 10 5