1、设计并实现栈 （1）实现顺序存储结构的顺序栈SqStack 实现链表存储结构的链式栈LinkStack

栈是一种只允许在一端进行插入和删除操作的数据结构，通常称为“先进后出”（Last In First Out, LIFO）。这里我会分别介绍如何实现顺序存储结构的顺序栈（也称数组栈）和链式存储结构的链式栈。

**1. 顺序存储结构的顺序栈（SqStack - 数组实现）**

public class SqStack {
    private int[] stackArray;
    private int top;

    // 构造函数初始化数组大小
    public SqStack(int capacity) {
        stackArray = new int[capacity];
        top = -1;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 栈满判断
    public boolean isFull() {
        return top == stackArray.length - 1;
    }

    // 入栈元素
    public void push(int value) {
        if (isFull()) {
            throw new StackOverflowError("Stack is full");
        }
        stackArray[++top] = value;
    }

    // 出栈元素（返回值）
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException("Stack is empty");
        }
        return stackArray[top--];
    }

    // 查看栈顶元素但不移除
    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException("Stack is empty");
        }
        return stackArray[top];
    }
}

**2. 链式存储结构的链式栈（LinkStack - 链表实现）**

public class LinkStack {
    private class Node {
        int data;
        Node next;
    }

    private Node top;

    public LinkStack() {
        top = null;
    }

    // 同上，添加对应方法...
    
    public void push(int value) {
        Node newNode = new Node();
        newNode.data = value;
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException("Stack is empty");
        }
        int poppedValue = top.data;
        top = top.next;
        return poppedValue;
    }

    // ...其他方法
}