栈(Stack)

概念：就像一个盒子一样，进去想出来就得等上面的先出去，也就是“先进后出”。

往往栈的功能有上面四种，下面我们手写一个栈来实现这四种功能来更好的理解一下。

模拟栈的实现：

#include<iostream>
#include<string>

using namespace std;

const int N = 100010;

int stk[N], tt; //tt为栈顶指针，初始化为0 

int main(){
	int n; //要进行几次操作 
	cin >> n;
	string op; //要进行的操作
	
	while (n --){
		cin >> op;
		if (op == "push"){
			int x; //需要入栈的数 
			cin >> x;
			stk[++ tt] = x;  
		}
		else if (op == "pop") tt --;
		else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;
		else cout << stk[tt] << endl;
	} 
	
	return 0;
} 

模拟栈的实现，只需要控制栈顶指针tt即可。

如果想访问栈顶元素时，只需访问tt所指位置的元素即可。

想往栈添加元素，只需让tt加1，指向下一个位置，然后在该位置存数即可。

想删除栈顶元素，只需让tt减1，这个元素也就不在是栈顶元素，也就是被移出了栈。

判断栈是否为空，只需看tt是否为0即可。

当然比赛中我们直接调用STL库即可。

#include<stack> //头文件

stack<int> s; //定义一个栈

s.size(); //栈中元素的数量 

s.empty(); //栈是否为空 

s.push(); //将此元素压入栈 

s.pop(); //弹出栈顶元素
 
s.top(); //访问栈顶元素 

队列

概念：就像排队一样，先来的人排在前面，后来的人只能排在队尾，先来的人可以先走，后来的人只能后走，也就是“先进先出”。

往往队列的功能有上面四种，下面我们手写一个队列来实现这四种功能来更好的理解一下。

#include<iostream>
#include<string>

using namespace std;

const int N = 100010;

int q[N];
int hh, tt = -1; //hh为队头，tt为队尾 

int main(){
	int n; //要进行的操作数 
	cin >> n;
	
	while (n --){
		string op;
		cin >> op; //要进行的操作
		if (op == "push"){
			int x; //要加入的数 
			cin >> x;
			q[++ tt] = x; 
		}
		else if (op == "pop") hh ++;
		else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;
		else cout << q[hh] << endl; 
	}
	
	return 0;
}

模拟队列的实现，只需要控制队头hh和队尾tt即可。

如果想查询队头元素，只需查看hh所指地方值即可。

如果想添加一个元素，只需让tt加1，指向下一个位置，在该位置存数即可。

想删除元素，只需让hh加1，让他指向下一个元素，该元素也就删除了。

判断队列是否为空，只需看队头是否大于队尾即可。如果大于队尾则空，反之则不空。

接下来我们看STL库中的队列方法。

#include<queue>

queue<int> q; //定义一个队列

que.size(); //返回队列元素数量

que.empty(); //返回队列是否为空

que.push(); //加入队列

que.pop(); //出队

que.front(); //返回队首

que.back(); //返回队尾 

下面我们来看一道天梯赛L2难度的真题：

例题

一种自动包装机的结构如图 1 所示。首先机器中有 N 条轨道，放置了一些物品。轨道下面有一个筐。当某条轨道的按钮被按下时，活塞向左推动，将轨道尽头的一件物品推落筐中。当 0 号按钮被按下时，机械手将抓取筐顶部的一件物品，放到流水线上。图 2 显示了顺序按下按钮 3、2、3、0、1、2、0 后包装机的状态。


一种特殊情况是，因为筐的容量是有限的，当筐已经满了，但仍然有某条轨道的按钮被按下时，系统应强制启动 0 号键，先从筐里抓出一件物品，再将对应轨道的物品推落。此外，如果轨道已经空了，再按对应的按钮不会发生任何事；同样的，如果筐是空的，按 0 号按钮也不会发生任何事。
现给定一系列按钮操作，请你依次列出流水线上的物品。

分析

通过对题目的分析，我们发现只需要将轨道看成队列，框看成队列，然后模拟这个过程就可以。

代码

#include<iostream>
#include<queue>
#include<stack>

using namespace std;

const int N = 110;

queue<char> q[N]; //轨道
stack<char> s; //筐
int n, m, smax;

int main(){
	cin >> n >> m >> smax;
	for (int i = 1; i <= n; i ++) 
		for (int j = 0; j < m; j ++){
			char c;
			cin >> c;
			q[i].push(c);
		}
		
	int x;
	while (cin >> x, x != -1){
		if (x == 0 && !s.empty()){ //注意需要判断一下是否为空，如果在为空状态下访问栈顶元素会报错
			cout << s.top();
			s.pop();
		}
		if (x > 0 && s.size() < smax && q[x].size()){
			s.push(q[x].front());
			q[x].pop();
		}
		else if (x > 0 && s.size() >= smax && q[x].size()){
			cout << s.top();
			s.pop();
			s.push(q[x].front());
			q[x].pop();
		}
	}
	
	return 0;
}

vector

概念：就像一个长度可变的数组一样，把他当成数组处理就可以。

STL库：

#include<vector>

vector<int> v; //定义一个vector

v.push_back(item); //向v后加一个元素

v.pop_back(); //删除v最后一个元素

v.size(); //获取v中元素个数

v.empty(); //判断v是否为空

v.clear(); //清空v中的元素

v[index]; //获取v中下标为index的元素O(1)

v.begin(); //返回指向第一个元素的迭代器

v.end(); //返回指向vector末尾(最后一个元素之后的那个位置)的迭代器

v.front(); //返回第一个元素

v.back(); //返回最后一个元素

set

概念：相当于是数学的集合，会对相同的元素进行去重处理并默认排序。

STL库：

#include<set>

set<int>s; //定义一个set

s.insert(); //插入一个元素 

s.size(); //获取元素的个数

s.empty(); //判断是否为空

s.clear(); //清空s

s.count(item); //返回s中item的数量，因为集合中的元素不能重复，因此只能返回0或1 

map

概念：map是一个键值对，是一个映射关系，你可以理解为帮你封装好了的hash表，通过键访问你的值。

STL库：

#include<map>

map<int,int> mp; //定义一个map

mp.size(); //获取元素个数

mp.empty(); //判断是否为空

mp.clear(); //清空mp

mp[key]=tmp; //可以把键值对key—value中的value赋值为tmp,如果没有对应的键值对,则将该键值对插入到map中