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

Question

我遇到了下面的面试问题，我正在研究它:

Build a queue class with the enqueue and dequeue methods. The queue can store an UNLIMITED number of elements but you are limited to using arrays that can store up to 5 elements max..

这是我能够想出的。这是在面试中这样做的正确方法还是我们应该在面试中实现的更好方法？

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

正如我在评论中提到的，您的解决方案并没有真正解决问题，因为 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++];
  }
}