目录

单链表

双链表

栈

队列

单调栈

单调队列

单链表

实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数；
2. 删除第 k 个插入的数后面的数；
3. 在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

1. H x，表示向链表头插入一个数 x。
2. D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
3. I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

1≤M≤100000
所有操作保证合法。

输入样例：

10H 9I 1 1D 1D 0H 6I 3 6I 4 5I 4 5I 3 4D 6

输出样例：

6 4 6 5

#includeusing namespace std;const int N = 100010;int head,e[N],ne[N],idx;//初始化void init(){    head = -1;    idx = 0;}//插入到头节点void add_to_head(int x){    e[idx] = x;    ne[idx] = head;    head = idx++;}//在第 k 个插入的数后插入一个数void add(int k,int x){    e[idx] = x;    ne[idx] = ne[k];    ne[k] = idx++;}//删除第k个数后面的数void remove(int k){    ne[k] = ne[ne[k]];}int main(){    int m;    cin>>m;    init();    while(m--){ int k,x; char op; cin>>op; if(op == 'H'){     cin>>x;     add_to_head(x); }else if(op == 'D'){ cin>>k;    if(!k) head = ne[head];    else remove(k-1);}else{    cin>>k>>x;    add(k-1,x);}    }    for(int i = head;i!=-1;i = ne[i])cout<<e[i]<<' ' ;    cout<<endl;    return 0;}

双链表

实现一个双链表，双链表初始为空，支持 55 种操作：

1. 在最左侧插入一个数；
2. 在最右侧插入一个数；
3. 将第 k 个插入的数删除；
4. 在第 k 个插入的数左侧插入一个数；
5. 在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

1. L x，表示在链表的最左端插入数 x。
2. R x，表示在链表的最右端插入数 x。
3. D k，表示将第 k 个插入的数删除。
4. IL k x，表示在第 k 个插入的数左侧插入一个数。
5. IR k x，表示在第 k 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

数据范围

1≤M≤100000
所有操作保证合法。

输入样例：

10R 7D 1L 3IL 2 10D 3IL 2 7L 8R 9IL 4 7IR 2 2

输出样例：

8 7 7 3 2 9

#includeusing namespace std;const int N = 100010;int m,e[N],l[N],r[N],idx;//插入void insert(int a,int x){    e[idx] = x;    l[idx] = a;    r[idx] = r[a];    l[r[a]] = idx;    r[a] = idx++;}//删除第k个节点void remove(int a){    l[r[a]] = l[a];    r[l[a]] = r[a];} int main(){    cin>>m; r[0] = 1,l[1] = 0;    idx = 2; while(m--){ string op; cin>>op; int k,x; if(op == "L"){     cin>>x;     insert(0,x);     }else if(op == "R"){     cin>>x;     insert(l[1],x);      }else if(op == "D"){     cin>>k;     remove(k+1);      }else if(op == "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]<<' ';    cout<<endl;    return 0;}

栈

实现一个栈，栈初始为空，支持四种操作：

1. push x – 向栈顶插入一个数 xx；
2. pop – 从栈顶弹出一个数；
3. empty – 判断栈是否为空；
4. query – 查询栈顶元素。

现在要对栈进行 M 个操作，其中的每个操作3 和操作 4 都要输出相应的结果。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围

1≤M≤100000
1≤x≤1e9
所有操作保证合法。

输入样例：

10push 5querypush 6popquerypopemptypush 4queryempty

输出样例：

55YES4NO

#includeusing namespace std;const int N = 100010;int stk[N],tt;int m;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;}

 

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

• 数据保证给定的表达式合法。
• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 231−1231−1。
• 题目中的整除是指向 00 取整，也就是说对于大于 00 的结果向下取整，例如 5/3=15/3=1，对于小于 00 的结果向上取整，例如 5/(1−4)=−15/(1−4)=−1。
• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 105105。

输入样例：

(2+2)*(1+1)

输出样例：

8

#include#include#include#includeusing namespace std;stacknum;stackop;unordered_map h{{'+',1},{'-',1},{'*',2},{'/',2}};void eval(){    int a = num.top();    num.pop();    int b = num.top();    num.pop();    char p = op.top();    op.pop();    int r = 0;    if(p == '+') r = b+a;    if(p == '-') r = b-a;    if(p == '*') r = b*a;    if(p == '/') r = b/a;    num.push(r);}int main(){    string s;    cin>>s;    for(int i = 0;i<s.size();i++){  if(isdigit(s[i])){     int x = 0,j = i;     while(j=h[s[i]]) eval(); op.push(s[i]); }     }    while(op.size() ) eval(); cout<<num.top()<<endl; return 0;}

#includeusing namespace std;const int N = 1e5+10;int q[N],hh,tt=-1;int m;int main(){    cin>>m;    string s;    int x;    while(m--){ cin>>s; if(s == "push"){     cin>>x;     q[++tt] = x; }else if(s == "pop"){     hh++; }else if(s == "empty"){     cout<<(hh<=tt?"NO":"YES")<<endl; }else{     cout<<q[hh]<<endl; }    }    return 0;}

#include 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 -- ;//如果栈顶元素大于当前待入栈元素，则出栈 if (!tt) printf("-1 ");//如果栈空，则没有比该元素小的值。 else printf("%d ", stk[tt]);//栈顶元素就是左侧第一个比它小的元素。 stk[ ++ tt] = x;    }    return 0;}

#include using namespace std;const int N = 1000010;int a[N], q[N];int main(){    int n, k;    scanf("%d%d", &n, &k);    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);    int hh = 0, tt = -1;    for (int i = 0; i < n; i ++ )    { if (hh  q[hh]) hh ++ ; while (hh = a[i]) tt -- ; q[ ++ tt] = i; if (i >= k - 1) printf("%d ", a[q[hh]]);    }    puts("");    hh = 0, tt = -1;    for (int i = 0; i < n; i ++ )    { if (hh  q[hh]) hh ++ ; while (hh <= tt && a[q[tt]] = k - 1) printf("%d ", a[q[hh]]);    }    puts("");    return 0;}