算法常用模板

系统管理员 2023-10-04 08:26 33阅读 0赞

### 第二部分：数据结构 ###

**一.数组模拟链表，栈，队列，单调栈，单调队列**

**1.链表**

*（一）单链表*

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
    int head, e[N], ne[N], idx;
    //初始化，第一个结点从0开始
    void init()
    {
        
         head=-1;
         idx=0;
    }
    //在链表头插入一个数x
    void insert_head(int x)
    {
        
         e[idx]=x;
         ne[idx]=head;
         head=idx++;
    }
    //在链表第k个插入的数后面插入一个数x
    void insert_k(int k,int x)
    {
        
         e[idx]=x;
         ne[idx]=ne[k];
         ne[k]=idx++;
    }
    //将头结点删除，需要保证头结点存在
    void remove_head()
    {
        
         head=ne[head];
    }
    //删除第k个插入的数后面的数
    void remove_k(int k)
    {
        
         ne[k]=ne[ne[k]];
    }

*（二)双链表*

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
    int e[N], l[N], r[N], idx;
    //初始化
    void init()
    {
        
         r[0]=1,l[1]=0;
         idx=2;
    }
    //在节点a的右边插入一个数x
    void insert(int a,int x)
    {
        
         e[idx]=x;
         l[idx]=a,r[idx]=r[a];
         l[r[a]]=idx,r[a]=idx++;
    }
    //删除节点a
    void remove(int a)
    {
        
         l[r[a]]=l[a];
         r[l[a]]=r[a];
    }

**2.栈**

// tt表示栈顶
    int stk[N], tt = 0;
    
    // 向栈顶插入一个数
    stk[ ++ tt] = x;
    
    // 从栈顶弹出一个数
    tt -- ;
    
    // 栈顶的值
    stk[tt];
    
    // 判断栈是否为空
    if (tt > 0)
    {
        
    
    }

**3.队列**

1.  普通队列：

// hh 表示队头，tt表示队尾
    int q[N], hh = 0, tt = -1;
    
    // 向队尾插入一个数
    q[ ++ tt] = x;
    
    // 从队头弹出一个数
    hh ++ ;
    
    // 队头的值
    q[hh];
    
    // 判断队列是否为空
    if (hh <= tt)
    {
        
    
    }

1.  循环队列：

// hh 表示队头，tt表示队尾的后一个位置
    int q[N], hh = 0, tt = 0;
    
    // 向队尾插入一个数
    q[tt ++ ] = x;
    if (tt == N) tt = 0;
    
    // 从队头弹出一个数
    hh ++ ;
    if (hh == N) hh = 0;
    
    // 队头的值
    q[hh];
    
    // 判断队列是否为空
    if (hh != tt)
    {
        
    
    }

**4.单调栈**

//常见模型：找出每个数左边离它最近的比它大/小的数
    int tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        
        while (tt && check(stk[tt], i)) tt -- ;
        stk[ ++ tt] = i;
    }

**5.单调队列**

//常见模型：找出滑动窗口中的最大值/最小值
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        
        while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
        while (hh <= tt && check(q[tt], i)) tt -- ;
        q[ ++ tt] = i;
    }

转载自：[AcWing][]

[AcWing]: https://www.acwing.com/blog/content/404/