algorithm - 构建一个数组大小限制为 5 的队列 - 但队列可以增长

Question

问题:使用 enqueue 和 dequeue 方法构建一个队列类。但是，您使用的语言有一个错误，不允许数组存储超过 5 个元素，您将如何构建它？

我写了下面的代码但被拒绝了，想知道问题是什么以及我被拒绝的原因，仅供引用 - 这是在技术电话屏幕上。

static LinkedList<Queue<Integer>> list = new LinkedList<Queue<Integer>>();

public static void enQueue(Integer element){

    //iterating the linkedlist....
    while(true){ //todo
        Queue<Integer> curr;
        if(list.size() > 0)
            curr = list.getLast();
        else{
            curr = new LinkedList<Integer>();
            list.add(curr);
        }
        if(curr.size() < 5){
            curr.add(element);
            System.out.println("enqueued:" + element);
            break;
        } else{
            Queue<Integer> newQueue = new LinkedList<Integer>();
            newQueue.add(element);
            list.add(newQueue); //adding the new Queue of size(5) to the list
            break;
        }
    }
}

public static Integer deQueue(){
    LinkedList<Queue<Integer>> node = list;
    if(!isEmpty()){
        Integer retValue = 0;
        while(list.size() > 0){
            Queue<Integer> q = node.getFirst();
            if(!q.isEmpty()){
                retValue =  q.poll();
                break;
            }else{
                node.removeFirst();
            }
        }
        return retValue;
    }else{
        System.out.println("No such element found");
        return -1; //throw new NoSuchElementException("no element found");
    }
}

public static boolean isEmpty(){
    return list.size() == 0;
}

Answer 1

你被拒绝了，因为:

• 您假设了一个预先存在的 Queue 类，这是您应该实现的。
• 您使用了一个 LinkedList，它已经实现了一个类似队列的接口(interface)，而不是实际实现一个队列。
• 您对 LinkedList 的使用很糟糕——根本没有理由使用任何类型的循环。你可以让你的 enQueue 和 deQueue 调用 LinkedList.add() LinkedList.pollFirst()

面试官真的希望你实际实现一个队列。数组限制是强制你使用链接实现，面试官希望看到你正确维护链接。