1.3 Bags, Queues, and Stacks：访问顺序与表示选择

按官方1.3重建Bag、Queue、Stack API，扩缩容数组、链表实现、泛型迭代与Dijkstra双栈求值。

从“同样存三个items，为什么不能只用一个List”开始

背包、队列与栈（，bags, queues, and stacks）都能保存items，却表达不同算法语义。Bag只承诺收集和遍历；Queue按first-in-first-out处理arrival；Stack按last-in-first-out处理nested或需要反向恢复的工作。

先预测依次加入A、B、C后，三者的foreach是否都应输出A、B、C。Queue是FIFO，通常如此；Stack的official iterator按LIFO输出C、B、A；Bag client根本不应依赖顺序。若用一个通用List却把访问policy留给每个caller，算法正确性会散落在index convention里，API无法替你守住order invariant。

官方1.3依次覆盖 APIs、Array and resizing array implementations of collections、Linked lists、Linked-list implementations of collections、Iteration。Applications还包括Dijkstra双栈算术表达式求值。这里从abstract policy走到两种representation，再回到client-visible iteration。

1.3.1 Collection APIs：把访问顺序写进operation names

集合API（，collection APIs）应让错误operation难以表达。Stack使用 push/pop，Queue使用 enqueue/dequeue，Bag只提供 add；如果都暴露 remove(int index)，policy就不再由ADT保证。

public interface Stack<Item> {
    void push(Item item);
    Item pop();
    Item peek();
    boolean isEmpty();
    int size();
}
 
public interface Queue<Item> {
    void enqueue(Item item);
    Item dequeue();
    Item peek();
    boolean isEmpty();
    int size();
}

Official implementations是generic并实现 Iterable<Item>。Autoboxing允许 Stack<Integer> 接收int literals，但container实际保存Integer references；Integer identity与numeric value仍不能混淆。Empty removal属于underflow，current code抛 NoSuchElementException，client应在API层知道，而不是依赖null作为合法item与empty marker的二义值。

Bag常用于不需要removal的统计或graph adjacency collection；Queue用于BFS、event arrival；Stack用于DFS、parsing、backtracking和method-call-like nesting。选择不是性能表查一行，而是先把problem order semantics固定。

1.3.2 Resizing array：用几何扩缩容获得均摊常数

动态调整数组（，resizing arrays）保持items在 a[0..n-1]。Push在 n == a.length 时分配double capacity并复制；pop清空slot，若size降到quarter capacity则halve。

public void push(Item item) {
    if (n == a.length) resize(2 * a.length);
    a[n++] = item;
}
 
public Item pop() {
    if (isEmpty()) throw new NoSuchElementException("Stack underflow");
    Item item = a[n - 1];
    a[n - 1] = null;            // avoid loitering
    n--;
    if (n > 0 && n == a.length / 4) resize(a.length / 2);
    return item;
}

单次resize是linear copy，但capacity doubling意味着连续push中，每个旧item被复制的总次数受geometric series约束，push是amortized constant time。Pop若在half-full立即halve，下一次push可能马上double，交替操作造成resize thrashing；quarter-full才halve保留hysteresis，并让capacity维持在size的常数倍。

对象游离（，loitering）解释为什么要把removed slot设为null。Logical size已经减小并不自动清除reference；长期stack若保留large objects会形成memory leak-like retention。

Java不能直接 new Item[capacity]，因为generic type erasure与reified arrays不兼容。Official code创建 new Object[capacity] 后做受控cast；安全依赖private array只通过Item-typed API进入，不能把它暴露成可写Object array。

1.3.3 Linked lists：节点与局部pointer rewiring

链表（，linked lists）把capacity问题换成每item node overhead和pointer locality。Singly linked stack把top保存在 first，push在head插入，pop移除head：

private Node<Item> first;
private int n;
 
public void push(Item item) {
    Node<Item> oldFirst = first;
    first = new Node<Item>();
    first.item = item;
    first.next = oldFirst;
    n++;
}
 
