1.栈的定义

栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top）。

栈的插入操作，叫做入栈（push）。存入栈的元素之间没有任何具体的关系，只有到来的时间的先后顺序。

入栈图

出栈图

入栈操作涉及的单个数据的进入，所以时间复杂度为 O(1)，同时入栈过程中只需要单个的临时存储空间，所以空间复杂度为 O(1)。

2.栈的存储原理

栈既可以用数组来实现，也可以用链表来实现

栈的数组实现如下:

数组实现的栈也叫顺序栈或静态栈

栈的链表实现如下：

3.栈的操作-数组实现

入栈

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶

出栈（弹栈）

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

public class ArrayStack { private int[] array; // 存储栈元素的数组    private int top; // 栈顶指针，指向栈顶元素在数组中的位置    private int capacity; // 栈的最大容量
    // 构造函数，创建一个指定容量的栈    public ArrayStack(int capacity) {        this.capacity = capacity;        this.array = new int[capacity];        this.top = -1; // 栈为空，栈顶指针为-1    }
    // 将给定的元素推送到栈的顶部    public void push(int item) {        if (isFull()) { // 如果栈已满，抛出异常            throw new RuntimeException("Stack is full");        }        array[++top] = item; // 将元素放入栈顶，同时栈顶指针+1    }
    // 从栈的顶部删除元素并返回该元素    public int pop() {        if (isEmpty()) { // 如果栈为空，抛出异常            throw new RuntimeException("Stack is empty");        }        return array[top--]; // 返回栈顶元素，同时栈顶指针-1    }
    // 返回栈顶元素但不删除它    public int peek() {        if (isEmpty()) { // 如果栈为空，抛出异常            throw new RuntimeException("Stack is empty");        }        return array[top]; // 返回栈顶元素，但不修改栈顶指针    }
    // 如果栈为空，则返回true，否则返回false    public boolean isEmpty() {        return top == -1; // 栈顶指针为-1表示栈为空    }
    // 如果栈已满，则返回true，否则返回false    public boolean isFull() {        return top == capacity - 1; // 栈顶指针+1等于栈容量表示栈已满    }
    // 返回栈中元素的数量    public int size() {        return top + 1; // 栈顶指针+1即为栈中元素的数量    }
    // 清空栈中的所有元素    public void clear() {        top = -1; // 将栈顶指针重置为-1，表示栈为空    }}

在上面的示例中，我们定义了一个ArrayStack类，该类使用数组实现栈。该类具有以下主要方法：

push(item)：将给定的元素推送到栈的顶部。
pop()：从栈的顶部删除元素并返回该元素。
peek()：返回栈顶元素但不删除它。
isEmpty()：如果栈为空，则返回true，否则返回false。
isFull()：如果栈已满，则返回true，否则返回false。
size()：返回栈中元素的数量。
clear()：清空栈中的所有元素。

测试代码

public class ArrayStackTest {    public static void main(String[] args) {        // 创建一个容量为5的栈        ArrayStack stack = new ArrayStack(5);
        // 测试栈的基本操作        stack.push(1); // 入栈1        stack.push(2); // 入栈2        stack.push(3); // 入栈3        System.out.println("栈顶元素为：" + stack.peek()); // 输出栈顶元素3        stack.pop(); // 出栈3        System.out.println("栈顶元素为：" + stack.peek()); // 输出栈顶元素2        stack.push(4); // 入栈4        stack.push(5); // 入栈5        System.out.println("栈是否为空：" + stack.isEmpty()); // 输出false        System.out.println("栈是否已满：" + stack.isFull()); // 输出true        System.out.println("栈中元素个数为：" + stack.size()); // 输出4
        // 测试异常情况        try {            stack.push(6); // 入栈6，栈已满，抛出异常        } catch (RuntimeException e) {            System.out.println("异常信息：" + e.getMessage());        }        stack.pop(); // 出栈5        stack.pop(); // 出栈4        stack.pop(); // 出栈2        stack.pop(); // 出栈1        System.out.println("栈是否为空：" + stack.isEmpty()); // 输出true        try {            stack.pop(); // 出栈空栈，抛出异常        } catch (RuntimeException e) {            System.out.println("异常信息：" + e.getMessage());        }    }}

4.栈的操作-链表实现

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

代码实现

import java.util.LinkedList;
public class LinkedStack<T> {
    private LinkedList<T> stackList; // 创建LinkedList类型的变量stackList，用于存储栈元素
    // 构造函数，创建一个空的LinkedList对象    public LinkedStack() {        stackList = new LinkedList<>();    }
    // 将元素添加到栈的顶部，即链表的头部    public void push(T item) {        stackList.addFirst(item);    }
    // 弹出并返回栈顶元素，同时将其从链表中删除    public T pop() {        if (stackList.isEmpty()) { // 如果栈为空，则抛出异常            throw new RuntimeException("Stack is empty");        }        return stackList.removeFirst(); // 否则弹出并返回栈顶元素    }
    // 返回栈顶元素，但不弹出它    public T peek() {        if (stackList.isEmpty()) { // 如果栈为空，则抛出异常            throw new RuntimeException("Stack is empty");        }        return stackList.getFirst(); // 否则返回栈顶元素    }
    // 判断栈是否为空    public boolean isEmpty() {        return stackList.isEmpty();    }
    // 返回栈的元素数量    public int size() {        return stackList.size();    }}

该类有一个泛型类型T，用于存储栈元素。在构造函数中，我们创建了一个空的LinkedList对象来存储栈元素。

push方法将元素添加到栈的顶部，即链表的头部。

pop方法弹出并返回栈顶元素，同时将其从链表中删除。

peek方法返回栈顶元素，但不弹出它。

isEmpty方法返回栈是否为空。

size方法返回栈的元素数量。

请注意，如果尝试从空栈中弹出或查看元素，则会抛出RuntimeException。在实际应用中，可能需要使用不同的异常类型来更好地处理这种情况。

测试以上代码

public class LinkedStackTest {    public static void main(String[] args) {        // 创建一个字符串类型的栈        LinkedStack<String> stack = new LinkedStack<>();
        // 测试isEmpty方法，输出true        System.out.println("Stack is empty: " + stack.isEmpty());
        // 测试push方法，添加元素到栈顶        stack.push("first");        stack.push("second");        stack.push("third");
        // 测试size方法，输出3        System.out.println("Stack size: " + stack.size());
        // 测试peek方法，输出"third"        System.out.println("Top element: " + stack.peek());
        // 测试pop方法，弹出并输出"third"        System.out.println("Popped element: " + stack.pop());
        // 再次测试peek方法，输出"second"        System.out.println("Top element: " + stack.peek());
        // 测试pop方法，弹出并输出"second"        System.out.println("Popped element: " + stack.pop());
        // 测试size方法，输出1        System.out.println("Stack size: " + stack.size());
        // 测试isEmpty方法，输出false        System.out.println("Stack is empty: " + stack.isEmpty());    }}