アルゴ式（beta版）の「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキューからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
僕が作成、提出したコードは、以下のとおりです。
Q1. 閉じた筒とボール (スタック)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q1. 閉じた筒とボール (スタック) https://algo-method.com/tasks/886 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ /*~操作はじめ~ A AB ABC AB ABX ABXY ABXYZ ABXY ~操作おわり~*/ printf("A\nB\nX\nY\n"); return 0; }
Q2. 開いた筒とボール (キュー)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q2. 開いた筒とボール (キュー) https://algo-method.com/tasks/885 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ /*~操作はじめ~ A AB ABC BC BCX BCXY BCXYZ CXYZ ~操作おわり~*/ printf("C\nX\nY\nZ\n"); return 0; }
Q3. キューを配列で実装
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q3. キューを配列で実装 https://algo-method.com/tasks/884 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,q; cin>>n>>q; vector<ll> a(n,-1); ll head=0,tail=0; for(ll i=0;i<q;i++){ ll num; cin>>num; if(num==0){ ll v; cin>>v; a[tail]=v; tail++; if(tail==n){ tail=0; } }else{ a[head]=-1; head++; if(head==n){ head=0; } } } for(ll i=0;i<n;i++){ cout<<a[i]<<endl; } return 0; }
Q4. 逆ポーランド記法の計算
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q4. 逆ポーランド記法の計算 https://algo-method.com/tasks/883 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ string x; ll n; cin>>x>>n; vector<string> s(n); for(ll i=0;i<n;i++){ cin>>s[i]; } stack<ll> num; for(ll i=0;i<n;i++){ string t=s[i]; if(t=="+" || t=="-" || t=="*"){ ll n2=num.top(); num.pop(); ll n1=num.top(); num.pop(); ll j; if(t=="+"){ j=n1+n2; }else if(t=="-"){ j=n1-n2; }else if(t=="*"){ j=n1*n2; } num.push(j); }else{ ll j=stoi(t); num.push(j); } } ll ans=num.top(); cout<<x<<"="<<ans<<endl; return 0; }
Q5. 括弧列の対応関係 (1)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q5. 括弧列の対応関係 (1) https://algo-method.com/tasks/887 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; string s; cin>>n>>s; stack<ll> st; ll ans=-1; for(ll i=0;i<n;i++){ if(s[i]=='('){ st.push(i); }else{ ll num=st.top(); st.pop(); if(num==0){ ans=i; } } } cout<<ans<<endl; return 0; }
Q6. 括弧列の対応関係 (2)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q6. 括弧列の対応関係 (2) https://algo-method.com/tasks/890 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; string s; cin>>n>>s; stack<ll> st; vector<ll> v(n,-1); for(ll i=0;i<n;i++){ if(s[i]=='('){ st.push(i); }else{ ll nu=st.top(); st.pop(); ll num=i; v[nu]=num; v[num]=nu; } } ll q; cin>>q; for(ll i=0;i<q;i++){ ll k; cin>>k; cout<<v[k]<<endl; } return 0; }
Q7. 括弧列の整合性判定
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q7. 括弧列の整合性判定 https://algo-method.com/tasks/888 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; string s; cin>>n>>s; stack<ll> st; for(ll i=0;i<n;i++){ if(s[i]=='('){ st.push(i); }else{ if(st.size()==0){ cout<<"No"<<endl; return 0; } st.pop(); } } if(st.size()>0){ cout<<"No"<<endl; return 0; } cout<<"Yes"<<endl; return 0; }
Q8. スパン
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q8. スパン https://algo-method.com/tasks/893 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> a(n); for(ll i=0;i<n;i++){ cin>>a[i]; } stack<pair<ll,ll>> st; st.push(pair(0,0)); for(ll i=1;i<n;i++){ ll A=a[i]; while(A<=st.top().first){ st.pop(); } ll ans=i-st.top().second; cout<<ans<<endl; st.push(pair(A,i)); } return 0; }
Q9. タスクスケジューリング (1)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q9. タスクスケジューリング (1) https://algo-method.com/tasks/882 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll q; cin>>q; queue<string> que; for(ll i=0;i<q;i++){ ll num; cin>>num; if(num==0){ string s; cin>>s; que.push(s); }else{ cout<<que.front()<<endl; que.pop(); } } return 0; }
Q10. タスクスケジューリング (2)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q10. タスクスケジューリング (2) https://algo-method.com/tasks/889 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll x,q; cin>>x>>q; queue<ll> que; ll sum=0; for(ll i=0;i<q;i++){ ll num,t; cin>>num>>t; if(num==0){ que.push(t+x); }else{ while(que.size()>0 && que.front()<=t){ que.pop(); sum++; } cout<<sum<<endl; } } return 0; }
Q11. シール貼り
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q11. シール貼り https://algo-method.com/tasks/891 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,l; cin>>n>>l; vector<ll> a(n); for(ll i=0;i<n;i++){ cin>>a[i]; } vector<ll> v(n,0); queue<ll> que; ll num=0; for(ll i=0;i<n;i++){ v[i]=max(a[i]-num,0LL); que.push(v[i]); num+=v[i]; if(que.size()>=l){ num-=que.front(); que.pop(); } } ll ans=0; for(ll i=0;i<n;i++){ ans+=v[i]; } cout<<ans<<endl; return 0; }
Q12. 幅優先探索
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー Q12. 幅優先探索 https://algo-method.com/tasks/892 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll dx[4]={1,0,-1,0}; ll dy[4]={0,1,0,-1}; int main(void){ ll h,w; cin>>h>>w; vector<string> s(h); for(ll i=0;i<h;i++){ cin>>s[i]; } ll sx=-1,sy=-1,gx=-1,gy=-1; for(ll x=0;x<h;x++){ for(ll y=0;y<w;y++){ if(s[x][y]=='S'){ sx=x; sy=y; } if(s[x][y]=='G'){ gx=x; gy=y; } } } vector<vector<ll>> vv(h,vector<ll>(w,-1)); queue<pair<ll,ll>> que; vv[sx][sy]=0; que.push(make_pair(sx,sy)); while(que.size()>0){ auto [x,y]=que.front(); que.pop(); for(ll i=0;i<4;i++){ ll nx=x+dx[i],ny=y+dy[i]; if((0<=nx && nx<h) && (0<=ny && ny<w)){ if(s[nx][ny]=='#'){ continue; } if(vv[nx][ny]!=-1){ continue; } vv[nx][ny]=vv[x][y]+1; que.push(make_pair(nx,ny)); } } } cout<<vv[gx][gy]<<endl; return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com
