第 01 篇、stack 的運用 - 進階程式設計 - 多元選修 (高中) | Zrn Code = 為了夢想、永不停歇

像是自助餐廳的餐盤架，最新補充的乾淨餐盤堆疊在上方，客人取用餐盤時，從最上方的開始拿。

# 基本用法

名稱	意義
`stack<int> sk`	建立一個 `int` 型別的 `stack`
`sk.size()`	堆疊元素數量
`sk.empty()`	判斷堆疊是否為空
`sk.push(x)`	從堆疊「頂端」加入一個元素 x
`sk.pop()`	刪除堆疊頂端元素
`sk.top()`	取得堆疊頂端元素

刪除 sk.top() 並不會刪除頂端元素

# 上課例題

# a034: 二進位制轉換

將一個 10 進位的數字換成二進位數字

每一次就對 n 做一次取餘數，並記錄下來，
再往右邊推移位 (除以二) 直到 n 等於 0 為止。
之後，再倒著輸出出來就好了啊！！

	#include<iostream>
	using namespace std;

	int main(){
	int n,i;
	int a[1000];
	while(cin>>n){
	i=-1;
	while(n){
	a[++i]=n%2;
	n/=2;
	}
	for(int j =i; j>=0;j--)
	cout<<a[j];
	cout<<endl;
	}
	}

因為結果是倒著輸出的部分可以使用 stack 的 Last In First Out 特性將陣列替代掉。

	#include <bits/stdc++.h>
	using namespace std;

	int main(){
	int n;
	while(cin>>n){
	stack<int>s;
	while(n){
	s.push(n%2);
	n/=2;
	}
	while(s.size()){
	cout<<s.top();
	s.pop();
	}
	cout<<endl;
	}
	}

# b838: 104 北二 2. 括號問題

請你寫一個程式判斷一個式子中的括號是否正確，
若正確的話，請輸出式子中有幾對括號，
若錯誤的話，請輸出 0。

讀入一個 ( 就加入堆疊，讀入一個 ) 就刪除一個堆疊中的 ( 。
若運算中，堆疊元素量不足為不合法；
運算結束後，若堆疊能有元素亦為不合法。

	#include <bits/stdc++.h>
	using namespace std;

	int main(){
	int n;
	while(cin>>n){
	cin.ignore();
	while(n--){
	stack <char> st;
	string s;
	bool flag = true;
	int ans=0;
	getline(cin,s);
	for(int i=0;i<s.size();i++){
	if(s[i]=='(') st.push('(');
	else if(s[i]==')') {
	if(!st.empty())st.pop(), ans++;
	else { cout<<"0\n" ; flag=false; break; }
	}
	}
	if(!st.empty()) { cout<<"0\n"; flag=false; }
	if(flag) cout<<ans<<endl;
	}
	}
	}

# 延伸練習

# b923: stack 堆疊的模板題

實作 stack 的幾種操作

刪除堆頂元素
輸出頂端元素
丟數字進堆疊

	#include <iostream>
	#include<stack>
	using namespace std;

	int main(){
	stack<int> sk;
	int n;
	cin>>n;
	while(n--){
	int m;
	cin>>m;
	if(m==3){
	int temp;
	cin>>temp;
	sk.push(temp);
	}
	else if(m==2)
	cout<<sk.top()<<endl;
	else
	sk.pop();
	}
	}

# d318: 11185 - Ternary

將一個 10 進位的數字換成三進位數字

跟轉換二進位的過程及方式一樣，只需要改成取 3 的餘數即可

	#include <bits/stdc++.h>
	using namespace std;

	int main(){
	int n;
	while(cin>>n){
	stack<int>s;
	if(n==0){
	cout<<0<<endl;
	continue;
	}
	if(n<0){
	break;
	}
	while(n){
	s.push(n%3);
	n/=3;
	}
	while(s.size()){
	cout<<s.top();
	s.pop();
	}
	cout<<endl;
	}

	}

# a132: 10931 - Parity

整數 n 的「同位元」定義為：其二進位表示法中每位元的和再除以 2 的餘數。
計算一個整數 1 ≤ I ≤ 2147483647 的同位元。

運用 stack 將數字先轉為二進位，
並再將所有的一的數量記錄下來即可。

	#include <bits/stdc++.h>
	using namespace std;

	int main(){
	int n;
	while(cin>>n&&n){
	stack<int>s;
	int cnt = 0;
	while(n){
	s.push(n%2);
	if(n%2) cnt++;
	n/=2;
	}
	cout<<"The parity of ";
	while(s.size()){
	cout<<s.top();
	s.pop();
	}
	cout<< " is "<<cnt<<" (mod 2).\n";
	}
	}

# a565: 2.p&q 的邂逅

每一組名單中，p 與 q 之間可能相鄰或者以「.」分隔，「.」的數量多寡不定，
目標就是盡量找出所有可以配成對的 p 與 q。

建立一個空的堆疊，
每當讀到一個 p 就將其加入堆疊，
若讀到 q 則判斷堆疊是否為空，
若不為空，則將從堆疊上取走一個 p，並總數加一，否則忽視。

	#include <bits/stdc++.h>
	using namespace std;

	int main() {
	int n;
	scanf("%d\n",&n);
	while(n--){
	stack <char> sk;
	int cnt=0;
	while(true){
	char c = getchar();
	if(c=='.')
	continue;
	else if(c=='p')
	sk.push('p');
	else if(c=='q')
	if(!sk.empty()&&sk.top()=='p')
	sk.pop(),cnt++;
	else
	break;
	}
	printf("%d\n",cnt);
	}
	}

STL stack 多元選修