数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++实现频率栈程序
假设我们要构建一个名为FrequencyStack的栈，我们的FrequencyStack有两个函数：
append(x)：将值x添加到栈顶。
pop()：移除并返回栈中最频繁的元素。如果有多个元素具有相同的频率，则移除并返回最靠近栈顶的元素。
例如，如果输入是依次添加元素7, 9, 7, 9, 6, 7，然后执行四次pop操作，则输出将分别为7, 9, 7, 6。
为了解决这个问题，我们将遵循以下步骤：
定义一个map cnt
定义一个map sts
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
更新于：2020-12-26
浏览量：112
广告