首页 > 其他分享 >数组模拟链表 模拟栈和队列 单调栈和队列(9/7 9/8)

数组模拟链表 模拟栈和队列 单调栈和队列(9/7 9/8)

时间:2023-09-08 21:23:44浏览次数:49  
标签:idx 队列 tt cin else 链表 int hh 模拟

单链表

数组模拟链表可以加快速度,更利于优化算法

#include<iostream>
using namespace std;
const int N = 100010;
int e[N], ne[N], head, idx;

void init()
{
    head = -1;
    idx = 0;
}

void add_head(int x)
{
    e[idx] = x; ne[idx] = head; head = idx++;
}

void insert(int k, int x)
{
    e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++;
}

void delete_link(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
     int n; cin >> n;
    init();
    while (n--)
    {
        char c;int k,x;
      cin>>c;
        if (c == 'H')
        {
            scanf("%d",&x);
            add_head(x);
        }
        else if (c == 'I')
        {
            scanf("%d%d",&k,&x);
            insert(k-1, x);
        }
        else {
            
            scanf("%d",&k);
            if(k==0) head=ne[head];//注意这个特殊情况
            else{
            delete_link(k-1);}
        }
    }

    for (int i = head; i != -1; i = ne[i])
        printf("%d ",e[i]);
    return 0;
}

双链表

//注意事项:::切记不要把下一位看成k+1,因为这是不对的空间是不连续的


#include<iostream>
using namespace std;
const int N = 100010;
int e[N], l[N], r[N], idx;

void insert(int k,int x)
{
    e[idx] = x; 
    l[idx] = l[r[k]], r[idx] = r[k];
    l[r[k]] = idx; r[k] = idx++;
}

void del(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main()
{
    r[0] = 1; l[1] = 0; idx = 2;//用0表示开头,1表示结尾,不存实际值
    int n; cin >> n;
    while (n--)
    {
        int k, x; string c;
        cin >> c;
        if (c == "R")
        {
            cin >> x;
            insert(l[1], x);//结尾往左边插
        }
        else if (c == "L")
        {
            cin >> x;
            insert(0, x);//从0开始查
        }
        else if (c == "D")
        {
            cin >> k;
            del(k + 1);//查的是下标
        }
        else if (c == "IL")
        {
            cin >> k >> x;
            insert(l[k+1], x);
        }
        else {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }
    for (int i = r[0]; i != 1; i = r[i])
    {
        cout << e[i] << " ";
    }
    return 0;
}

模拟栈

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int stk[N], tt;

int main()
{
    cin >> m;
    while (m -- )
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            stk[ ++ tt] = x;
        }
        else if (op == "pop") tt -- ;
        else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;//简化代码
        else cout << stk[tt] << endl;
    }

    return 0;
}

 

模拟队列

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int q[N], hh, tt = -1;

int main()
{
    cin >> m;

    while (m -- )
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            q[ ++ tt] = x;
        }
        else if (op == "pop") hh ++ ;
        else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;
        else cout << q[hh] << endl;
    }

    return 0;
}

 

单调栈

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt -- ;//判断栈顶元素如果大于等于x,就弹出
        if (!tt) printf("-1 ");//如果空就输出-1
        else printf("%d ", stk[tt]);//没有就输出元素
        stk[ ++ tt] = x;//把新的加入
    }

    return 0;
}

//自写代码较为复杂,但精细
#include<iostream> using namespace std; const int N = 100010; int a[N]; int main() { int hh = -1; int n; cin >> n; while (n--) { int x; scanf("%d", &x); if (hh == -1) { printf("-1 "); a[++hh] = x; } else { if (a[hh] < x) { printf("%d ", a[hh]); a[++hh] = x; } else { while (a[hh] >= x && hh > -1) hh--; if (a[hh] < x&&hh!=-1)cout << a[hh] << " ";//一定加上hh!=-1的条件 if(hh==-1)printf("-1 "); a[++hh] = x; } } } return 0; }
 

 

单调队列

#include<iostream>
using namespace std;
const int N = 1000010;
int a[N],q[N]; int hh=0, tt=-1;
int main()
{
    int n, k; cin >> n >> k;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && i - k + 1 > q[hh])hh++;//可以等于,相当于1个元素
        while (a[i] < a[q[tt]] && hh <= tt)tt--;
        q[++tt] = i;
        if (i-k+1>=0)cout << a[q[hh]] << " ";
    }
    cout<<endl;
    hh=0, tt=-1;
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && i - k + 1 > q[hh])hh++;
        while (a[i] >= a[q[tt]] && hh <= tt)tt--;
        q[++tt] = i;
        if (i-k+1>=0)cout << a[q[hh]] << " ";
    }
    return 0;
}

 

