Java-使用dualarraydeque实现阻止列表会导致错误

Question

所以我试图实现一个实现List接口的BlockedList类。此类的构造函数基本上采用整数块大小b，并且实现应具有以下性能特征：

a）get（i）和set（i，x）应该在每次操作的O（1）时间中运行

b）add（i，x）和remove（i）应该以O（b + min {i，n-i} / b）每次操作的摊销时间运行

我想我大部分时间都正确地完成了工作，但是问题是，每当我尝试编译代码时，我都会收到很多错误，例如：

找不到符号f =新的Factory（t）;

类BlockedList中的构造方法BlockedList不能应用于给定类型；列表q =新的BlockedList（Integer.class）;

我对为什么会收到这些错误感到困惑，希望能帮助您解决此问题。

BlockedList.java：

package task2;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class BlockedList<T> extends AbstractList<T> {
    /**
     * The class of objects stored in this structure
     */
    Factory<T> f;

    /**
     * the front "half" of the deque 
     */
    List<T> front;

    /** 
     * the back "half" of the deque
     */
    List<T> back;

    int b;
    /**
     * Create a new empty List data structure.
     * 
     * Subclasses should override this if they want to use
     * different structures for front and back. 
     * @return
     */
    List<T> newStack() {
        return new ArrayList<T>();
    }

    /**
     * Constructor
     * @param t0 the class of the objects stored in this list
     */
    public BlockedList(Class<T> t, int b) {
        f = new Factory<T>(t);
        front = newStack();
        back = newStack();
        this.b = b;
    }

    public T get(int i) {
        if (i < front.size()) {
            return front.get(front.size()-i-1);
        } else {
            return back.get(i-front.size());
        }
    }

    public T set(int i, T x) {
        if (i < front.size()) {
            return front.set(front.size()-i-1, x);

        } else {
            return back.set(i-front.size(), x);
        }
    }

    public void add(int i, T x) {
        if (i < front.size()) { 
            front.add(front.size()-i, x);
        } else {
            back.add(i-front.size(), x);
        }
        balance();
    }

    /**
     * Rebalance the elements between front and back
     * if necessary
     */
    protected void balance() {
        int n = size();
        if (3*front.size() < back.size()) {
            int s = n/2 - front.size();
            List<T> l1 = newStack();
            List<T> l2 = newStack();
            l1.addAll(back.subList(0,s));
            Collections.reverse(l1);
            l1.addAll(front);
            l2.addAll(back.subList(s, back.size()));
            front = l1;
            back = l2;
        } else if (3*back.size() < front.size()) {
            int s = front.size() - n/2;
            List<T> l1 = newStack();
            List<T> l2 = newStack();
            l1.addAll(front.subList(s, front.size()));
            l2.addAll(front.subList(0, s));
            Collections.reverse(l2);
            l2.addAll(back);
            front = l1;
            back = l2;
        }
    }

    public T remove(int i) {
        T x;
        if (i < front.size()) {
            x = front.remove(front.size()-i-1);
        } else {
            x = back.remove(i-front.size());
        }
        balance();
        return x;
    }

    public int size() {
        return front.size() + back.size();      
    }

    public void clear() {
        front.clear();
        back.clear();
    }

    public static void main(String args[]) {
        List<Integer> l = new BlockedList<Integer>(Integer.class);
        for (int i = 0; i < 20; i++) {
            l.add(new Integer(i));
        }
        System.out.println(l);
        for (int i = -1; i > -20; i--) {
            l.add(0,new Integer(i));
        }
        System.out.println(l);

        Integer n = 1000;
        Integer x = 20;
        List<Integer> q = new BlockedList<Integer>(Integer.class);
        for (int i = 0; i < n; i++) {
            q.add(i);
        }
        while (true) {
            q.add(x);
            q.remove(0);
        }
    }
}

Answer 1

您使用的是Java（）的通用性差。

您不得要求构造函数中的对象具有该类，因为所收集对象的类为T。我不知道在何处创建对象工厂，但这不是必需的。第二个错误是因为您放置了一个参数而构造函数需要两个参数。

希望对您有帮助，对不起我的英语不好。