25 7.8上午 栈 队列 二叉搜索树
栈：
#include<bits/stdc++.h>
#define int long long
/*
STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有：
元素访问
st.top() 返回栈顶
修改
st.push() 插入传入的参数到栈顶
st.pop() 弹出栈顶
容量
st.empty() 返回是否为空
st.size() 返回元素数量
此外，std::stack 还提供了一些运算符。较为常用的是使用赋值运算符 = 为 stack 赋值
*/
using namespace std;
stack<int>s;
const int N=1e5+50;
int st[N],top;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
s.push(1);//入栈
st[++top]=1;//模拟入栈
int x=s.top();//栈顶
s.pop();//弹出
x=st[top--];//模拟出栈
return 0;
}推荐题目：UVA12096（洛谷）
UVA12096（vjudge）
UVA12096代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
stack<int>s;
map<set<int>,int>IDset;
vector<set<int> >sets;
int ID(set<int> x){
if(IDset[x]){
return IDset[x];
}
sets.push_back(x);
return IDset[x]=sets.size()-1;
}
set<int>set_union(set<int>x1,set<int>x2){
set<int>::iterator x=x2.begin();
while(x!=x2.end()){
x1.insert(*x);
++x;
}
return x1;
}
set<int>set_inter(set<int>x1,set<int>x2){
set<int>x;
x.clear();
for(auto i:x1){
if(x2.find(i)!=x2.end()){
x.insert(i);
}
}
// set<int>::iterator i = x2.begin();
// while(i != x2.end())
// {
// if(x2.find(*i) != x2.end())
// x.insert(*i);
// ++ i;
// }
return x;
}
void clear(){
while(!s.empty()){
s.pop();
}
IDset.clear();
sets.clear();
}
void solve(){
clear();
int n;
cin>>n;
while(n--){
string op;
cin>>op;
if(op[0]=='P'){
s.push(ID(set<int>()));
}
else if(op[0]=='D'){
s.push(s.top());
}
else{
set<int>x1=sets[s.top()];
s.pop();
set<int>x2=sets[s.top()];
s.pop();
set<int>x;
if(op[0]=='U'){
x=set_union(x1,x2);
}
if(op[0]=='I'){
x=set_inter(x1,x2);
}
if(op[0]=='A'){
x=x2;
x.insert(ID(x1));
}
s.push(ID(x));
}
cout<<sets[s.top()].size()<<"\n";
}
cout<<"***\n";
}
int T;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
} 队列：
#include<bits/stdc++.h>
#define int long long
/*
队列操作对应的代码如下：
插入元素：q[++qr] = x;
删除元素：ql++;
访问队首：q[ql]
访问队尾：q[qr]
清空队列：ql = 1; qr = 0;
STL 中的 queue 容器提供了一众成员函数以供调用。其中较为常用的有：
元素访问
q.front() 返回队首元素
q.back() 返回队尾元素
修改
q.push() 在队尾插入元素
q.pop() 弹出队首元素
容量
q.empty() 队列是否为空
q.size() 返回队列中元素的数量
此外，queue 还提供了一些运算符。较为常用的是使用赋值运算符 = 为 queue 赋值
*/
/*
循环队列
使用数组模拟队列会导致一个问题：随着时间的推移，整个队列会向数组的尾部移动，一旦到达数组的最末端，即使数组的前端还有空闲位置，再进行入队操作也会导致溢出（这种数组里实际有空闲位置而发生了上溢的现象被称为「假溢出」）。
解决假溢出的办法是采用循环的方式来组织存放队列元素的数组，即将数组下标为 0 的位置看做是最后一个位置的后继。（数组下标为 x 的元素，它的后继为 (x + 1) % SIZE）。这样就形成了循环队列。
*/
using namespace std;
queue<int>q;
int q2[N],st,ed;
const int N=1e5+50;
void test(){
st=1;
ed=0;
q.push(1);
q2[++ed]=1;
int x=q.front();
int y=q2[st];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
test();
return 0;
} 推荐题目：UVA540（洛谷）
UVA540（vjudge）
UVA540代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,te[1000111],w;
string s;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
while(1){
w++;
int fl=0;
queue<int>q;
queue<int>p[1010];
cin>>n;
if(n==0){
return 0;
}
for(int i=1;i<=n;i++){
int num;
cin>>num;
for(int j=1;j<=num;j++){
int k;
cin>>k;
te[k]=i;
}
}
while(1){
cin>>s;
int num;
if(s[0]=='E'){
cin>>num;
if(p[te[num]].empty()){
q.push(te[num]);
p[te[num]].push(num);
}
else{
p[te[num]].push(num);
}
}
if(s[0]=='D'){
if(fl==0){
cout<<"Scenario #"<<w<<"\n";
fl=1;
}
while(p[q.front()].empty()){
q.pop();
}
cout<<p[q.front()].front()<<"\n";
p[q.front()].pop();
}
if(s[0]=='S'){
cout<<"\n";
break;
}
}
}
return 0;
}二叉搜索树：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+50;
int n,rt;
int a[N];
struct Node{
int data,ls,rs;
}t[N];
/*
二叉搜索树是一种二叉树的树形数据结构，其定义如下：
空树是二叉搜索树。
若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
二叉搜索树的左右子树均为二叉搜索树。
*/
/*
在以 root 为根节点的二叉搜索树中搜索一个值为 value 的节点。
分类讨论如下：
若 root 为空，返回 false。
若 root 的权值等于 value，返回 true。
若 root 的权值大于 value，在 root 的左子树中继续搜索。
若 root 的权值小于 value，在 root 的右子树中继续搜索。
*/
void build(int x,int l,int r){
if(l==r){
t[x].data=a[l];
return;
}
int mid=(l+r)>>1;
t[x].data=a[mid];
if(l<mid){
build(x*2,l,mid-1);
}
if(r>mid){
build(x*2+1,mid+1,r);
}
}
int find(int x,int y){
if(t[x].data==0)return -1;
if(t[x].data==y)return x;
if(t[x].data>y)return find(x*2,y);
if(t[x].data<y)return find(x*2+1,y);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
rt=1;
build(1,1,n);
int m;
cin>>m;
while(m--){
int x;
cin>>x;
cout<<find(rt,x)<<'\n';
}
return 0;
}推荐题目：B4016
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
vector<int>e[N];
int fa[N],deep[N];
int mx;
void dfs(int x){
if(deep[x]>deep[mx])mx=x;
for(auto i:e[x]){
if(i!=fa[x]){
fa[i]=x;
deep[i]=deep[x]+1;
dfs(i);
}
}
}
int n;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1);
memset(deep,0,sizeof(deep));
memset(fa,0,sizeof(fa));
dfs(mx);
cout<<deep[mx];
return 0;
} 推荐题目：P1305
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
char s[10];
map<char,int>mp;
int n,sz;
struct node{
char c;
int ls,rs;
}t[30];
void print(int x){
cout<<t[x].c;
if(t[x].ls)print(t[x].ls);
if(t[x].rs)print(t[x].rs);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
if(!mp[s[0]]){
mp[s[0]]=++sz;
t[sz].c=s[0];
}
if(!mp[s[1]]&&s[1]!='*'){
mp[s[1]]=++sz;
t[sz].c=s[1];
}
if(!mp[s[2]]&&s[2]!='*'){
mp[s[2]]=++sz;
t[sz].c=s[2];
}
if(s[1]!='*')t[mp[s[0]]].ls=mp[s[1]];
if(s[2]!='*')t[mp[s[0]]].rs=mp[s[2]];
}
print(1);
return 0;
}