Ngăn xếp tần số tối đa trong C ++

Giả sử chúng ta muốn triển khai một ngăn xếp được gọi là FreqStack, FreqStack của chúng ta có hai chức năng -

push (x), Điều này sẽ đẩy một số nguyên x vào ngăn xếp.
pop (), Điều này sẽ loại bỏ và trả về phần tử thường xuyên nhất trong ngăn xếp. Nếu có nhiều hơn một phần tử có cùng tần số, thì phần tử gần đầu ngăn xếp nhất sẽ bị xóa và trả về.

Vì vậy, nếu đầu vào giống như đẩy một số phần tử như 7, 9, 7, 9, 6, 7, sau đó thực hiện các phép toán bật lên bốn lần, thì đầu ra sẽ tương ứng là 7,9,7,6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một bản đồ cnt
Xác định một số bản đồ
maxFreq:=0
Xác định một hàm push (), điều này sẽ lấy x,
(tăng cnt [x] lên 1)
maxFreq:=tối đa của maxFreq và cnt [x]
chèn x vào sts [cnt [x]]
Xác định một hàm pop ()
maxKey:=maxFreq
x:=phần tử hàng đầu của sts [maxKey]
xóa phần tử khỏi sts [maxKey]
nếu kích thước của sts [maxKey] bằng 0, thì -
- xóa maxKey khỏi sts
- (giảm maxFreq xuống 1)
(giảm cnt [x] đi 1)
trả lại x

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 FreqStack {
   public:
   unordered_map <int ,int > cnt;
   unordered_map <int, stack <int> >sts;
   int maxFreq = 0;
   FreqStack() {
      maxFreq = 0;
      cnt.clear();
      sts.clear();
   }
   void push(int x) {
      cnt[x]++;
      maxFreq = max(maxFreq, cnt[x]);
      sts[cnt[x]].push(x);
   }
   int pop() {
      int maxKey = maxFreq;
      int x = sts[maxKey].top();
      sts[maxKey].pop();
      if(sts[maxKey].size() == 0){
         sts.erase(maxKey);
         maxFreq--;
      }
      cnt[x]--;
      return x;
   }
};
main(){
   FreqStack ob;
   ob.push(7);
   ob.push(9);
   ob.push(7);
   ob.push(9);
   ob.push(6);
   ob.push(7);
   cout << (ob.pop()) << endl;
   cout << (ob.pop()) << endl;
   cout << (ob.pop()) << endl;
   cout << (ob.pop()) << endl;
}

Đầu vào

push elements 7, 9, 7, 9, 6, 7, then call pop() four times.

Đầu ra