public Item pop() {
    if (isEmpty()) throw new NoSuchElementException("Stack underflow");
    Item item = first.item;
    first = first.next;
    n--;
    return item;
}

每个operation只改constant number of references，因此worst-case constant time，不需要amortization。Representation invariant包括：n == 0 iff first == null；沿next恰好走到n个nodes后到null；不存在cycle。只测push/pop outputs无法发现错误n或隐藏cycle，invariant checker应独立遍历。

1.3.4 Linked queue：first与last必须同步

Queue需要在tail插入、head删除，因此同时保存 first 与 last。Enqueue到empty queue时二者指向same new node；dequeue最后一个item后，first 变null，也必须把 last 设null。

public void enqueue(Item item) {
    Node<Item> oldLast = last;
    last = new Node<Item>();
    last.item = item;
    if (isEmpty()) first = last;
    else oldLast.next = last;
    n++;
}
 
public Item dequeue() {
    if (isEmpty()) throw new NoSuchElementException("Queue underflow");
    Item item = first.item;
    first = first.next;
    n--;
    if (isEmpty()) last = null;
    return item;
}

如果遗漏最后一行，logical queue虽empty，last 仍引用removed node；下一次enqueue的empty branch会重设first/last，功能测试可能暂时通过，但representation不干净并保留旧object。应核查empty iff first和last都null，nonempty时last.next为null。

1.3.5 Iteration：暴露顺序，不暴露representation

迭代（，iteration）由 Iterable<Item> 与 Iterator<Item> 协作。Collection的 iterator() 创建独立cursor；hasNext 判断，next 返回item并推进。Array stack从 n-1 倒着走，linked stack从first沿next走，二者都给LIFO order。

private class ReverseArrayIterator implements Iterator<Item> {
    private int i = n - 1;
 
    public boolean hasNext() { return i >= 0; }
    public Item next() {
        if (!hasNext()) throw new NoSuchElementException();
        return a[i--];
    }
}

Iterator封装traversal mechanics，但order仍是behavior。Queue official iterator给FIFO；Stack给LIFO；Bag只保证visit all items，client不应把当前linked implementation的reverse insertion order当永久contract。Concurrent modification policy也要明确；本节minimal iterators不是fail-fast correctness guarantee。

1.3.6 Dijkstra双栈求值：ADT policy直接成为算法

Fully parenthesized arithmetic expression可用两个stacks单遍求值：operator压入ops，number压入vals；遇右括号时弹出一个operator和所需operands，计算后把result压回vals。LIFO正好匹配最近尚未完成的nested operation。

Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
 
while (!StdIn.isEmpty()) {
    String token = StdIn.readString();
    if      (token.equals("(")) { }
    else if (token.equals("+")) ops.push(token);
    else if (token.equals("*")) ops.push(token);
    else if (token.equals(")")) {
        String op = ops.pop();
        double right = vals.pop();
        double left = vals.pop();
        vals.push(op.equals("+") ? left + right : left * right);
    }
    else vals.push(Double.parseDouble(token));
}

Official Evaluate 支持 + - * / sqrt，并要求tokens由whitespace分开且每个operation fully parenthesized。Subtraction和division必须保留operand order：先pop的是right operand。若输入malformed，underflow或剩余items应被视为parse failure，不能只打印偶然top value。

统一验收：从访问policy到representation invariant

本章回顾

  1. Bags, queues, and stacks以API固定collection访问policy，而非只换operation names。
  2. Collection APIs应说明generic item、underflow、size与iteration behavior。
  3. Resizing arrays以doubling和quarter-full halving获得amortized constant operations与bounded spare space。
  4. Removed array slots要null以避免loitering，generic arrays需要受控representation。
  5. Linked stack只维护first；linked queue维护first/last并在empty transition同步清理。
  6. Iteration隐藏traversal mechanics，但client-visible order仍需明确。
  7. Dijkstra two-stack evaluation说明LIFO policy如何直接支撑nested expression algorithm。

名词解释

讨论

评论区加载中…