创建具有高效随机访问的三端队列

Question

我的任务是解决一个关于创建具有有效随机访问的三端队列的问题，如本文所述:https://open.kattis.com/problems/teque。我创建了一个基于使用2个非常大的数组的程序，一个包含到目前为止所有存储的整数的前半部分，另一个包含后半部分，两者都是相同的大小，或者前半部分最多比每次插入操作后的后半部多包含1个元素。这应该允许所有插入和检索操作的时间复杂度为0(1)，但是代码只是不断超出给定的时间限制。谁能告诉我我的代码有什么问题?

import java.util.*;
import java.io.*;
public class Teque3 {
static int[] front = new int[1_000_000];
static int[] back = new int[1_000_000];
static int frontHead = 499_999;
static int backHead = 499_999;
static int frontSize = 0;
static int backSize = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
String[] line = br.readLine().split(" ");
if (line[0].equals("get")) {
int index = Integer.parseInt(line[1]);
if (index >= frontSize) System.out.println(back[backHead + index - frontSize]);
else System.out.println(front[frontHead + index]);
continue;
}
if (frontSize == backSize) {
if (line[0].equals("push_front")) {
frontHead--;
front[frontHead] = Integer.parseInt(line[1]);
frontSize++;
} else if (line[0].equals("push_back")) {
back[backHead + backSize] = Integer.parseInt(line[1]);
front[frontHead + frontSize] = back[backHead];
frontSize++;
backHead++;
} else if (line[0].equals("push_middle")) {
front[frontHead + frontSize] = Integer.parseInt(line[1]);
frontSize++;
}
} else {
if (line[0].equals("push_front")) {
frontHead--;
front[frontHead] = Integer.parseInt(line[1]);
backHead--;
back[backHead] = front[frontHead + frontSize];
backSize++;
} else if (line[0].equals("push_back")) {
back[backHead + backSize] = Integer.parseInt(line[1]);
backSize++;
} else if (line[0].equals("push_middle")) {
backHead--;
back[backHead] = Integer.parseInt(line[1]);
backSize++;
}
}
}
}
}

Answer 1

1. 您可以尝试最小化IO-Operations:收集您的程序输出。与其写System.out.println，不如创建一个新的StringBuilder来收集所有内容。最后一次写完。

   static StringBuilder result = new StringBuilder();
   ...
   private static void result(int value) {
   result.append(value).append("n");
   }
   ...
   if (index >= frontSize) result(back[backHead + index - frontSize]);
   else result(front[frontHead + index]);
   ...
   System.out.println(result);
   

2. 从解析和进程中解耦读取:创建一个线程用于读取操作。但是Queue中的操作。为该进程启动另一个线程。