参考链接：https://blog.csdn.net/SSLGZ_yyc/article/details/81700623
对顶栈的思想：
建立两个栈，栈A存储从序列开头到当前光标的位置的一段序列，栈B存储从光标到结尾的序列。这两个栈一共存储了整个序列。
java版本代码
import java.util.Scanner;
import java.util.Stack; public class Main {
public static void main(String[] args) {
int f[]=new int[200000];
f[0]=-999999999;
int sum=0;
Scanner in = new Scanner(System.in);
int n=in.nextInt();
while(in.hasNext())
{
Stack<Integer> a=new Stack<Integer>();
Stack<Integer> b=new Stack<Integer>(); while((n--)!=0) {
String s=in.next();
if (s.equals("I")) {
int x=in.nextInt();
a.push(x);
sum=sum+x;
int l=a.size();
f[l]=Math.max(sum, f[l-1]);
}else if (s.equals("D")&&a.size()>0) {
int x=a.pop();
sum=sum-x;
}else if (s.equals("L")&&a.size()>0) {
int x=a.pop();
sum=sum-x;
b.push(x);
}else if (s.equals("R")&&b.size()>0) {
int x=b.pop();
a.push(x);
sum+=x;
int l=a.size();
f[l]=Math.max(sum,f[l-1]);
}else if (s.equals("Q")) {
int x=in.nextInt();
System.out.println(f[x]);
}
}
}
}
}
c++版本代码：
#include<iostream>
#include<stack>
#include<stdio.h>
using namespace std;
int f[2000000]; int main()
{
char ch,zfc[200];
int n;
while (scanf("%d",&n)!=EOF)
{
stack <int> a;
stack <int> b;
int sum=0,x;
f[0]=-999999999;
while (n--)
{
scanf("%s",zfc);
ch=zfc[0];
if (ch=='I')
{
scanf("%d",&x);
a.push(x);
sum+=x;
int l=a.size();
f[l]=max(sum,f[l-1]);
} else
if (ch=='D'&&a.size()>=1)
{
x=a.top();
a.pop();
sum-=x;
} else
if (ch=='L'&&a.size()>=1)
{
x=a.top();
a.pop();
sum-=x;
b.push(x);
} else
if (ch=='R'&&b.size()>=1)
{
x=b.top();
b.pop();
a.push(x);
sum+=x;
int l=a.size();
f[l]=max(sum,f[l-1]);
} else
if (ch=='Q')
{
scanf("%d",&x);
printf("%d\n",f[x]);
}
}
}
return 0;
}