1 队列—queue
我想很多人都知道这个神器—queue
队列queue（FIFO），！！需要头文件 #incldue
有几种常见操作：
1.queue q 定义一个某类型的队列q
2.q.push(元素) 把一个元素压入队列q的队首
3.q.pop() 弹出队尾元素
4.q.size() 返回队列中元素的个数
5.q.empty() 判断队列是否为空，为空则返回1，不为空则返回0
6.q.front()返回队首元素
2 栈—stack
stack是一种类似于队列（FIFO）的另一种（LIFO）链式储存结构
栈stack,！！需要头文件 #include
c++中STL提供了几种常见操作：
1.stack s定义一个某类型的队列s
2.s.push(元素)把一个元素压入s的栈顶
3.s.pop()弹出栈顶元素
4.s.size()返回栈中元素的个数
5.s.empty()判断是否空栈，为空则返回1，不为空则返回0
6.s.top()返回栈顶元素
3 向量—vector
向量vector俗称"动态数组"，因为其可以像数组一样进行下标运算，而且使用时，vector自动动态申请储存空间，并且拥有更多操作，亦可以用于sort等函数之中
向量vector,！！需要头文件 #include
c++中STL提供了几种常见操作：
1.vector v定义一个某类型的向量v
2.v.push_back()在数组v的最后添加一个数据
3.v.pop_back()弹出数组v的最后一个数据
4.v.begin()返回v的首部元素的迭代器
5.v.end()返回v的尾部元素的后一个元素的的迭代器
6.v.back()返回v的首元素
7.v.front()返回v的尾元素
8.v.size()返回v中的元素个数
9.v.erase()删除指针指向的数据项
10.v.clear()弹出v中所有元素
11.v.empty()判断是否为空，为空则返回1，不为空则返回0
下面来举几个栗子：
1
输入n个数，逆序输出这n个数（栈实现）
#include#include using namespace std; int main() { int n; cin>>n; stackint> s; for(int i=1;i) { int a; cin>>a; s.push(a); } while(s.size()) { cout" "; s.pop(); } }
2
输入n个数，由小到大排序后输出（向量实现）
#include#include #include using namespace std; int main() { int n; cin>>n; vectorint> v; for(int i=1;i) { int a; cin>>a; v.push_back(a); } sort(v.begin(),v.end());//STL中sort的用法请见我后面的文章 vectorint>:: iterator it=v.begin();//STL中迭代器的用法请见我后面的文章 for(it;it ) { cout" "; } }
3
走迷宫： 一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。 给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。 input： 第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1
e.g.input: 5 5 ..### #.... #.#.# #.#.# #.#.. e.g.output: 9
#include#include using namespace std; int vis[1000][1000]; struct node { int x,y,step; }; int main() { queue q; int R,C; cin>>R>>C; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; char map[1000][1000]; for(int i=1;i) { for(int o=1;o) { cin>>map[i][o]; } } node yy; yy.x=1; yy.y=1; yy.step=1; q.push(yy);//队列实现宽搜 while(q.size()) { node op; op=q.front(); for(int i=0;i4;i++) { int qqx=op.x+dx[i]; int qqy=op.y+dy[i]; if(map[qqx][qqy]=‘.‘&&qqx>0&&qqx0&&qqyvis[qqx][qqy]) { map[qqx][qqy]=‘#‘; vis[qqx][qqy]=true; node pp; pp.x=qqx; pp.y=qqy; pp.step=op.step+1; q.push(pp); if(qqx==R&&qqy==C) { cout1; return 0; } } } q.pop(); } }