背包、队列和栈

栈

定义

栈是一种基于后进先出(LIFO)策略的集合类型。

API

链表实现

pop

push

代码

public class LinkedStackOfStrings {
    private Node first = null;

    private class Node {
        String item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public void push(String item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }

    public String pop() {
        String item = first.item;
        first = first.next;
        return item;
    }
}

数组实现

Array implementation of a stack.

• Use array s[] to store N items on stack.
• push(): add new item at s[N].
• pop(): remove item from s[N-1].

Defect. Stack overflows when N exceeds capacity.

调整数组大小

• push(): double size of array s[] when array is full.
• pop(): halve size of array s[] when array is one-quarter full.

代码

public class ResizingArrayStackOfStrings {
    private String[] s;
    private int N = 0;

    public ResizingArrayStackOfStrings (int capacity) {
        s = new String[capacity];
    }

    public boolean isEmpty () {
        return N == 0;
    }

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

    public String pop() {
        String item = s[--N];
        s[N] = null;
        if (N > 0 && N == s.length/4) resize(s.length/2);
        return item;
    }

    private void resize(int capacity) {
        String[] copy = new String[capacity];
        for(int i = 0; i < N; i++) {
            copy[i] = s[i];
        }
        s = copy;
    }
}

队列

定义

队列是一种基于先进先出(FIFO)策略的集合类型。

链表实现

enqueue

dequeue

代码

public class LinkedQueueOfStrings {
    private Node first, last;

    private class Node {
        String item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public void enqueue(String item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        // special cases for empty queue
        if (isEmpty()) first = last;
        else oldlast.next = last;
        first.next = oldlast;
    }

    public String dequeue() {
        String item = first.item;
        first = first.next;
        // special cases for empty queue
        if (isEmpty()) last = null;
        return item;
    }
}

数组实现

API

背包

定义

背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历（顺序无关）所有收集到的元素。

API

实现

Stack (without pop) or queue (without dequeue).