集训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;
}