【Java/数据结构】栈（Stack）（图文版）_java stack
本博客将带大家一起学习基本数据结构之一——栈（Stack），虽然Java当中的Stack集合已经被Deque（双端队列）替代了，但是他的基本思想和实现还是有必要学习的。
一.初识栈
1.基本概念
堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
简单来讲，栈就是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
如下是它在Java集合框架中的位置：
ps：由于Vector设计过时，所以继承自他的Stack也被替代了。
2.特性
LIFO：即Last In First Out，后进先出原则。
类似于坐电梯，先走进去的人后出来；或者上子弹，最先进弹夹的子弹最后打出。
3.核心操作
入栈（push）、出栈（pop）、查看栈顶（peek）
二.栈的模拟实现
老规矩，先看源码：
我们不难发现栈的实现相当简单，底层就是一个数组，同时Stack类也相当简单，仅仅只有140余行。
接下来我们不考虑泛型与io，存储的数据默认为int，来实现一个简单的栈，以理解栈的底层原理。
1.经典实现
最经典的就是基于数组的实现：
（1）基本结构
public class MyStack { private int[] elements; // 存储元素的数组 private int top; // 栈顶指针（初始为-1） private static final int DEFAULT_CAPACITY = 10; // 构造方法 public MyStack() { this(DEFAULT_CAPACITY); } public MyStack(int initialCapacity) { if (initialCapacity <= 0) { throw new IllegalArgumentException(\"容量必须为正数\"); } this.elements = new int[initialCapacity]; top = -1; } ......说明：
由于是基于数组实现的，所以不得不考虑动态扩容机制。
我们提供2种构造方法，一种指定初始容量，另一种不指定，使用默认容量，即DEFAULT_CAPACITY这一静态变量。
我们提供一个指针来指示栈顶，即top。
（2）动态扩容
// 动态扩容private void resize(int newCapacity) { int[] newArray = new int[newCapacity]; System.arraycopy(elements, 0, newArray, 0, top + 1); elements = newArray;}说明：
System.arraycopy(elements, 0, newArray, 0, top + 1);复制数组参数（原数组，复制起始位置，复制目的地，目的地起始位置，复制长度）
（3）入栈（push）
// 入栈（带动态扩容）public void push(int value) { // 检查是否需要扩容 if (top == elements.length - 1) { resize(2 * elements.length); } elements[++top] = value;}（4）出栈（pop）
// 出栈public int pop() { if (isEmpty()) { throw new IllegalStateException(\"栈为空\"); } return elements[top--];}（5）查看栈顶（peek）
// 查看栈顶元素public int peek() { if (isEmpty()) { throw new IllegalStateException(\"栈为空\"); } return elements[top];}（6）其他
// 判断是否为空public boolean isEmpty() { return top == -1;}// 获取元素数量public int size() { return top + 1;}（7）完整实现与测试
public class MyStack { private int[] elements; // 存储元素的数组 private int top; // 栈顶指针（初始为-1） private static final int DEFAULT_CAPACITY = 10; // 构造方法 public MyStack() { this(DEFAULT_CAPACITY); } public MyStack(int initialCapacity) { if (initialCapacity <= 0) { throw new IllegalArgumentException(\"容量必须为正数\"); } elements = new int[initialCapacity]; top = -1; } // 入栈（带动态扩容） public void push(int value) { // 检查是否需要扩容 if (top == elements.length - 1) { resize(2 * elements.length); } elements[++top] = value; } // 出栈 public int pop() { if (isEmpty()) { throw new IllegalStateException(\"栈为空\"); } return elements[top--]; } // 查看栈顶元素 public int peek() { if (isEmpty()) { throw new IllegalStateException(\"栈为空\"); } return elements[top]; } // 判断是否为空 public boolean isEmpty() { return top == -1; } // 获取元素数量 public int size() { return top + 1; } // 动态扩容 private void resize(int newCapacity) { int[] newArray = new int[newCapacity]; System.arraycopy(elements, 0, newArray, 0, top + 1); elements = newArray; } // 测试代码 public static void main(String[] args) { MyStack stack = new MyStack(3); // 测试入栈和扩容 stack.push(10); stack.push(20); stack.push(30); stack.push(40); // 触发扩容到6 System.out.println(\"栈顶元素: \" + stack.peek()); // 输出40 System.out.println(\"元素数量: \" + stack.size()); // 输出4 // 测试出栈 System.out.println(\"出栈: \" + stack.pop()); // 40 System.out.println(\"出栈: \" + stack.pop()); // 30 System.out.println(\"剩余元素数量: \" + stack.size()); // 2 }}2.链表实现
除了使用数组存储数据，使用链表也是可以的，并且使用链表不用考虑动态扩容。
（1）基本结构
public class MyLinkedStack { private static class Node { int data; Node next; Node(int data) { this.data = data; } } private Node top; // 栈顶节点 private int size; // 元素数量 ......（2）入栈（push）
public void push(int value) { Node newNode = new Node(value); newNode.next = top; // 新节点指向原栈顶 top = newNode; // 更新栈顶 size++;}（3）出栈（pop）
public int pop() { if (isEmpty()) { throw new IllegalStateException(\"栈为空\"); } int value = top.data; top = top.next; // 移动栈顶指针 size--; return value;}特别注意栈为空时会报错，所以要检查栈是否为空。
（4）查看栈顶（peek）
public int peek() { if (isEmpty()) { throw new IllegalStateException(\"栈为空\"); } return top.data;}（5）其他
public boolean isEmpty() { return top == null;}public int size() { return size;}（6）完整实现与测试
public class MyLinkedStack { private static class Node { int data; Node next; Node(int data) { this.data = data; } } private Node top; // 栈顶节点 private int size; // 元素数量 public void push(int value) { Node newNode = new Node(value); newNode.next = top; // 新节点指向原栈顶 top = newNode; // 更新栈顶 size++; } public int pop() { if (isEmpty()) { throw new IllegalStateException(\"栈为空\"); } int value = top.data; top = top.next; // 移动栈顶指针 size--; return value; } public int peek() { if (isEmpty()) { throw new IllegalStateException(\"栈为空\"); } return top.data; } public boolean isEmpty() { return top == null; } public int size() { return size; } // 测试代码 public static void main(String[] args) { MyLinkedStack stack = new MyLinkedStack(); stack.push(100); stack.push(200); System.out.println(stack.pop()); // 200 System.out.println(stack.peek()); // 100 }}三.栈的使用
请见以下代码:
import java.util.Stack;public class StackDemo { public static void main(String[] args) { // 1. 创建栈对象 Stack stack = new Stack(); // 2. 压栈操作（push） System.out.println(\"----- 压栈操作 -----\"); stack.push(10); stack.push(20); stack.push(30); System.out.println(\"当前栈内容: \" + stack); // 输出: [10, 20, 30] // 3. 查看栈顶（peek） System.out.println(\"\\n----- 查看栈顶 -----\"); System.out.println(\"栈顶元素: \" + stack.peek()); // 输出: 30 System.out.println(\"查看后栈内容: \" + stack); // 保持原样 // 4. 弹栈操作（pop） System.out.println(\"\\n----- 弹栈操作 -----\"); System.out.println(\"弹出元素: \" + stack.pop()); // 输出: 30 System.out.println(\"弹出后栈内容: \" + stack); // 输出: [10, 20] // 5. 检查空栈（empty） System.out.println(\"\\n----- 检查空栈 -----\"); System.out.println(\"栈是否为空? \" + stack.empty()); // 输出: false // 6. 搜索元素（search） System.out.println(\"\\n----- 搜索元素 -----\"); int target = 20; int position = stack.search(target); System.out.println(\"元素 \" + target + \" 的位置: \" + position); // 输出: 1（栈顶为1） // 7. 清空栈 System.out.println(\"\\n----- 清空栈 -----\"); while (!stack.empty()) { System.out.println(\"弹出: \" + stack.pop()); } System.out.println(\"清空后栈是否为空? \" + stack.empty()); // 输出: true }}更多信息请见官方文档说明：
Stack (Java Platform SE 8 )
四.栈的典型应用
1.括号匹配算法
该算法能自动检验输入的字符串中括号是否正确匹配：
import java.util.Stack;public class BracketMatcher { public static boolean isValid(String s) { Stack stack = new Stack(); for (char c : s.toCharArray()) { // 遇到左括号时，将对应的右括号压入栈 switch (c) { case \'(\': stack.push(\')\'); break; case \'[\': stack.push(\']\'); break; case \'{\': stack.push(\'}\'); break; default: // 遇到右括号时，检查栈顶是否匹配 if (stack.isEmpty() || stack.pop() != c) { return false; } } } // 最终栈必须为空才表示完全匹配 return stack.isEmpty(); }}原理请见LeetCode：20. 有效的括号 - 力扣（LeetCode）
2.逆波兰表达式（计算机的算数运算）
import java.util.Stack;public class ReversePolishNotation { public static int evalRPN(String[] tokens) { Stack stack = new Stack(); for (String token : tokens) { // 遇到运算符时进行计算 if (isOperator(token)) { int b = stack.pop(); int a = stack.pop(); stack.push(calculate(a, b, token)); } // 遇到数字时压栈 else { stack.push(Integer.parseInt(token)); } } return stack.pop(); } // 判断是否是运算符 private static boolean isOperator(String s) { return s.equals(\"+\") || s.equals(\"-\") || s.equals(\"*\") || s.equals(\"/\"); } // 执行运算（注意操作数顺序） private static int calculate(int a, int b, String op) { switch (op) { case \"+\": return a + b; case \"-\": return a - b; case \"*\": return a * b; case \"/\": return a / b; // 题目通常要求整数除法向零取整 default: throw new IllegalArgumentException(\"非法运算符\"); } } public static void main(String[] args) { // 测试案例 String[][] testCases = { {\"2\",\"1\",\"+\",\"3\",\"*\"}, // (2+1)*3=9 {\"4\",\"13\",\"5\",\"/\",\"+\"}, // 4+(13/5)=6 {\"10\",\"6\",\"9\",\"3\",\"+\",\"-11\",\"*\",\"/\",\"*\",\"17\",\"+\",\"5\",\"+\"} // 10*(6/((9+3)*-11))+17+5 }; for (String[] testCase : testCases) { System.out.println(\"表达式: \" + String.join(\" \", testCase)); System.out.println(\"结果: \" + evalRPN(testCase) + \"\\n\"); } }}详情请见：150. 逆波兰表达式求值 - 力扣（LeetCode）
结语
关于用Deque替代Stack的事，我们在队列Quque中会讲到，敬请期待！
如果有帮助不妨点个赞吧，下期就是Quque了！( ´∀｀)つt[ ]
