背包、队列和栈

API介绍

---

背包

public class Bag<Item> implements Iterable<Item>
{
            Bag()              // 创建一个空背包
    void    add(Item item)     // 向背包中添加一个元素
    boolean isEmpty()          // 背包是否为空
    int     size()             // 背包中的元素数量
}         

队列

public class Queue<Item> implements Iterable<Item>
{
            Queue()            // 创建空队列
    void    enqueue(Item item) // 添加一个元素
    Item    dequeue()          // 删除最早添加的元素
    boolean isEmpty()          // 队列是否为空
    int     size()             // 队列中的元素数量
}

栈

public class Stack<Item> implements Iterable<Item>
{
            Stack()             // 创建一个空栈
    void    push(Item item)     // 压入一个元素
    Item    pop()               // 推出最后压入的元素
    boolean isEmpty()           // 栈是否为空
    int     size()              // 栈中的元素数量
}

特点及用例

---

背包

• 不支持从中删除元素
• 迭代的顺序不确定且与用例无关

// 用于计算平均数和标准差
public class Stats
{
    public static void main(String[] args)
    {
        Bag<Double> numbers = new Bag<Double>();
        while (!StdIn.isEmpty())
            numbers.add(StdIn.readDouble());
        int N = numbers.size();

        double sum = 0.0;
        for (double x : numbers)
            sum += x;
        double mean = sum/N;  // 平均数

        sum = 0.0;
        for (double x : numbers)
            sum += (x - mean)*(x - mean);
        double std = Math.sqrt(sum/(N-1));  // 标准差

        StdOut.printf("Mean: %.2f\n", mean);
        StdOut.printf("Std: %.2f\n", std);
    }
}

队列

• 先进先出（FIFO）
• 入列顺序和出列顺序相同

// 将队列的中数字拷贝到数组当中
public static int[] readInts(String name)
{
    In in = new In(name);
    Queue<Integer> q = new Queue<Integer>();
    while (!in.isEmpty())
        q.enqueue(in.readInt()); // 从文件中读入整数, 加入队列(自动装箱)

    int N = q.size();
    int[] a = new int[N];  // 数组定义初始化
    for (int i = 0; i < N; i++)
        a[i] = q.dequeue();  // FIFO: 顺序保持不变
    return a;
}

栈

• 后进先出（LIFO）
• 可是使用双栈来求解数学运算

public class Evaluate
{
    public static void main(String[] args)
    {
        Stack<String> ops = new Stack<String>();  // 操作符栈
        Stack<Double> vals = new Stack<Double>();  // 操作数栈
        while (!StdIn.isEmpty())
        {
            String s = StdIn.readString();
            if      (s.equals("("));
            else if (s.equals("+"))      ops.push(s);
            else if (s.equals("-"))      ops.push(s);
            else if (s.equals("*"))      ops.push(s);
            else if (s.equals("/"))      ops.push(s);
            else if (s.equals(")"))
            {
                String op = ops.pop();  // 弹出操作符
                double v  = vals.pop(); // 弹出操作数
                if      (op.equals("+")) v = vals.pop() + v;  
                else if (op.equals("-")) v = vals.pop() - v;  
                else if (op.equals("*")) v = vals.pop() * v;
                else if (op.equals("/")) v = vals.pop() / v;
                vals.push(v);
            }
            else vals.push(Double.parseDouble(s));
        }
        StdOut.println(vals.pop());
    }
}

集合类数据类型的实现

---

动态变容量的栈(数组实现)

1. 需要resize方法动态扩展栈的容量
2. push的时候，需要检查栈和数组的大小，合适的时候进行扩容
3. pop的时候，当栈的大小小于数组的1/4的时候，数组缩减为原来的1/2
4. pop的时候，将不使用的对象置为null，方便垃圾回收
5. 实现iterable接口，方便遍历

import java.util.Iterator
public class ResizeingArrayStack<Item> implements Iterable<Item> {
  private Item[] a = (Item[]) new Object[1]; // 栈元素  
  private int N = 0; // 元素数量  
  public boolean isEmpty() {return N == 0;}
  public int size() {return N;}
  private void resize(int max) {
    // 将一个数组移动到一个新的数组当中
    Item[] temp = (Item[]) new Object[max];
    for (int i = 0; i < N; i++)
      temp[i] = a[i];
    a = temp;
  }

  public void push(Item item) {
    if (N == a.length) {resize(2 * a.length)}
    a[N++] = item;
  }

  public Item pop() {
    Item item = a[--N];
    a[N] = null;// 避免对象游离
    if (N > 0 &&N < a.length / 4) 
      resize(a.length / 2);
  }
 
  public Iterator<Item> iterator() {
    return new ReverseArrayIterator()
  }

  private class ReverseArrayIterator implements Iterator<Item>{
    // 实现后进先出的迭代顺序
    private int i = N;
    public boolean hasNext() { return N > 0; }
    public Item next() { return a[--i]; }
    public void remove() {}
  }
} 

动态变容量的栈(链表实现)

import java.util.Iterator
public class Stack<Item> implements Iterable<Item> {
    private Node first;
    private int N;
    private class Node {
        Item item;
        Node next;
    }
    
    public boolean isEmpty(){
        return N == 0;
    }
    
    public int size() {
        return N;
    }
    
    public void push(Item item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }
    
    public Item pop() {
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
}

动态变容量的队列(链表实现)

由于实现队列需要使用两个指针（first/last）， 所以需要考虑一些特殊情况。

1. 入队列的时候，如果只有一个元素，需要将first和last都指向第一个元素
2. 出队列的时候，如果是最后一个元素，需要将last置为null

import java.util.Iterator
public class Queue<Item> implements Iterable<Item> {
    private Node first;
    private Node last;
        private int N;
    private class Node {
        Item item;
        Node next;
    }
    
    public boolean isEmpty(){
        return N == 0;
    }
    
    public int size() {
        return N;
    }
    
    public void enqueue(Item item) {
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if(isEmpty())
            first = last;
        else 
            oldLast.next = last;
        N++;
    }
    
    public Item dequeue() {
        Item item = first.item;
        first = first.next;
        if(isEmpty())
            last = null;
        N--;
        return item;
    }
}