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());
}
}
5.栈的应用场景
子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中， 直到子程序执行完后再将地址取出，以回到原来的程序中。 递归的调用：可以用来在函数调用的时候存储断点， 储存下一个指令的地址外，也将参数、区域变量等数据存入栈中。 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。 二叉树的遍历。 图形的深度优先(depth一first)搜索法。
