`

Java实现数据结构的栈和队列

数据结构 
阅读更多
栈是一种先进后出的数据结构, 首先定义了栈需要实现的接口:

Java代码  
public interface MyStack {   
    /**  
     * 判断栈是否为空  
     */  
    boolean isEmpty();   
    /**  
     * 清空栈  
     */  
    void clear();   
    /**  
     * 栈的长度  
     */  
    int length();   
    /**  
     * 数据入栈  
     */  
    boolean push(T data);   
    /**  
     * 数据出栈  
     */  
    T pop();   
}  

public interface MyStack { 
/** 
* 判断栈是否为空 
*/ 
boolean isEmpty(); 
/** 
* 清空栈 
*/ 
void clear(); 
/** 
* 栈的长度 
*/ 
int length(); 
/** 
* 数据入栈 
*/ 
boolean push(T data); 
/** 
* 数据出栈 
*/ 
T pop(); 
}

栈的数组实现, 底层使用数组: 

public class MyArrayStack implements MyStack {   
    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 = 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  implements MyStack { 
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 = 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  implements MyStack {   
    /**  
     * 栈顶指针  
     */  
    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;   
    }   
}  

public class MyLinkedStack implements MyStack { 
/** 
* 栈顶指针 
*/ 
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; 
} 
}

两种实现的比较, 主要比较数据入栈和出栈的速度: 
Java代码  
@Test  
public void testSpeed() {   
    MyStack stack = new MyArrayStack();   
    int num = 10000000;   
    long start = System.currentTimeMillis();   
    for (int i = 0; i  stack = new MyArrayStack(); 
int num = 10000000; 
long start = System.currentTimeMillis(); 
for (int i = 0; i  myStack = new MyArrayStack();   
    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();   
}  

private String conversion(int num, int n) { 
MyStack myStack = new MyArrayStack(); 
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 myStack = new MyArrayStack();   
    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();   
}  

public boolean isMatch(String str) { 
MyStack myStack = new MyArrayStack(); 
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 myStack = new MyArrayStack();   
    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();   
}

转载出处：http://coolxing.iteye.com/blog/1468674

分享到：
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    数据结构中栈和队列思想的停车场管理系统

    基于c语言数据结构中栈和队列思想的简单停车场管理系统，以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车...

    数据结构试验2-栈和队列实验报告含源码

    1. 实验目的：明确学习栈和队列的目的，比如理解其工作原理，掌握如何实现和应用这些数据结构。 2. 知识回顾：解释栈和队列的基本概念，包括它们的定义、特性以及在实际问题中的应用。 3. 实验设计：描述所使用的...

    数据结构 第3章 栈和队列（课后习题程序实现）.rar

    数据结构 第3章 栈和队列（课后习题程序实现）.rar 数据结构 第3章 栈和队列（课后习题程序实现）.rar 数据结构 第3章 栈和队列（课后习题程序实现）.rar 数据结构 第3章 栈和队列（课后习题程序实现）.rar

    数据结构 实验4 栈和队列

    1. 设计和实现栈和队列的类结构，包括构造函数、压入、弹出、入队、出队等方法。 2. 使用栈来实现简单的逆序输出字符串、括号匹配检查等问题。 3. 使用队列来实现简单的打印队列、银行服务模拟等场景。 4. 探讨栈和...

    数据结构关于栈和队列的实现源代码

    本资源提供了关于栈和队列的源代码实现，这对于理解这两种数据结构的工作原理以及如何在实际编程中应用它们非常有帮助。 首先，我们来深入理解栈和队列的概念： **栈（Stack）**： 栈是一种后进先出（LIFO，Last ...

    用Java实现数据结构中的队列

    在计算机科学中，数据结构是组织、存储和处理数据的方式，...通过理解这些基本概念和代码示例，你可以轻松地在Java项目中实现和使用队列数据结构。记住，选择哪种实现取决于具体的需求，如性能、内存使用和功能需求。

    栈和队列源代码

    在计算机科学中，栈和队列是两种基本的数据结构，它们在编程中有着广泛的应用。栈被称为“后进先出”（LIFO, Last In First Out）数据结构，而队列则是“先进先出”（FIFO, First In First Out）数据结构。这两种...

    数据结构 栈和队列的详细代码~

    在给定的压缩包文件中，"第3章 栈和队列"可能包含了关于这两种数据结构的更深入的理论介绍、实例分析以及具体的编程实现，包括但不限于C++、Java、Python等语言。通过学习这些内容，你可以更好地理解和掌握栈和队列...

    数据结构-线性表、栈、队列

    线性表、栈和队列是数据结构中最基础且广泛使用的三种结构，它们在各种应用程序中都有重要应用。下面将详细讨论这些概念以及JWArray和JWList库在实现这些数据结构时的细节。 首先，线性表是一种基本的数据结构，由n...

    数据结构 栈和队列基本算法

    栈和队列是两种基础且广泛使用的数据结构，它们在编程和算法设计中扮演着重要角色。本篇将深入探讨这两种数据结构的基本原理、实现方式以及常见的应用场景。 栈（Stack）是一种后进先出（LIFO, Last In First Out）...

    数据结构--表、栈、队列（java）

    ### 数据结构概述与Java实现 #### 一、表（List） **表**是一种常见的线性数据结构，它允许用户在任意...这些数据结构在算法设计和软件开发中扮演着极其重要的角色，掌握它们的概念和实现细节对于编程实践至关重要。

    利用栈和队列实现迷宫

    这里我们使用栈和队列两种数据结构来解决这个问题。 栈是一种后进先出（Last In First Out，LIFO）的数据结构，栈可以用来存储迷宫的路径。我们可以通过栈来实现迷宫的求解，首先将起点压入栈中，然后通过循环来...

    java 栈和队列的小例子

    在Java编程语言中，栈（Stack）和队列（Queue）是两种基本的数据结构，它们在处理数据存储和操作方面有着广泛的应用。本教程将通过一些小例子来深入理解这两种数据结构及其在Java中的实现。 栈是一种后进先出（LIFO...

    栈和队列的基本操作实现及其应用实验报告

    通过实践，掌握了栈和队列在数组和链表两种存储结构上的基本操作实现，并学会了如何利用这些数据结构来解决实际问题。此外，还意识到了程序测试的重要性，特别是在测试用例的选择上，应确保覆盖各种可能的情况，以...

    数据结构 Java实验4 栈和队列.doc

    通过这两个实验，我们不仅学会了如何用Java实现栈和队列这两种重要的数据结构，而且还掌握了如何将它们应用于解决实际问题。栈和队列的应用非常广泛，它们在计算机科学的各个领域中都扮演着重要的角色。例如，栈在...

    java实现数据结构

    下面将详细介绍Java中实现链表、栈、队列、优先级队列以及哈希表这些基本数据结构的方法。 首先，我们来看链表。链表是一种线性数据结构，其中的元素不连续存储，而是通过指针连接。Java中的`LinkedList`类实现了`...

    回文-栈和队列

    栈和队列的基本操作及其应用 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。...3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。 回文判断

    Java模拟栈和队列数据结构的基本示例讲解共4页.pdf

    本篇文档《Java模拟栈和队列数据结构的基本示例讲解共4页.pdf》将深入浅出地介绍如何在Java中实现栈和队列，以帮助开发者更好地理解和应用这些概念。 首先，让我们来了解栈和队列的基本特性： 1. **栈（Stack）**...

    Java版数据结构代码，栈，动态数组，队列，链表，二叉树

    在Java中，LinkedList类就是链表的实现，适用于实现队列和栈等数据结构。 5. **二叉树（Binary Tree）**：二叉树是每个节点最多有两个子节点的数据结构，分为左子节点和右子节点。常见的二叉树类型有二叉搜索树、...

Magicbox
Global site tag (gtag.js) - Google Analytics