RSS
トップページ – 新C++編 – queue、priority_queue、deque
このページは、練習問題の解答例や解説のページです。
６個のデータ 4, 3, 5, 3, 7, 6 を
std::stack、std::queue、std::priority_queue
のそれぞれに追加し、その後１つずつ取り出すと、どのような順序で取り出されますか？
std::stack
は後入れ先出しの構造なので、あとに追加されたデータから取り出されます。4、3、5、3、7、6
の順番に追加したので、6、7、3、5、3、4
の順に取り出されます。
std::queue は先入れ先出しの構造なので（本編解説）、先に追加されたデータから取り出されます。よって、4、3、5、3、7、6
の順に取り出されます。
std::priority_queue は優先度に従って取り出す順番が決まる構造です（本編解説）。優先度は、デフォルトでは要素の値の降順であるため、大きな整数値のものから順に取り出されます。よって、7、6、5、4、3、3
の順です。
次のプログラムで確かめられます。
#include <iostream>
#include <queue>
#include <stack>
int main() {
std::stack<int> stack {};
std::queue<int> queue {};
std::priority_queue<int> prio_queue {};
for (int v : {4, 3, 5, 3, 7, 6}) {
stack.push(v);
queue.push(v);
prio_queue.push(v);
}
std::cout << "stack: ";
while (!stack.empty()) {
auto v = stack.top();
stack.pop();
std::cout << v << " ";
}
std::cout << "\n";
std::cout << "queue: ";
while (!queue.empty()) {
auto v = queue.front();
queue.pop();
std::cout << v << " ";
}
std::cout << "\n";
std::cout << "priority_queue: ";
while (!prio_queue.empty()) {
auto v = prio_queue.top();
prio_queue.pop();
std::cout << v << " ";
}
std::cout << "\n";
}実行結果：
stack: 6 7 3 5 3 4
queue: 4 3 5 3 7 6
priority_queue: 7 6 5 4 3 3標準入力から整数を１つずつ入力させ、そのつど最新５件の平均値を出力するプログラムを、std::deque を使って作成してください。
プログラムを終了させる方法は適当に決めて構いません。
std::deque は両端キューを実装したものであり、先頭と末尾のいずれにでもデータの追加と削除が行えます（本編解説）。この特性を利用すれば、入力されてきた新しいデータを先頭に追加し、用がなくなった古いデータを末尾側から追い出す（先頭と末尾は入れ替えても構わない）ことが簡単にできます。これだけなら std::queue でもできますが、最新５件の平均を求めるには各要素へのアクセスできる必要がありますから、添字やイテレータが使える std::deque の方が適しています。
プログラムは次のように書けます。
#include <deque>
#include <iostream>
int main() {
constexpr int DataNum {5}; // 処理対象のデータの件数
std::deque<int> deque {};
while (true) {
int value {};
std::cin >> value;
if (std::cin.fail()) {
break;
}
// すでにデータが十分な個数に達していたら、古いものを取り除く
if (deque.size() >= DataNum) {
deque.pop_back();
}
// 新しいデータを追加
deque.push_front(value);
// 平均を求めて出力
auto sum = 0LL;
for (int elem : deque) {
sum += elem;
}
auto average = static_cast<double>(sum) / deque.size();
std::cout << "average of last " << DataNum << " data: " << average << "\n";
}
}実行結果：
50 <-- 入力
average of last 5 data: 50
10 <-- 入力
average of last 5 data: 30
10 <-- 入力
average of last 5 data: 23.3333
20 <-- 入力
average of last 5 data: 22.5
15 <-- 入力
average of last 5 data: 21
15 <-- 入力
average of last 5 data: 14
10 <-- 入力
average of last 5 data: 14
5 <-- 入力
average of last 5 data: 13
a <-- 入力標準入力から整数を１つずつ入力させ、そのつど最新５件の中で一番小さな値を出力するプログラムを、std::priority_queue を使って作成してください。
プログラムを終了させる方法は適当に決めて構いません。
std::priority_queue は優先度が一番高い要素から取り出せます。この問題の場合、取り出すのではなく topメンバ関数を使って、次に取り出される要素の参照を使えば、最新５件の中で一番小さい値を見つけられます。
ただし、std::priority_queue
の優先度は、デフォルトでは要素の値の降順なので、このままでは一番
“大きい”
値を返してしまいます。そこで優先度を要素の値の昇順になるように設定する必要があります。std::priority_queue
の変数を宣言するとき、<> の内側の３つ目の引数を
std::greater とすればよかったのでした（本編解説）。
プログラムは次のようになります。
#include <functional>
#include <iostream>
#include <queue>
int main() {
constexpr int DataNum {5}; // 処理対象のデータの件数
std::priority_queue<int, std::vector<int>, std::greater<int>> prio_queue {};
while (true) {
int value {};
std::cin >> value;
if (std::cin.fail()) {
break;
}
// すでにデータが十分な個数に達していたら、古いものを取り除く
if (prio_queue.size() >= DataNum) {
prio_queue.pop();
}
// 新しいデータを追加
prio_queue.push(value);
// 一番小さい数（優先度が一番高い要素）を出力
std::cout << "min of last " << DataNum << " data: " << prio_queue.top() << "\n";
}
}実行結果：
3 <-- 入力
min of last 5 data: 3
5 <-- 入力
min of last 5 data: 3
10 <-- 入力
min of last 5 data: 3
7 <-- 入力
min of last 5 data: 3
8 <-- 入力
min of last 5 data: 3
9 <-- 入力
min of last 5 data: 5
4 <-- 入力
min of last 5 data: 4
a <-- 入力
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |