スタックとキュー
L！ I！ F！ O！
ここでは、ちょっと変わったコンテナとその使い道を紹介していく。
stack
データを後ろからのみ入れることができて、後ろから逆の順序でしか取り出せないコンテナ。
データを皿のように積み上げていくイメージ。
ここでのスタックは MTG の用語じゃないよ。
↑ 取ったり ↓ 乗せたり
ーーー
| 2 |
ーーー
| 0 | こことか
ーーー
| 1 | ここは取り出せない
ーーー
#include <stack> が必要。
// vector と同じで格納する型はテンプレート引数
std::stack<int> S;
// push でスタックに一つ「積む」
S.push(2); // {2}
// pop でスタックから一つ取り除く
S.pop(); // { }
S.push(4); // {4}
S.push(3); // {4, 3}
S.pop(); // {4}
S.push(1); // {4, 1}
// empty で空かどうかを bool で取得
while (!S.empty()) {
// top でスタックの一番上 (後ろ) を取得
auto top = S.top();
S.pop();
std::cout << top << " ";
}
これは、やることを積んでおいて逆順に解決していくのに使うよ。
例題
例題をやってみる。
入力:
N T
Nは0以上T の長さ未満の整数Tは文字列
'('と')'で構成された文字列が与えられる。
'('と')'は必ず対応付け (開いて閉じること) がされている。文字列
TのN番目の位置 (0 始まり) の'('または')'に対応している、反対向きの括弧の位置 (0 始まり) を探す。その位置を出力せよ。
例えば、入力が
5
((())(()()))(())
の場合は、
( ( ( ) ) ( ( ) ( ) ) ) ( ( ) )
0 11 12 15
1 4 13 14
2 3
5 10
6 7
8 9
と対応付けられるので、10 を出力する。
- 文字列の中の文字を一つづつ見る
- 括弧が始まっている
- その位置を
stackに乗せて次の文字へ
- その位置を
stackのtop、もしくは今見ている位置がNに等しいかどうか見る- 等しければ反対側にあたる位置を出力して終了
- 括弧が終わっている (他の文字がないので常に
true)stackを一つ取る
- 括弧が始まっている
と解けば楽ちん。
#include <iostream>
#include <stack>
int main() {
int N;
std::string T;
std::cin >> N >> T;
std::stack<int> brace_index;
for (size_t i = 0; i < T.size(); ++i) {
if (T[i] == '(') {
brace_index.push(i);
continue;
}
if (i == N) {
std::cout << brace_index.top() << "\n";
break;
}
if (brace_index.top() == N) {
std::cout << i << "\n";
break;
}
brace_index.pop();
}
}
queue
データを入れると、入れた順番でしか取り出せないコンテナ。
要素は後ろから追加する。
要素の取得と削除は前側からしかできない。
#include <queue> が必要。
std::queue<int> Q;
// push と pop があるけど stack とは違う
Q.push(2); // {2}
Q.pop(); // { }
Q.push(4); // {4}
Q.push(3); // {4, 3}
Q.pop(); // {3}
Q.push(1); // {3, 1}
// empty で空かどうかを bool で取得
while (!Q.empty()) {
// front でキューの先頭を取得
auto head = Q.front();
Q.pop();
std::cout << head << " ";
}
例題
それじゃあ毎度おなじみ例題だよ。
入力:
V E S G src1 dst1 src2 dst2 : srcE dstE
VとEは正の整数SとGは0以上E未満の整数srcEとdstEは0以上V未満の整数
V個の異空間がある。異空間どうしの間には二つの空間をつなぐ一方通行のポータルがあり、
src番目の空間からdst番目の空間に向かってだけ移動できる。ポータルを利用して、
S番目の空間からG番目の空間へ移動できるかどうか求めよ。移動できる場合は
"YES"、できない場合は"NO"を改行を加えて出力せよ。
入力例1:
5 8 0 4 0 1 1 2 2 3 3 4 0 2 0 3 1 0 1 3出力例1:
YES
入力例2:
3 4 0 1 0 2 0 2 2 0 2 2出力例2:
NO
それじゃあ入力を受け付けよう。
using std::cin;
int V, E, S, G;
cin >> V >> E >> S >> G;
// adj[i] を i 番目の空間から入れるポータルの行き先リストとする
std::vector<std::vector<size_t>> adj(V);
for (int i = 0; i < E; ++i) {
int src, dst;
cin >> src >> dst;
adj[src].push_back(dst);
}
これでデータは用意できた。あとは、
- 最初の空間である
Sをキューにpush - キューが空になるまで繰り返し
- キューの
frontをnowとして取り出し、pop nowがGなら- 到達可能なので終了
nowが 通過済み なら次のキューの要素へ飛ばすnowを 通過済み とメモするnowのportalsの各要素をnextとして見るnextが 通過済み ではないものならnextをキューにpush
- キューの
で判断できる。
問題に書いてある 入力例1 でこのアルゴリズムの動作の確認をしてみる。
nowは0。通過済み にする。
nowから行けるのは1、2、3。すべてpush。nowは1。通過済み にする。
nowから行けるのは0、2、3。このうち2、3をpush。nowは2。通過済み にする。
nowから行けるのは3。これをpush。nowは3。通過済み にする。
nowから行けるのは4。これをpush。nowは2。pushできるものはない。nowは3。pushできるものはない。nowは3。pushできるものはない。nowは4。到達できちゃった。
こういう手近な方法から幅広く探していくのを、幅優先探索 (BFS、Breadth First Search) という。キューを使うことが多い。
bool reachable = false;
std::vector<bool> passed(E); // 通過済みかどうかのメモ用
std::queue<size_t> bfs;
bfs.push(S);
while (!bfs.empty()) {
auto now = bfs.front();
bfs.pop();
if (G == now) {
reachable = true;
break;
}
// 通過済みなので更新する必要がない場合
if (passed[now]) {
continue;
}
passed[now] = true;
for (auto next : adj[now]) {
if (!passed[next]) {
bfs.push(next);
}
}
}
仕上げに出力を書いて終わり。
using std::cout;
if (reachable) {
cout << "YES\n";
} else {
cout << "NO\n";
}
全体はこうなる。
#include <iostream>
#include <queue>
int main() {
using std::cin;
int V, E, S, G;
cin >> V >> E >> S >> G;
std::vector<std::vector<size_t>> adj(V);
for (int i = 0; i < E; ++i) {
int src, dst;
cin >> src >> dst;
adj[src].push_back(dst);
}
bool reachable = false;
std::vector<bool> passed(E); // 通過済みかどうかのメモ用
std::queue<size_t> bfs;
bfs.push(S);
while (!bfs.empty()) {
auto now = bfs.front();
bfs.pop();
if (G == now) {
reachable = true;
break;
}
// 通過済みなので更新する必要がない場合
if (passed[now]) {
continue;
}
passed[now] = true;
for (auto next : adj[now]) {
if (!passed[next]) {
bfs.push(next);
}
}
}
using std::cout;
if (reachable) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
こういった幅優先探索は、迷路やパズルを解いたり、ゲームの対戦用 CPU を作ったりといったことにまで応用できるよ。
ちなみに、入力例2 のようにループする状況のために passed で記録する必要がある。逆にループしない場合は passed をチェック/記録する必要はない。
priority_queue
データを入れると自動で降順 (大きい→小さい順) にソートされて、その片端からしか取り出せないコンテナ。
これは #include <queue> が必要。std::queue と同じ queue ファイルに入ってる。
std::priority_queue<int> Q;
// push と pop があるけど他のとはかなり違う
Q.push(2); // {2}
Q.push(4); // {2, 4}
Q.push(3); // {2, 3, 4}
Q.push(1); // {1, 2, 3, 4}
// empty で空かどうかを bool で取得
while (!Q.empty()) {
// top でキューの末尾を取得
auto head = Q.top();
// pop で末尾を削除
Q.pop();
std::cout << head << " ";
}
ソートの順番を変えるには、テンプレート引数にソートに使う関数型も渡す。
デフォルトは std::less になっている。これは < 演算子の意味があり、前の要素 < 次の要素 になるようにソートする。
逆に std::greater は > 演算子の意味があり、前の要素 > 次の要素 になるようにソートする。
基本的にこのどっちかを第三テンプレート引数に渡す。
何故か第三引数だから、第二引数のコンテナ型の指定もしなきゃいけない。これは std::vector でいい。
std::priority_queue<
int, // 要素型
std::vector<int>, // std::vector<要素型> で OK
std::greater<> // ソートに使う関数型、テンプレート引数は空でいい
> Q;
Q.push(2); // {2}
Q.push(4); // {4, 2}
Q.push(3); // {4, 3, 2}
Q.push(1); // {4, 3, 2, 1}
例題
それでは例題を (ry
入力:
V E S G src1 dst1 duration1 src2 dst2 duration2 : srcE dstE durationE
VとEは正の整数SとGは0以上E未満の整数srcEとdstEは0以上V未満の整数durationEは正の整数
V個の異空間がある。異空間どうしの間には二つの空間をつなぐ一方通行のポータルがあり、
src番目の空間からdst番目の空間に向かってだけ移動できる。この移動には、
duration秒時間がかかる。ポータルを利用すると、
S番目の空間からG番目の空間へ必ず移動できる。この移動にかかる最小時間と、改行を出力せよ。
入力例1:
3 3 0 2 0 2 40 0 1 10 1 2 20出力例1:
30
入力例2:
6 9 0 4 0 1 7 0 2 9 0 5 14 1 3 15 2 3 11 2 5 2 5 4 9 3 4 6 1 2 10出力例2:
20
入力の処理は、durationE に対応するぶんを変える。
using std::cin;
int V, E, S, G;
cin >> V >> E >> S >> G;
std::vector<std::vector<size_t>> adj(V);
std::vector<std::vector<int>> cost(V, std::vector<int>(V));
for (int i = 0; i < E; ++i) {
int src, dst, duration;
cin >> src >> dst >> duration;
adj[src].push_back(dst);
cost[src][dst] = duration; // src から dst へかかる時間をこう表現することにする
}
さっきの queue を使った幅優先探索と似たやり方で解ける。察していると思うけど、今回は priority_queue のほうがいい。
これを使うと、こんなアルゴリズムになる。
- 最初の空間である
S番目のイテレータをキューにpush - キューが空になるまで繰り返し
- キューの
topをcost,nowとして取り出し、pop nowのportalsの各要素をnextとして見るnowのcost_from_Sと、nextと同じインデックスのportal_costsを足す (見ているnow)。これをnew_costとするnew_costがnextのcost_from_Sより小さいい場合nextのcost_from_Sにnew_costを代入nextをキューにpush
- キューの
このアルゴリズムを、発明者にちなんでダイクストラ法っていう。
// 最短距離のメモ用。最大値にしておいて、これから小さくしていく
std::vector<int> cost_from_S(V,
std::numeric_limits<int>::max() // 型の最大値を取得する関数
);
cost_from_S[S] = 0;
// pair に コストとインデックスを格納する
std::priority_queue<
std::pair<int, size_t>,
std::vector<std::pair<int, size_t>>,
std::greater<>
> Q;
Q.push({0, S});
while (!Q.empty()) {
auto pair = Q.top();
int now_cost = pair.first;
size_t now = pair.second;
Q.pop();
// cost_from_S[now] を更新する必要がない場合
if (cost_from_S[now] < now_cost) {
continue;
}
for (auto next : adj[now]) {
auto new_cost = now_cost + cost[now][next];
if (new_cost < cost_from_S[next]) {
cost_from_S[next] = new_cost;
Q.push({cost_from_S[next], next});
}
}
}
あとは出力しておわり。
std::cout << cost_from_S[G] << "\n";
全体はこうなった。私にでも何日かかかるくらい難しかったから、サクサクできたならすごいよ。
#include <iostream>
#include <queue>
int main() {
using std::cin;
int V, E, S, G;
cin >> V >> E >> S >> G;
std::vector<std::vector<size_t>> adj(V);
std::vector<std::vector<int>> cost(V, std::vector<int>(V));
for (int i = 0; i < E; ++i) {
int src, dst, duration;
cin >> src >> dst >> duration;
adj[src].push_back(dst);
cost[src][dst] = duration;
}
// 最短距離のメモ用。最大値にしておいて、これから小さくしていく
std::vector<int> cost_from_S(V,
std::numeric_limits<int>::max() // 型の最大値を取得する関数
);
cost_from_S[S] = 0;
// pair に コストとインデックスを格納する
std::priority_queue<
std::pair<int, size_t>,
std::vector<std::pair<int, size_t>>,
std::greater<>
> Q;
Q.push({0, S});
while (!Q.empty()) {
auto pair = Q.top();
int now_cost = pair.first;
size_t now = pair.second;
Q.pop();
// cost_from_S[now] を更新する必要がない場合
if (cost_from_S[now] < now_cost) {
continue;
}
for (auto next : adj[now]) {
auto new_cost = now_cost + cost[now][next];
if (new_cost < cost_from_S[next]) {
cost_from_S[next] = new_cost;
Q.push({cost_from_S[next], next});
}
}
}
std::cout << cost_from_S[G] << "\n";
}
こういうふうに経路について処理する、グラフ理論 に関する問題を章末問題に出しておくね。