使用固定大小的数组实现队列

Question

我遇到了面试问题，我正在研究它：

使用enqueue和dequeue方法构建队列类。队列可以存储无限数量的元素，但您只能使用最多可存储5个元素的数组。

这是我能想到的。这是在面试中做到这一点的正确方法，还是我们应该在面试中采用更好的方式？

class Solution {  
  private final List<List<Integer>> array;

  public Solution() {
    this.array = new ArrayList<>();
  }

  public void enqueue(int value) {
    if(array.isEmpty()) {
      List<Integer> arr = new ArrayList<>();
      arr.add(value);
      array.add(arr);
      return;
    }
    if(array.get(array.size() - 1).size() != 5) {
      array.get(array.size() - 1).add(value);   
      return;
    }
    List<Integer> arr = new ArrayList<>();
    arr.add(value);
    array.add(arr);
    return;
  }

  public int dequeue() {
    if(array.isEmpty()) {
      return -1; 
    }
    for(List<Integer> l : array) {
      for(int i=0; i<l.size(); i++) {
        return l.remove(i); 
      }
    }
    return -1;
  }
}

Answer 1

你的答案使用ArrayList而不是真正的数组，更糟糕的是，使用无限制的arraylist来放置那些数组。我认为采访者希望你实现一个单元链接的5元素数组列表：

/**
 * A singly-linked list node with an array; supports popping its 1st elements, 
 * and adding elements at the end, possibly by creating a new node
 */
public class ListNode {
    final int MAX = 5;
    private int contents[] = new int[MAX];
    private int size = 0; // valid elements

    private ListNode next = null;
    private ListNode(ListNode next) {
        this.next = next;
    }

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

    public ListNode addLast(int value) {
        ListNode next = this;
        if (size == MAX) {
            next = new ListNode(this);
        }
        next.contents[next.size ++] = value;
        return next;
    }

    public int removeFirst() {
        if (size == 0) {
            throw new NoSuchElementException("empty queue");
        }
        int value = contents[0];
        size --;
        for (int i=1; i<size; i++) contents[i-1] = contents[i];
        return value;
    }
}

/**
 * A simple queue on top of nodes that keep arrays of elements
 */
public class ListArrayQueue {
    ListNode first = new ListNode();
    ListNode last = first;
    public void enqueue(int value) {
        last = last.addLast(value);
    }
    public int dequeue() {
        if (first.isEmpty() && first != last) {
            first = first.next;
        }
        return first.removeFirst();
    }
}

性能方面，这可以改进：你可以避免在每个size中保持ListNode，因为只有第一个和最后一个节点可以是非满的。你也可以避免removeFirst中的循环，但这需要用size和firstIndex替换lastIndex;可以再次移动到ListArrayQueue以节省每个节点的空间。

如果他们要求您使用5个元素的数组构建无限数组，那么您将不得不实现类似于b-tree的内容。在没有方便的参考资料的情况下，在面试中很难完成。

Answer 2

您可以使用1-D数组并使用环绕索引来实现队列，其限制是队列可以包含最多5个元素。

要检查空队列的条件，请维护一个计算队列中存在的元素数的变量。

Answer 3

Is this the right way to do it in the interview…? 提出未注释的代码永远是对的，更不用说在面试中了。 在交互式访谈中，您的任务是找出是否可以/应该使用无限数量的数组。如果没有，你必须协商一种方法来处理enqueue()到一个填充到容量的队列，除了dequeue()到空的。修复队列可以容纳的项目类型。同意enqueue and dequeue methods的参数。

任务是Build a queue class，Solution是一个名字的坏选择 - array的东西访问项目是没有更好的。 在提供数组的语言中，我会逐字地使用limited to using arrays - 如果使用更多内容，为什么不实现java.util.Queue？ 空队列处理完全是多余的：在enqueue()中，您可以使用 if (!array.isEmpty() && array.get(array.size() - 1).size() < 5);在dequeue()你可以放弃它。 实例化List<Integer>s，你知道一次不会有超过五个项目：告诉构造函数。 dequeue()在List<Integer>留下空的arrayss，导致当前嵌套的循环迫切需要评论。

（对于问题的第二部分，我是第二个Rajkamal Tomar。）

Answer 4

正如我在评论中提到的，你的解决方案并没有真正解决问题，因为5元素数组的外部数组可以有超过5个元素。

相反，您可以将队列实现为4个整数节点的链接列表，使用第5个元素作为对下一个数组的引用。但是没有理由假设元素是整数。事实证明这很简单。

public class SillyQueue<T> {
  private static final int MAX = 5;
  private Object [] head = new Object[MAX], tail = head;
  private int headPtr = 0, tailPtr = 0;

  void enqueue(T x) {
    if (tailPtr == MAX - 1) {
      Object [] a = new Object[MAX];
      tail[MAX - 1] = a;
      tail = a;
      tailPtr = 0;
    }
    tail[tailPtr++] = x;
  }

  T dequeue() {
    if (headPtr == MAX - 1) {
      head = (Object[]) head[MAX - 1];
      headPtr = 0;
    }
    return (T) head[headPtr++];
  }
}