5.1 向量（vector）

向量（vector）是可以改变其大小的线性序列容器。

#include <vector>
定义：vector<typename> name;
两个状态:：empty(), size()
尾部元素的添加或删除：push_back(), pop_back()
元素访问：1. 下标访问（类似数组） 2. 迭代器（类似指针）访问
元素操作：insert(), erase(), clear()
迭代器操作：begin(), end()

例题5.1 完数与盈数

提交地址

#include <iostream>
#include <vector>

using namespace std; 

int main(int argc, char** argv) {
	vector<int> wanshu;
	vector<int> yingshu;
	for(int i=2; i<=60; i++){
		int sum = 0;
		for(int j=1; j<=i/2; j++){
			if(i % j == 0){
				sum += j;
			}
		}
		if(sum == i) wanshu.push_back(i);
		else if(sum > i) yingshu.push_back(i);
	}
	cout << "E:";
	for(int v:wanshu) cout << " " << v;
	cout << endl << "G:";
	for(int v:yingshu) cout << " " << v;
	return 0;
}

5.2 队列（queue）

队列中各个元素的操作次序必定遵循先进先出(FIFO)规则。

#include <queue>
定义：queue<typename> name;
状态：empty(), size()
添加和删除：push(), pop()
元素的访问：front(), back()

例题5.2 约瑟夫问题No.2

// 使用队列模拟的方法 
#include <iostream>
#include <queue>

using namespace std; 

int main(int argc, char** argv) {
	int n, p, m;
	while(cin >> n >> p >> m){
		if(n==0 && p==0 && m==0){
			break;
		}
		queue<int> children;
		for(int i=1; i<=n; i++){	//依次加入队列 
			children.push(i);
		}
		for(int i=0; i<p-1; i++){		//使编号为p的小孩在队首 
			children.push(children.front());
			children.pop();
		}
		while(!children.empty()){
			if(children.size() == 1){
				cout << children.front() << endl;
				children.pop();
			}
			else{
				for(int i=0; i<m-1; i++){
					children.push(children.front());
					children.pop();
				}
				cout << children.front() << ",";
				children.pop();
			}
		}
	}
	return 0;
}

例题5.3 猫狗收容所

#include <iostream>
#include <queue>
#include <vector>

using namespace std; 

struct animal{
	int number;
	int order;
	animal(int n, int o): number(n), order(o) {};	//构造函数 
};

int main(int argc, char** argv) {
	int n, m, t;
	queue<animal> dog;
	queue<animal> cat;
	vector<int> out;
	int order = 1;
	cin >> n;
	while(n--){
		cin >> m >> t;
		if(m == 1){
			if(t > 0){
				dog.push(animal(t, order++));
			}
			else if(t < 0){
				cat.push(animal(t, order++));
			}
		}
		else if(m == 2){
			if(t == 0){
				if(!cat.empty() && !dog.empty()){
					if(cat.front().order < dog.front().order){
						out.push_back(cat.front().number);
						cat.pop();
					}
					else{
						out.push_back(dog.front().number);
						dog.pop();
					}
				}
				else if(cat.empty() && !dog.empty()){
					out.push_back(dog.front().number);
					dog.pop();
				}
				else if(!cat.empty() && dog.empty()){
					out.push_back(cat.front().number);
					cat.pop();
				}
			}
			else if(t == 1 && !dog.empty()){
				out.push_back(dog.front().number);
				dog.pop();
			}
			else if(t == -1 && !cat.empty()){
				out.push_back(cat.front().number);
				cat.pop();
			}
		}
	}
	for(int o:out) cout << o << " ";
	return 0;
}

5.3 栈（stack）

栈中各个元素的操作次序必定遵循后进先出（LIFO）规则。

#include <stack>
定义：stack<typename> name;
状态：empty(), size()
添加或删除：push(), pop()
访问：top()

例题5.4 Zero-complexity Ttransposition

提交地址

#include <iostream>
#include <stack>

using namespace std; 

int main(int argc, char** argv) {
	int n;
	stack<long long> rev;
	cin >> n;
	for(int i=0; i<n; i++){
		int num;
		cin >> num;
		rev.push(num);
	}
	while(!rev.empty()){
		cout << rev.top() << " ";
		rev.pop();
	}
	return 0;
}

例题5.5 括号匹配问题

#include <iostream>
#include <stack>
#include <string>

using namespace std; 

int main(int argc, char** argv) {
	string str;
	while(cin >> str){
		stack<int> brackets;
		string answer(str.size(), ' ');	//初始化answer字符串 
		for(int i=0; i<str.size(); i++){
			if(str[i] == '('){
				brackets.push(i);
			}
			else if(str[i] == ')'){
				if(!brackets.empty()){
					brackets.pop();
				}
				else{
					answer[i] = '?';
				}
			}
		}
		while(!brackets.empty()){
			int num = brackets.top();
			answer[num] = '$';
			brackets.pop();
		}
		cout << str << endl;
		cout << answer << endl;
	}
	return 0;
}

例题5.6 简单计算器

提交地址

//这一题没有处理括号，相对简单一些 
#include <iostream>
#include <stack>
#include <cctype>
#include <string>
#include <map> 

using namespace std; 

double GetNumber(string str, int& index){
	double num = 0;
	while(isdigit(str[index])){
		num = num*10 + str[index] - '0';
		index++;
	}
	return num;
}

double Calculate(double x, double y, char oper){
	if(oper == '+'){
		return x + y;
	}
	if(oper == '/'){
		return x / y;
	}
	if(oper == '*'){
		return x * y;
	}
	if(oper == '-'){
		return x - y;
	}
}

int main(int argc, char** argv) {
	map<char, int> prior = {{'#',0}, {'$',1}, {'+',2}, {'-',2}, {'*',3}, {'/',3}};
	string str;
	while(getline(cin, str)){
		if(str == "0"){
			break;
		}
		int index = 0;
		stack<char> oper;
		stack<double> data;
		str += '$';
		oper.push('#');
		while(index < str.size()){
			if(str[index] == ' '){
				index++;
			}
			else if(isdigit(str[index])){
				data.push(GetNumber(str, index));
			}
			else{
				if(prior[str[index]] > prior[oper.top()]){
					oper.push(str[index]);
					index++;
				}
				else{
					double y = data.top();
					data.pop();
					double x = data.top();
					data.pop();
					data.push(Calculate(x, y, oper.top()));
					oper.pop();
				}
			}
		}
		printf("%.2f\n", data.top());
	}
	return 0;
}

习题

习题5.1 堆栈的使用

提交地址

#include <iostream>
#include <stack>

using namespace std; 

int main(int argc, char** argv) {
	int n;
	while(cin >> n){
		if(n == 0){
			break;
		}
		stack<int> num;
		char tmp;
		int t;
		while(n--){
			cin >> tmp;
			if(tmp == 'A'){
				if(num.empty()){
					cout << "E" << endl;
				}
				else{
					cout << num.top() << endl;
				}
			}
			else if(tmp == 'P'){
				cin >> t;
				num.push(t);
			}
			else if(tmp == 'O'){
				if(!num.empty()){
					num.pop();
				}
			}
		}
		cout << endl;
	}
	return 0;
}