【Java/数据结构】栈（Stack）

server/2025/3/26 3:53:56/

本博客将带大家一起学习基本数据结构之一——栈（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）基本结构

java">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）动态扩容

java">// 动态扩容
private void resize(int newCapacity) {int[] newArray = new int[newCapacity];System.arraycopy(elements, 0, newArray, 0, top + 1);elements = newArray;
}

说明：

java">System.arraycopy(elements, 0, newArray, 0, top + 1);

复制数组参数（原数组，复制起始位置，复制目的地，目的地起始位置，复制长度）

（3）入栈（push）

java">// 入栈（带动态扩容）
public void push(int value) {// 检查是否需要扩容if (top == elements.length - 1) {resize(2 * elements.length);}elements[++top] = value;
}

（4）出栈（pop）

java">// 出栈
public int pop() {if (isEmpty()) {throw new IllegalStateException("栈为空");}return elements[top--];
}

（5）查看栈顶（peek）

java">// 查看栈顶元素
public int peek() {if (isEmpty()) {throw new IllegalStateException("栈为空");}return elements[top];
}

（6）其他

java">// 判断是否为空
public boolean isEmpty() {return top == -1;
}// 获取元素数量
public int size() {return top + 1;
}

（7）完整实现与测试

java">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);  // 触发扩容到6System.out.println("栈顶元素: " + stack.peek()); // 输出40System.out.println("元素数量: " + stack.size()); // 输出4// 测试出栈System.out.println("出栈: " + stack.pop()); // 40System.out.println("出栈: " + stack.pop()); // 30System.out.println("剩余元素数量: " + stack.size()); // 2}
}

2.链表实现

除了使用数组存储数据，使用链表也是可以的，并且使用链表不用考虑动态扩容。

（1）基本结构

java">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）

java">public void push(int value) {Node newNode = new Node(value);newNode.next = top; // 新节点指向原栈顶top = newNode;     // 更新栈顶size++;
}

（3）出栈（pop）

java">public int pop() {if (isEmpty()) {throw new IllegalStateException("栈为空");}int value = top.data;top = top.next; // 移动栈顶指针size--;return value;
}

特别注意栈为空时会报错，所以要检查栈是否为空。

（4）查看栈顶（peek）

java">public int peek() {if (isEmpty()) {throw new IllegalStateException("栈为空");}return top.data;
}

（5）其他

java">public boolean isEmpty() {return top == null;
}public int size() {return size;
}

（6）完整实现与测试

java">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()); // 200System.out.println(stack.peek()); // 100}
}

三.栈的使用

请见以下代码:

java">import java.util.Stack;public class StackDemo {public static void main(String[] args) {// 1. 创建栈对象Stack<Integer> 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()); // 输出: 30System.out.println("查看后栈内容: " + stack);    // 保持原样// 4. 弹栈操作（pop）System.out.println("\n----- 弹栈操作 -----");System.out.println("弹出元素: " + stack.pop());  // 输出: 30System.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.括号匹配算法

该算法能自动检验输入的字符串中括号是否正确匹配：

java">import java.util.Stack;public class BracketMatcher {public static boolean isValid(String s) {Stack<Character> 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.逆波兰表达式（计算机的算数运算）

java">import java.util.Stack;public class ReversePolishNotation {public static int evalRPN(String[] tokens) {Stack<Integer> 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[ ]


http://www.ppmy.cn/server/179133.html

相关文章

Shopify Checkout UI Extensions

Shopify Checkout UI Extensions

结账界面的UI扩展允许应用开发者构建自定义功能&#xff0c;商家可以在结账流程的定义点安装&#xff0c;包括产品信息、运输、支付、订单摘要和Shop Pay。 Shopify官方在去年2024年使用结账扩展取代了checkout.liquid&#xff0c;并将于2025年8月28日彻底停用checkout.liquid…
阅读更多...
三层网络 （服务器1 和 服务器2 在不同网段）

三层网络 （服务器1 和 服务器2 在不同网段）

服务器1 和 服务器2 在不同网段&#xff0c;并且通过三层交换机实现通信 1. 网络拓扑 假设网络拓扑如下&#xff1a; 服务器1&#xff1a; mac0&#xff1a;IP 地址 192.168.1.10/24&#xff0c;网关 192.168.1.1 mac1&#xff1a;IP 地址 10.0.1.10/24&#xff0c;网关 10.0…
阅读更多...
SQL 版本历史

SQL 版本历史

SQL&#xff08;Structured Query Language&#xff09;是一种用于管理和操作关系数据库的标准语言。SQL标准由多个组织制定和维护&#xff0c;主要包括以下几个版本&#xff1a; SQL-86 (SQL-87): 这是SQL的第一个官方标准&#xff0c;由ANSI&#xff08;美国国家标准协会&…
阅读更多...
Linux 基础入门操作 第十二章 TINY Web 服务器

Linux 基础入门操作 第十二章 TINY Web 服务器

1 服务器基础架构 1.1 背景知识 Web 服务器使用 HTTP 协议与客户端&#xff08;即浏览器&#xff09;通信&#xff0c;而 HTTP 协议又基于 TCP/IP 协议。因此我们要做的工作就是利用 Linux 系统提供的 TCP 通信接口来实现 HTTP 协议。 而 Linux 为我们提供了哪些网络编程接口…
阅读更多...
炫酷的3D卡片翻转画廊实现教程

炫酷的3D卡片翻转画廊实现教程

炫酷的3D卡片翻转画廊实现教程 这里写目录标题 炫酷的3D卡片翻转画廊实现教程项目概述核心技术点1. 3D空间设置2. CSS3变换与过渡3. 渐变背景 实现步骤1. HTML结构2. CSS样式3. JavaScript交互 技术难点与解决方案1. 3D效果的实现2. 动画流畅度优化3. 兼容性处理 项目亮点总结 …
阅读更多...
防止重复点击方法总结-微信小程序

防止重复点击方法总结-微信小程序

在微信小程序中&#xff0c;防止重复点击的通用方法可以通过以下几种方式实现&#xff1a; 1. 使用 disabled 属性 在点击事件中&#xff0c;通过设置 disabled 属性来禁用按钮&#xff0c;防止用户重复点击。 <button bindtap"handleClick" disabled"{{isD…
阅读更多...
Android第六次面试总结（okhttp篇）

Android第六次面试总结（okhttp篇）

OkHttp 是一个高效的 HTTP 客户端&#xff0c;它的工作流程包含多个步骤&#xff0c;从请求的创建、发送&#xff0c;到服务器响应的接收和处理&#xff0c;每个环节都有特定的逻辑和组件参与。以下是对 OkHttp 工作流程的详细说明&#xff1a; 1. 请求构建 在使用 OkHttp 发…
阅读更多...
WordPress上传图片时显示“未提供数据”错误

WordPress上传图片时显示“未提供数据”错误

在WordPress中上传图片时显示“未提供数据”的错误&#xff0c;通常是由多种原因引起的&#xff0c;以下是一些常见的问题及其解决方法&#xff1a; 1. 文件权限问题 WordPress需要正确的文件和目录权限才能正常上传图片。如果权限设置不正确&#xff0c;可能会导致无法上传图…
阅读更多...
最新文章

Copyright @ 2022~2023