1. 栈
1.1 栈的概念
栈：一种特殊的线性表，其**只允许在固定的一端进行插入和删除元素操作（表的末端）。**进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
对栈的基本操作有push（入栈）和pop（出栈），前者相当于插入，后者则时删除最后插入的元素。
栈又称为 LIFO（后进先出）表。
栈在生活中的例子：
1.2 栈的使用
| 方法 | 功能 |
| Stack() | 构造一个空的栈 |
| E push(E e) | 将e入栈，并返回e |
| E pop() | 将栈顶元素出栈并返回 |
| E peek() | 获取栈顶元素 |
| int size() | 获取栈中有效元素的个数 |
| boolean empty() | 检测栈是否为空 |
2. 栈的模拟实现
栈的定义
- 定义一个数组，用于存储栈的元素
public int[] elem;
- 定义一个变量，用于记录栈的有效元素个数
public int usedSize;
- 定义一个常量
NUMBER，其值为10，表示栈的默认大小
public static final int NUMBER = 10;
- 构造方法，初始化栈
public MyStack() { this.elem = new int[NUMBER]; }
栈的定义完整代码：
public class MyStack { public int[] elem; // 定义一个数组 public int usedSize; // 记录数组中数据有效的个数 public static final int NUMBER = 10; // 默认数组长度为10 public MyStack() { this.elem = new int[NUMBER]; } }
入栈（push操作）
- 定义方法判断栈是否已满（即是否还有入栈空间）：如果
usedSize等于数组长度，则表示栈已满，返回true；否则返回false
public boolean isFull() { return usedSize == elem.length; }
- 判断栈是否已满（
usedSize等于数组长度），则需要扩展数组的大小）,使用Arrays.copyOf方法将原数组复制一份，长度为原数组的两倍
public void push(int val) { if (isFull()) { this.elem = Arrays.copyOf(elem,2 * elem.length); } }
- 将
val存入数组的usedSize位置，并将usedSize加1，表示有一个新元素入栈
elem[usedSize] = val; usedSize++;
入栈完整代码：
public void push(int val) { if (isFull()) { this.elem = Arrays.copyOf(elem,2 * elem.length); } elem[usedSize] = val; usedSize++; }
出栈（pop操作）
- 判断栈是否为空，如果为空则抛出异常
if (isEmpty()) { throw new EmptyStackException("栈空"); }
EmptyStackException异常类：
public class EmptyStackException extends RuntimeException{ public EmptyStackException() { } public EmptyStackException(String message) { super(message); } }
- 不为空则
usedSize- 1，表示有一个元素出栈
usedSize--;
- 返回
usedSize位置的元素值（即栈顶元素）
return elem[usedSize];
出栈完整代码：
public int pop() { if (isEmpty()) { throw new EmptyStackException("栈空"); } usedSize--; return elem[usedSize]; }
查看栈顶元素（peek操作）
- 判断栈是否为空，如果为空则抛出异常
if (isEmpty()) { throw new EmptyStackException("栈空"); }
- 返回
uesedSize - 1位置的元素值（即栈顶元素）
return elem[usedSize - 1];
判断栈是否为空
如果usedSize等于0，则表示栈为空，返回true；否则返回false
public boolean isEmpty() { return usedSize == 0; }
3. 完整代码
MyStack类：
import java.util.Arrays; public class MyStack { public int[] elem; // 定义一个数组 public int usedSize; // 记录数组中数据有效的个数 public static final int NUMBER = 10; // 默认数组长度为10 public MyStack() { this.elem = new int[NUMBER]; } // 入栈 public void push(int val) { if (isFull()) { this.elem = Arrays.copyOf(elem,2 * elem.length); } elem[usedSize] = val; usedSize++; } // 判断数组是否存满数据 public boolean isFull() { return usedSize == elem.length; } // 出栈 public int pop() { if (isEmpty()) { throw new EmptyStackException("栈空"); } usedSize--; return elem[usedSize]; } // 判断数组是否为空 public boolean isEmpty() { return usedSize == 0; } public int peek() { if (isEmpty()) { throw new EmptyStackException("栈空"); } return elem[usedSize - 1]; } }
EmptyStackException类：
public class EmptyStackException extends RuntimeException{ public EmptyStackException() { } public EmptyStackException(String message) { super(message); } }
