T07. Stacks and Queue

栈

好像没啥东西

队列

用数组实现队列的时候，有一种节约空间的做法，是循环使用数组（确保队列当中元素数量始终不超过数组大小）。循环数组的队列代码示例可以参考课件 40~45 页。

其实就相当于把 head 和 tail 始终 %= n 处理。

双端队列

课件里面没有讲如何实现

优先队列

课件里面提供了一种 $O(n)$ 插入、$O(1)$ 删除的低效优先队列。

这种优先队列是从栈的版本上改动得到的。更确切的说，其实是只有 insert 操作（也就是栈的 push）改了一下。

public void push(int x) {
  int nItems = top + 1;
  if (nItems == 0) {
    stackArray[0] = x;
  } else {
    int j = nItems;
    while (j > 0 && stackArray[j - 1] > x) {
      // 找到合适的位置，再插入
      stackArray[j] = stackArray[j - 1];
      j -= 1;
    }
    stackArray[j] = x;
  }
  top += 1;
}

public void pop() { top -= 1; }
public int top() { return stackArray[top]; }