集训Day1上午数据结构

1. 队列

定义方法：

queue</*类型*/> /*定义名*/;

用法：

queue<int> q;
q.push(/*加入的元素*/);//插入
q.pop();//删除队头
q.front();//获取队列头元素
q.size()//获取队列长度

当然还是有手写queue：

struct queue{
	int q[10000005];
	int h=1,tail=0;
	void push(int x){
		tail++;
		q[tail]=x;
	}
	void pop(){
		h++;
	}
	int head(){
		return q[h];
	}
	int size(){
		return tail-h+1;
	}
	bool empty(){
		return h>tail;
	}
}q;
signed main(){
	q.push(233);
	q.push(2233);
	q.pop();//无返回值
	int x = q.front();
	cout << q.size() << '\n';
} 

2. 栈

定义方法:

stack</*类型*/>s;//定义栈 

用法：

s.push();//压入元素 
s.pop();//弹出元素 
s.top();//查询栈顶元素 
s.size();//查询栈内元素个数 
s.empty();//查询栈是否为空

手写栈：

struct stack{
	int s[10000005],topp=0;
	void push(int x){
		topp++;
		s[topp]=x;
		return;
	}
	void pop(){
		topp--;
		return ;
	}
	int top(){
		return s[topp];
	}
	int size(){
		return topp;
	}
	bool empty(){
		return topp==0;
	}
}q;

signed main(){
	q.push(233);
	q.push(2233);
	q.pop();
	int x = q.top();
	cout << q.size() << '\n';
} 

3. 双端队列

定义:

deque<int>d;

用法：

.push_back();
.push_front();
.pop_...
.back();
.front();
.clear();//清空
.begin()//首地址
.erase()//删除
.end()//队尾地址
deque<int>::iterator it;//定义指针

双端队列可以用用双指针模拟，此处就不展示了.

单调队列

deque<int> q;

int a[100000];

void push(int i){
    while(q.size()>0&&a[q.back()]>=a[i])q.pop();
    q.push(i)
}

4. 堆

定义：

#incude<queue>
priority_queue<int>p;//从大到小
priority_queue<int,vector<int>,greater<int> >//从小到大

~温馨提示：从小到大可以通过取负来进行~

正难则反！

注意如果要用

struct

类型的

priority_queue

需

operator <

（重载小于号）.
如：

#include<queue>
//#include<bits/stdc++.h>

using namespace std;

priority_queue<int> q;
//大根堆 
//小根堆最简单的方法：取负号 

struct rec
{
	int a,b;
};
//如果要把结构体 放入 stl比大小 只能重载小于号 
bool operator<(const rec &x,const rec &y)
{
	return x.a + x.b > y.a + y.b;
}

priority_queue<rec> qq;//取出a+b最小的结构体 

signed main(){
	q.push(233);
	q.push(2233);//向堆里面加入一个元素
	q.pop();//从堆中删除一个元素 删除是堆中最大的元素 2233 void类型没有返回值
	int x = q.top();//获取堆中最大元素 233
	cout << q.size() << endl;//获取堆剩余的元素个数 1 
}

5. trie树

struct node{
	int nxt[2];//nxt[0] nxt[1]代表从当前点走0和1会到哪里走到0代表该点不存在 
	node()
	{
		nxt[0]=nxt[1]=0;
	}
}z[23333];
void insert(int x)
{
	for(int i=30;i>=0;i--)
	{
		int y=(x>>i)&1;//取出二进制的第i位
		if(z[p].nxt[y]==0){
			cnt++;
			z[p].nxt[y]=cnt;
		} 
		p-z[p].nxt[y];
	}
}
int query(int x)
{
	int p=root,ans=0;
	for(int i=30;i>=0;i--)
	{
		int y=(x>>i)&1;
		if(z[p].nxt[y^1]!=0)ans=ans|(1<<i),p=z[p].nxt[y^1];
		else p=z[p].nxt[y];
	}
	return ans;
}