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

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

正如我在注释中提到的，您的解决方案并不能真正解决这个问题，因为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++];
  }
}

Answer 2

您的答案使用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中的循环，但这将需要用firstIndex和lastIndex替换size；可以再次将它们移到ListArrayQueue中，以节省每个节点的空间。

如果他们要求您从5元素数组中构建一个无限数组，那么您就必须实现类似于B-树的东西。如果没有方便的推荐信，在面试中很难做到。

Answer 3

您可以使用一维数组并使用环绕索引来实现队列，但队列最多可以包含5个元素。

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