下压栈（简称栈）是一种基于后进先出（LILO）策略的集合类型。可以使用数组和链表实现。

API

实现

两种实现都支持 forEach 迭代。

数组实现

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;
public class ResizingArrayStack<Item> implements Iterable<Item> {
    // 数组默认初始化大小
    private static final int INIT_CAPACITY = 8;
    // 用于存储元素的数组
    private Item[] a;
    // 当前栈的元素数量
    private int n;
    public ResizingArrayStack() {
        a = (Item[]) new Object[INIT_CAPACITY];
        n = 0;
    }
    /**
     * 判断是否为空栈
     *
     * @return 如果为空返回 true，否则 false
     */
    public boolean isEmpty() {
        return n == 0;
    }
    /**
     * 调整数组大小
     *
     * @param capacity
     */
    private void resize(int capacity) {
        assert capacity >= n;
        Item[] copy = (Item[]) new Object[capacity];
        if (n >= 0) System.arraycopy(a, 0, copy, 0, n);
        a = copy;
    }
    /**
     * 添加新元素
     *
     * @param item
     */
    public void push(Item item) {
        if (n == a.length) resize(2 * a.length);
        a[n++] = item;
    }
    /**
     * 当前栈的元素数量
     *
     * @return 元素数量
     */
    public int size() {
        return n;
    }
    /**
     * 删除并返回最近添加的元素
     *
     * @return 最近添加的元素
     */
    public Item pop() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        Item item = a[n - 1];
        a[n - 1] = null;
        n--;
        if (n > 0 && n == a.length / 4) resize(a.length / 2);
        return item;
    }
    /**
     * 查看最新添加的元素（不删除）
     *
     * @return 最近添加的元素
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("stack underflow");
        return a[n - 1];
    }
    /**
     * 转化为字符串
     *
     * @return 字符串
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this) {
            s.append(item).append(" ");
        }
        return s.toString();
    }
    @Override
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }
    /**
     * 内部类用于 forEach 遍历
     */
    private class ReverseArrayIterator implements Iterator<Item> {
        private int i;
        public ReverseArrayIterator() {
            i = n - 1;
        }
        @Override
        public boolean hasNext() {
            return i >= 0;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
        @Override
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            return a[i--];
        }
    }
    public static void main(String[] args) {
        ResizingArrayStack<String> stack = new ResizingArrayStack<>();
        for (int i = 0; i < 10; i++) {
            //  generator random string
            int leftLimit = 97; // letter 'a'
            int rightLimit = 122; // letter 'z'
            int targetStringLength = 3;
            Random random = new Random();
            String generatedString = random.ints(leftLimit, rightLimit + 1)
                    .limit(targetStringLength)
                    .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
                    .toString();
            stack.push(generatedString);
        }
        // print
        for (String s : stack) {
            System.out.println("str: " + s);
        }
    }
}

链表实现

mport java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;
public class LinkedStack<Item> implements Iterable<Item> {
    private Node first; // 栈顶
    private int N; //  栈的元素数量
    /**
     * node 内部类
     */
    private class Node {
        Item item;
        Node next;
    }
    /**
     * 是否空栈
     *
     * @return 为空返回 true，否者返回 false
     */
    public boolean isEmpty() {
        return first == null;
    }
    /**
     * 当前栈的元素数量
     *
     * @return 元素数量
     */
    public int size() {
        return N;
    }
    /**
     * 添加一个新的元素
     *
     * @param item
     */
    public void push(Item item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }
    /**
     * 删除一个最近添加的元素
     *
     * @return 最近添加的元素
     */
    public Item pop() {
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
    /**
     * 返回最近添加的元素（不删除）
     *
     * @return 最近添加的元素
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        return first.item;
    }
    /**
     * 转化为字符串
     *
     * @return 字符串
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this) {
            s.append(item).append(" ");
        }
        return s.toString();
    }
    /**
     * 检测内部变量
     *
     * @return
     */
    private boolean check() {
        if (N < 0) {
            return false;
        }
        if (N == 0) {
            if (first != null) return false;
        } else if (N == 1) {
            if (first == null) return false;
            if (first.next != null) return false;
        } else {
            if (first == null) return false;
            if (first.next == null) return false;
        }
        int numberOfNodes = 0;
        for (Node x = first; x != null && numberOfNodes <= N; x = x.next) {
            numberOfNodes++;
        }
        return numberOfNodes == N;
    }
    @Override
    public Iterator<Item> iterator() {
        return new LinkedIterator();
    }
    private class LinkedIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext() {
            return current != null;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
    public static void main(String[] args) {
        LinkedStack<String> stack = new LinkedStack<>();
        for (int i = 0; i < 10; i++) {
            //  generator random string
            int leftLimit = 97; // letter 'a'
            int rightLimit = 122; // letter 'z'
            int targetStringLength = 3;
            Random random = new Random();
            String generatedString = random.ints(leftLimit, rightLimit + 1)
                    .limit(targetStringLength)
                    .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
                    .toString();
            stack.push(generatedString);
        }
        // print
        for (String s : stack) {
            System.out.println("str: " + s);
        }
    }
}

参考：

• 《算法》（第四版）第 1 章 背包、队列和栈