用C ++构造频率栈的程序

假设我们要构造一个称为FrequencyStack的堆栈，我们的FrequencyStack具有两个功能-

• append(x)，这会将值x附加或压入堆栈。

• pop()，这将删除并返回堆栈中最频繁的元素。如果有多个具有相同频率的元素，则将最接近堆栈顶部的元素移除并返回。

因此，如果输入就像追加一些元素，例如7、9、7、9、6、7，然后执行pop操作四次，则输出将分别为7,9,7,6。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个映射

• 定义一个映射站

• maxFreq：= 0

• 定义一个函数append()，这将需要x，

• （将cnt [x]增加1）

• maxFreq：= maxFreq和cnt [x]的最大值

• 将x插入sts [cnt [x]]

• 定义功能 pop()

• maxKey：= maxFreq

• x：= sts [maxKey]的顶部元素

• 从sts [maxKey]中删除元素

• 如果sts [maxKey]的大小等于0，则-

• 从sts删除maxKey

• （将maxFreq减少1）

• （将cnt [x]减1）

• 返回x

让我们看下面的实现以更好地理解-

示例

#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 append(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.append(7);
   ob.append(9);
   ob.append(7);
   ob.append(9);
   ob.append(6);
   ob.append(7);
   cout << (ob.pop()) << endl;
   cout << (ob.pop()) << endl;
   cout << (ob.pop()) << endl;
   cout << (ob.pop()) << endl;
}

输入值

ob.append(7);
ob.append(9);
ob.append(7);
ob.append(9);
ob.append(6);
ob.append(7);
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;

7
9
7
6