栈、队列函数
dengwenrui
2021-02-23 21:57:09
```
栈
头文件：#include<stack>
定义栈：stack <int> st;
进栈： st.push(x);
取栈顶元素：x=st.top();
出栈： st.pop();
判栈空： st.empty();
栈中数据的个数：n=st.size();
队列
1.单项队列
头文件：#include<queue>
定义：queue<int>q;
进队列：q.push(x);
出队列：q.pop();
访问队首元素：x=q.front();
访问队尾元素：x=q.back();
判队空：q.empty();
队列中数据的个数：n=q.size();
2.双向队列
头文件：#include<queue>
定义：deque<int>dq;
入队：dq.push_front(x); dq.push_back(x);
出队：dq.pop_front(); dq.pop_back();
判队空：dq.empty();
访问队首元素：x=dq.front();
访问队尾元素：x=dq.back();
队列中数据的个数：n=dq.size();
```
```
二分查找
1.查找一个数在从大到小排序后的数组的位置
#include<bits/stdc++.h>
using namespace std;
int lt,rt,mid,n,a[10005],x;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
cin>>x;
lt=1;
rt=n;
while(lt<=rt)
{
mid=(lt+rt)/2;
if(a[mid]==x)
{
cout<<mid;
return 0;
}
if(a[mid]>x)
rt=mid-1;
else
lt=mid+1;
}
cout<<"Not find";
return 0;
}
2.查找一个数在从大到小排序后的数组的最左边的位置
#include<bits/stdc++.h>
using namespace std;
int lt,rt,mid,n,a[10005],x;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
cin>>x;
lt=0;
rt=n+1;
while(lt+1<rt)
{
mid=(lt+rt)/2;
if(a[mid]>=x)
rt=mid;
else
lt=mid;
}
```
```
cout<<rt;
return 0;
}
3.查找一个数在从大到小排序后的数组的最右边的位置
#include<bits/stdc++.h>
using namespace std;
int lt,rt,mid,n,a[10005],x;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
cin>>x;
lt=0;
rt=n+1;
while(lt+1<rt)
{
mid=(lt+rt)/2;
if(a[mid]>x)
rt=mid;
else
lt=mid;
}
cout<<lt;
return 0;
}
二分答案
1.二分答案的应用条件：
1.确定答案的范围，即答案的最大值与最小值。
2.答案具有单调性。
3.容易判断某个值是否为答案。
（即二分过程中，能验证mid指向的点是否为答案）
4.当你看到找极大值中的最小值或者求极小值中的最大值的题目时，可以考虑二分答案。
2.二分答案要注意的地方：
1.left和right的初始值。
2.验证答案是否可行时，left和right值的变化。
3.当left与right相邻时停止循环，并输出值。
3.程序实例
【问题描述】
木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余）。需要得到的小段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位时cm。原木的长度都是正整数，我们要求得到的小段木头的长度也是正整数。
```
```
【输入格式】
第一行是两个正整数N和K（1≤N≤100000，1≤K≤200000)，N是原木的数目，K是需要得到的小段的数目。接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度L。
【输出格式】
输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出“0”。
【输入样例】 【输出样例】
3 7 23
50
60
70
该题程序：
#include<bits/stdc++.h>
using namespace std;
int n,k,len[10000],le,ri,mid;
int check(int t)
{
int num=0;
for(int i=0;i<n;i++)
num+=len[i]/t;
return num;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
scanf("%d",&len[i]);
le=0;
ri=10001;
while(le+1<ri)
{
mid=(le+ri)/2;
if(check(mid)>=k)
le=mid;
else
ri=mid;
}
cout<<le;
return 0;
}
```