标签:idx,队列,tt,cin,else,链表,int,hh,模拟
From: https://www.cnblogs.com/daimazhishen/p/17688559.html

相关文章

  • 记PE文件结构实验,模拟文件内存加载过程。
    记录文件结构试验前言:使用的模拟程序是notepad.exe,主要记录其中的思路和遇到其中的困难。实验目的:模拟内存加载PE文件的过程,将每个区段模拟加载到内存之中。根据文件结构中头表中的信息,读取并sekk指针到Segment头。然后循环遍历Segment头将内容加载到VirtualAddress中,主要目的......
  • 代码随想录刷题记录——栈与队列篇
    栈与队列理论基础 栈stack:先进后厨队列queue:先进先出STL(C++标准库)STL栈和队列属于容器适配器(containeradapter)优先队列priority_queue:默认大根堆,如果是pair<a,b>,默认比较a大小如果需要比较b大小,且小根堆,可以如下实现232.用栈实现队列题目链接 pop操作时,当......
  • 剑指 Offer 52. 两个链表的第一个公共节点
    题目链接:剑指Offer52.两个链表的第一个公共节点题目描述:输入两个链表,找出它们的第一个公共节点。解法思路:代码:/***Definitionforsingly-linkedlist.*typeListNodestruct{*Valint*Next*ListNode*}*/funcgetIntersectionNode(headA,h......
  • DHCP饿死攻击及防御(基于ENSP模拟器、Kali攻击机实现)
    相关参数:·Kali攻击机一台·ENSP模拟器 拓扑图:   实验说明:·通过配置DHCP_Server,使得192.168.150.0/24子网内的终端能够自动获取IP地址及DNS·通过配置SW交换机,开启DHCPSnooping功能,用于保证DHCP客户端从合法的DHCP服务器获取IP地址·Kali攻......
  • python模拟用户登录
    python模拟用户登录目录python模拟用户登录一、授权认证二、Cookie认证一、授权认证1、HTTP基础认证importrequestsfromrequests.authimportHTTPBasicAuthurl="https://xxx.xxx.xxx/"username="admin"password="admin"#HTTP基础认证response=requests.ge......
  • 线程安全的队列:使用Monitor模式和C++11多线程库
    线程安全的队列:使用Monitor模式和C++11多线程库引言在多线程编程中,数据共享是一个关键的问题。如果多个线程需要访问同一个数据结构,不正确的管理会导致数据不一致甚至程序崩溃。本文将介绍如何使用C++11的多线程库和Monitor模式来实现一个线程安全的队列。Monitor模式Monitor模式......
  • 【校招VIP】测试算法考点之链表
    考点介绍:链表是一种逻辑简单的、实用的数据结构,几乎被所有程序设计语言支持。单链表的操作算法是笔试面试中较为常见的题目。相关题目及解析内容可点击文章末尾链接查看!一、考点试题1.一个长度为n的单向链表,用O(1)空间复杂度来实现倒转输出,使用最低时间复杂度解答:思路:读题(......
  • 深入理解消息队列与事件驱动架构
    什么是消息队列?消息队列是一种通信模式,用于将消息从一个发送者传递到一个或多个接收者。它们允许应用程序之间以异步、松耦合的方式进行通信。消息队列通常包括消息代理(如RabbitMQ、ApacheKafka)和消息消费者。为什么使用消息队列?使用消息队列的好处包括:解耦应用程序:消息队列允许......
  • wzOI 2023.8.24 模拟赛(附树的直径和三分法)
    2023-08-2815:53:53$$A$$典型错误一知半解看样例型:如果该队某个数组的值比最大值大就算入答案。上第一次厕所前我的思路:开局\(30\)分钟。显然,我并不需要有一个数值最大才能赢,我只需要其中一个数值比其中一个数值比其中一个数值最大的那个要大的队要大即有可能获胜......
  • 暑假集训 Day17 模拟赛题解
    2023-08-0318:18:03前言好家伙,很少完整订正一场比赛,可能是因为这个比赛相对来说确实不难吧(至少正解不难)。总结与反思这场比赛其实没有我想象的那么难,只是觉得题目可能不简单,就没有往简单的思路想,反而是被之前讲过的题疑惑,以为要用到一些很奇特的算法,结果打完以后看了题解再结......