栈和队列——标准模板库(STL)
栈(STACK)
stk−−>栈stk-->栈stk−−>栈 stack<int>stack<int>stack<int>
1.定义 stack<int> stk 栈名
2.入栈 stk.push(变量名); 入栈
3.出栈 stk.pop(); 查看栈顶int tmp = stk.top();栈顶
4.栈长度 stk.size();
例题:验证栈序列
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
队列(QUEUE)
1.定义:一种线性表;
2.性质:先进先出,后进后出;
队列数组实现
步骤 代码 释义 1 front rear = 0; 一个指向队头前一个元素,一个尾巴 2 q[++rear]=x; 入队 3 front++; 4 cout<<q[front+1]; 5 cout<<rear-front; 6 当front,rear相等时记得先判空
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题:约瑟夫问题2
> 题目描述
>
> > n个人(编号0到n-1)围成一圈,从第一个人开始报数1,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,问最后一个人,编号多少?
> 输入格式
>
> > n m
> 输出格式
>
> > 出圈的编号
> 输入输出样例
>
> > 输入#1
> >
> > > 8 3
> > 输出#1
> >
> > > 6
> 说明/提示
>
> > 50%的数据0<n,m<=100
> > 100%的数据0<n<=1000000,0<m<=100
参考代码如下
优先队列(PRIORITY_QUEUE()PRIORITY\_QUEUE()PRIORITY_QUEUE())
1.1.1.定义优先队列
2.2.2.取最大值 O(LOGN)O(LOG_N)O(LOGN )
3.3.3.删除最大的元素 O(LOGN)O(LOG_N)O(LOGN )
4.4.4.放入一个元素 O(LOGN)O(LOG_N)O(LOGN )
5.5.5.判断是否为空
6.6.6.优先队列的长度
结构体重载
注:可以将return a.x < b.x;改成//return a.x > b.x;,意思就变成了把小的x放在前面 。大根堆为默认。