专栏文章

25 7.8上午 栈 队列 二叉搜索树

bbokaro_kyoku_mania
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioyf83h
此快照首次捕获于
2025/12/03 03:11
3 个月前
此快照最后确认于
2025/12/03 03:11
3 个月前
查看原文
栈：
CPP
#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代码：
CPP
#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;
}
队列：
CPP
#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代码：
CPP
#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;
}
二叉搜索树：
CPP
#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
代码：
CPP
#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
代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...