สมมติว่าเราต้องการสร้างสแต็กสูงสุด ซึ่งรองรับการดำเนินการต่อไปนี้ -
-
MaxStk() สิ่งนี้จะสร้างอินสแตนซ์ใหม่ของสแต็กสูงสุด
-
push(val) แทรก val ไปยังสแต็ก
-
top() รับองค์ประกอบสูงสุดจาก stack
-
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 อีกชุด aux
-
กำหนดคอนสตรัคเตอร์ สิ่งนี้ไม่ได้ทำงานพิเศษใดๆ
-
กำหนดฟังก์ชัน push() ซึ่งจะใช้ค่า val
-
แทรก pos_index , val ลงใน stk
-
แทรก val, pos_index ลงใน aux
-
(เพิ่ม pos_index ขึ้น 1)
-
กำหนดฟังก์ชัน top()
-
ถ้า stk ว่างเปล่า −
-
กลับ -1
-
-
ส่งคืนค่าที่สองของรายการแรกของ stk
-
กำหนดฟังก์ชัน max()
-
ถ้า aux ว่างเปล่า −
-
กลับ -1
-
-
ส่งคืนค่าแรกของรายการแรกของ aux
-
กำหนดฟังก์ชัน pop()
-
ถ้า stk ว่างเปล่า −
-
กลับ -1
-
-
id :=ค่าแรกของรายการแรกของ stk, ret =ค่าที่สองของรายการแรกของ stk
-
ลบองค์ประกอบแรกของ stk ออกจาก stk
-
ลบคู่ (ret, id) จาก aux
-
รีเทิร์น
-
กำหนดฟังก์ชัน popmax()
-
ถ้า aux ว่างเปล่า −
-
กลับ -1
-
-
ret :=ค่าแรกของรายการแรกของ aux, id =ค่าที่สองของรายการแรกของ aux
-
ลบองค์ประกอบแรกของ aux ออกจาก aux
-
ลบคู่ (id, ret) จาก stk
-
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
