Giả sử ta muốn tạo một Maximum Stack, hỗ trợ các phép toán sau:
- MaxStk(): khởi tạo instance mới của Maximum Stack.
- push(val): chèn val vào stack.
- top(): lấy phần tử đỉnh stack.
- max(): lấy phần tử lớn nhất trong stack.
- pop(): xóa và trả về phần tử đỉnh stack.
- popmax(): xóa và trả về phần tử lớn nhất trong stack.
Xây dựng Maximum Stack bằng cách gọi MaxStk(), sau đó push 5, 15, 10, rồi gọi lần lượt top(), max(), popmax(), max(), pop(), top(). Trạng thái stack ban đầu: [5, 15, 10], đầu ra tương ứng: 10, 15, 15, 10, 10, 5.
Để giải quyết, ta làm theo các bước:
- pos_index := 0.
- Định nghĩa set stk và set aux.
- Định nghĩa constructor (không làm gì đặc biệt).
- Định nghĩa push(val): chèn (pos_index, val) vào stk; chèn (val, pos_index) vào aux; tăng pos_index.
- Định nghĩa top(): nếu stk rỗng trả -1; ngược lại trả giá trị thứ hai của phần tử đầu tiên stk.
- Định nghĩa max(): nếu aux rỗng trả -1; ngược lại trả giá trị thứ nhất của phần tử đầu tiên aux.
- Định nghĩa pop(): nếu stk rỗng trả -1; lấy id, ret từ phần tử đầu stk; xóa khỏi stk và aux; trả ret.
- Định nghĩa popmax(): nếu aux rỗng trả -1; lấy ret, id từ phần tử đầu aux; xóa khỏi aux và stk; trả ret.
Xem triển khai dưới đây:
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