[例子和习题出自数据结构(严蔚敏版), 本人使用java进行实现. 转载请注明作者和出处, 如有谬误, 欢迎在评论中指正. ]
栈的实现
栈是一种先进后出的数据结构, 首先定义了栈需要实现的接口:
public interface MyStack<T> {
/**
* 判断栈是否为空
*/
boolean isEmpty();
/**
* 清空栈
*/
void clear();
/**
* 栈的长度
*/
int length();
/**
* 数据入栈
*/
boolean push(T data);
/**
* 数据出栈
*/
T pop();
}
栈的数组实现, 底层使用数组:
public class MyArrayStack<T> implements MyStack<T> {
private Object[] objs = new Object[16];
private int size = 0;
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
// 将数组中的数据置为null, 方便GC进行回收
for (int i = 0; i < size; i++) {
objs[size] = null;
}
size = 0;
}
@Override
public int length() {
return size;
}
@Override
public boolean push(T data) {
// 判断是否需要进行数组扩容
if (size >= objs.length) {
resize();
}
objs[size++] = data;
return true;
}
/**
* 数组扩容
*/
private void resize() {
Object[] temp = new Object[objs.length * 3 / 2 + 1];
for (int i = 0; i < size; i++) {
temp[i] = objs[i];
objs[i] = null;
}
objs = temp;
}
@SuppressWarnings("unchecked")
@Override
public T pop() {
if (size == 0) {
return null;
}
return (T) objs[--size];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("MyArrayStack: [");
for (int i = 0; i < size; i++) {
sb.append(objs[i].toString());
if (i != size - 1) {
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
}
栈的链表实现, 底层使用链表:
public class MyLinkedStack<T> implements MyStack<T> {
/**
* 栈顶指针
*/
private Node top;
/**
* 栈的长度
*/
private int size;
public MyLinkedStack() {
top = null;
size = 0;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
top = null;
size = 0;
}
@Override
public int length() {
return size;
}
@Override
public boolean push(T data) {
Node node = new Node();
node.data = data;
node.pre = top;
// 改变栈顶指针
top = node;
size++;
return true;
}
@Override
public T pop() {
if (top != null) {
Node node = top;
// 改变栈顶指针
top = top.pre;
size--;
return node.data;
}
return null;
}
/**
* 将数据封装成结点
*/
private final class Node {
private Node pre;
private T data;
}
}
两种实现的比较, 主要比较数据入栈和出栈的速度:
@Test
public void testSpeed() {
MyStack<Person> stack = new MyArrayStack<Person>();
int num = 10000000;
long start = System.currentTimeMillis();
for (int i = 0; i < num; i++) {
stack.push(new Person("xing", 25));
}
long temp = System.currentTimeMillis();
System.out.println("push time: " + (temp - start));
while (stack.pop() != null)
;
System.out.println("pop time: " + (System.currentTimeMillis() - temp));
}
MyArrayStack中入栈和出栈10,000,000条数据的时间:
push time: 936
pop time: 47
将MyArrayStack改为MyLinkedStack后入栈和出栈的时间:
push time: 936
pop time: 126
可见两者的入栈速度差不多, 出栈速度MyArrayStack则有明显的优势.
为什么测试结果是这样的? 可能有些朋友的想法是数组实现的栈应该具有更快的遍历速度, 但增删速度应该比不上链表实现的栈才对. 但是栈中数据的增删具有特殊性: 只在栈顶入栈和出栈. 也就是说数组实现的栈在增加和删除元素时并不需要移动大量的元素, 只是在数组扩容时需要进行复制. 而链表实现的栈入栈和出栈时都需要将数据包装成Node或者从Node中取出数据, 还需要维护栈顶指针和前驱指针.
栈的应用举例
1. 将10进制正整数num转换为n进制
private String conversion(int num, int n) {
MyStack<Integer> myStack = new MyArrayStack<Integer>();
Integer result = num;
while (true) {
// 将余数入栈
myStack.push(result % n);
result = result / n;
if (result == 0) {
break;
}
}
StringBuilder sb = new StringBuilder();
// 按出栈的顺序倒序排列即可
while ((result = myStack.pop()) != null) {
sb.append(result);
}
return sb.toString();
}
2. 检验符号是否匹配. '['和']', '('和')'成对出现时字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的.
遍历字符串的每一个char, 将char与栈顶元素比较. 如果char和栈顶元素配对, 则char不入栈, 否则将char入栈. 当遍历完成时栈为空说明字符串是合法的.
public boolean isMatch(String str) {
MyStack<Character> myStack = new MyArrayStack<Character>();
char[] arr = str.toCharArray();
for (char c : arr) {
Character temp = myStack.pop();
// 栈为空时只将c入栈
if (temp == null) {
myStack.push(c);
}
// 配对时c不入栈
else if (temp == '[' && c == ']') {
}
// 配对时c不入栈
else if (temp == '(' && c == ')') {
}
// 不配对时c入栈
else {
myStack.push(temp);
myStack.push(c);
}
}
return myStack.isEmpty();
}
3. 行编辑: 输入行中字符'#'表示退格, '@'表示之前的输入全都无效.
使用栈保存输入的字符, 如果遇到'#'就将栈顶出栈, 如果遇到@就清空栈. 输入完成时将栈中所有字符出栈后反转就是输入的结果:
private String lineEdit(String input) {
MyStack<Character> myStack = new MyArrayStack<Character>();
char[] arr = input.toCharArray();
for (char c : arr) {
if (c == '#') {
myStack.pop();
} else if (c == '@') {
myStack.clear();
} else {
myStack.push(c);
}
}
StringBuilder sb = new StringBuilder();
Character temp = null;
while ((temp = myStack.pop()) != null) {
sb.append(temp);
}
// 反转字符串
sb.reverse();
return sb.toString();
}
分享到：
相关推荐
在这个基于Java的SIP协议栈实现中，我们可以通过提供的源码实例和jar包来理解和学习SIP的工作原理。 首先，我们来看标题中的“java sip 协议栈实现客户端和服务”。这意味着这个项目包含了SIP协议客户端和服务器端...
本项目是利用栈来实现一个简单的计算器，不支持括号表达式的计算，其用户界面是通过Java Swing库构建的。下面将详细介绍这个计算器的实现原理以及涉及到的相关知识点。 1. **栈的基本概念**： 栈是一种线性数据...
总之，这个"Java实例 - 栈的实现源代码-详细教程"将引导你逐步了解和掌握如何在Java中实现和使用栈。通过实践这些源代码，你可以巩固理论知识，提高编程技能，并为解决复杂问题做好准备。无论是初学者还是经验丰富的...
在提供的"栈和队列"压缩包文件中，可能包含了多个Java源代码文件，每个文件都是一个具体的栈或队列应用实例，例如实现括号匹配检查、迷宫路径查找等经典问题。通过分析和运行这些代码，你可以更直观地了解栈和队列在...
本文通过实例代码，详细介绍了 Java 中栈结构的定义和实现，包括入栈、出栈、栈是否为空判断、栈大小计算、打印栈元素等相关操作技巧。通过本文，读者可以更好地理解 Java 中栈结构的实现和应用。
下面我们将深入探讨Java中如何实现栈，并通过实例进行演示。 1. **Java中的栈实现** Java标准库提供了`java.util.Stack`类来实现栈功能。这个类继承自`Vector`类，因此它包含了线程安全的增删查改操作。创建一个栈...
尽管PPT内容没有给出，但可以假设其内容可能涵盖了链表和栈的基本概念、操作和应用实例，有助于学习者通过实践加深理解。 总之，链表和栈是编程中必不可少的数据结构，它们的Java实现可以帮助开发者高效地处理数据...
通过阅读和理解这份文档，你应该能成功地在Java应用程序或Web应用中调用Matlab，实现跨技术栈的协同工作。 总的来说，Java调用Matlab是一个强大且实用的技术结合，它允许开发者充分利用Matlab的计算能力，同时借助...
Java 实现内存动态分配主要涉及Java内存模型以及内存管理机制，包括堆内存和栈内存的分配，以及垃圾回收等概念。下面将详细解释这些知识点。 1. **Java内存模型** Java程序运行时，内存分为堆内存（Heap）和栈内存...
栈的应用举例 1. 将10进制正整数num转换为n进制 private String conversion(int num, int n) { MyStack<Integer> myStack = new MyArrayStack(); Integer result = num; while (true) { // 将余数入栈 ...
《计算机科学丛书·数据结构从应用到实现(Java版)》系统地介绍了数据结构以及数据结构与对象之间的联系。主要内容包括：算法效率的输入规模、阶和大O，数据结构的无序和有序列表...设计和实现满足特定要求的数据结构。
在这个Java算法实例中，"SepStack1501203023"和"LinkStack1501203023"可能代表两个类，分别实现了顺序栈和链栈的抽象数据类型（ADT）。这些类可能包含了如下功能： - `push(E element)`：向栈顶添加一个元素。 - `...
通过本文的介绍，我们了解了Java中堆内存与栈内存的基本概念、特点及其应用场景。正确理解和使用这两种内存类型可以帮助开发者编写更加高效、健壮的代码。同时，在实际开发过程中还需注意合理选择数据存储位置，避免...
- 使用Java的`java.util.Stack`类创建一个栈实例。 - 定义一个映射关系，例如`Map, Character>`，存储每种左括号对应的右括号。 - 遍历字符串，对每个字符执行上述逻辑。 - 可以使用`StringBuilder`收集错误信息...
总结，Java实现WebSocket通信提供了多种途径，Tomcat的原生支持适合简单的应用，而Spring的WebSocket集成则适用于更复杂的业务场景，提供了更丰富的功能和更好的可扩展性。在选择实现方式时，应根据项目需求和技术栈...
在这个主题中，我们将深入探讨JDK的配置、数组的应用以及栈和堆内存的图解，同时通过具体的Java源码来加深理解。 首先，JDK（Java Development Kit）是开发和运行Java应用程序必不可少的软件包。配置JDK主要包括...
### Java 实现显示进度条 #### 背景与需求 在软件开发过程中，特别是涉及到长时间运行的任务时，向用户展示任务完成进度是一项非常实用的功能。进度条是实现这一功能的一种常见方式。本文将详细介绍如何使用Java...
总的来说，这个项目是一个结合了J#编程、栈数据结构应用以及计算器设计的实例。开发者通过J#语言编写了一个能够进行四则运算的计算器程序，利用栈来处理运算符的优先级，使得计算过程符合用户预期，展示了基础的编程...
本实例将深入探讨几种常见的数据结构及其在Java中的实现，包括数组、链表、栈、队列、集合、映射（哈希表）、图和树等。 首先，数组是最基本的数据结构，它提供了一种存储固定数量相同类型元素的方法。在Java中，...
总之，Java中的栈可以通过数组或链表两种方式实现，每种实现都有其优势和适用场景。选择哪种实现取决于具体的应用需求，如内存使用、插入删除效率等因素。在实际编程中，可以根据具体问题来决定采用哪种数据结构实现...