// 第 7 周 – 用数组实现栈
// 运行：java ArrayStack.java
public class ArrayStack {
    private final int[] data;
    private int top = -1; // 栈顶元素的下标；空栈时为 -1

    ArrayStack(int capacity) {
        data = new int[capacity];
    }

    boolean isEmpty() { return top == -1; }
    boolean isFull() { return top == data.length - 1; }
    int size() { return top + 1; }

    // 压入栈顶 – O(1)
    //   伪代码：If IsFull then ERROR ; top ← top + 1 ; T[top] ← x
    void push(int x) {
        if (isFull()) throw new IllegalStateException("the stack is full (stack overflow)");
        data[++top] = x;
    }

    // 从栈顶弹出 – O(1)
    //   伪代码：If IsEmpty then ERROR ; x ← T[top] ; top ← top − 1 ; Return x
    int pop() {
        if (isEmpty()) throw new IllegalStateException("the stack is empty (stack underflow)");
        return data[top--];
    }

    // 读取栈顶元素但不删除 – O(1)
    int top() {
        if (isEmpty()) throw new IllegalStateException("the stack is empty");
        return data[top];
    }

    public String toString() {
        StringBuilder sb = new StringBuilder("[bottom] ");
        for (int i = 0; i <= top; i++) sb.append(data[i]).append(' ');
        return sb.append("[top]").toString();
    }

    public static void main(String[] args) {
        ArrayStack s = new ArrayStack(5);
        s.push(15);
        s.push(8);
        s.push(42);
        System.out.println(s + "  size=" + s.size());
        System.out.println("top() = " + s.top());
        System.out.println("pop() = " + s.pop());
        System.out.println("pop() = " + s.pop());
        System.out.println(s);

        // 后进先出：元素按相反的顺序取回
        for (int x : new int[] { 1, 2, 3, 4 }) s.push(x);
        System.out.print("order of removal: ");
        while (!s.isEmpty()) System.out.print(s.pop() + " ");
        System.out.println();

        // 错误处理
        try {
            s.pop();
        } catch (IllegalStateException e) {
            System.out.println("Error: " + e.getMessage());
        }

        // Java 推荐的内置栈：ArrayDeque（代替旧的 Stack 类）
        java.util.ArrayDeque<String> st = new java.util.ArrayDeque<>();
        st.push("a");
        st.push("b");
        st.push("c");
        System.out.println("ArrayDeque: peek = " + st.peek() + ", pop = " + st.pop() + ", remaining = " + st);
    }
}