`

栈和Java基础类的Stack类的源码实现,缺陷以及如何实现自己的Stack类

阅读更多

栈是重要的数据结构,从数据结构角度看,栈也是线性表,其特殊性在栈的基本操作是线性表的子集。Stack作为最基本的数据结构,在JDK代码中,也有它的实现,java.util.Stack类是继承了Vector类,来实现了栈的基本功能。

 

1.栈的基本原理

 

栈(Stack)是限定仅在表尾进行插入或者删除操作的线性表。因此,对于栈来说,表尾端有特殊含义,成为栈顶,表头称之为栈底。

 

由下图可以看出,栈的最基本的特征是LIFO(Last In First Out),因此栈又被称为后进先出 的线性表。

 

2.栈的基本操作

 

InitStack(&S)--------------构造一个空栈

IsEmpty:判断栈是否为空

ClearStack:清空栈

StackLength:栈S的元素个数,即栈的长度

GetTop:获取栈顶元素

Push:插入新的元素

Pop:删除栈顶元素

 

3.java.util.Stack源码解析

 

1)数据结构:利用Vector(动态数组)完成后进先出的操作

2)基本方法:

 

     //初始化一个长度为10 的数组

     构造器      public Stack():

 

    //放入新元素到栈顶

     public E push(E item){

           //按序更新数组元素(计数器判断最后更新数组元素的索引)

           addElement(item);

           return item;

    }

 

    /**

   *1.如果由于新增的元素导致数组的长度不够,则把原来的数组尺寸翻倍,并拷贝老数组元素到新的数组

   *2.

   *

   *

   */

   public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
    }

 

 

//pop栈顶元素

 public synchronized E pop() {
    E    obj;
    int    len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
    }

 

4.java.util.stack的缺点

上述源码分析我们知道,Stack利用Vector动态数组实现了后进先出的栈的基本功能,但是数组有下列缺陷:

 

1)当数组默认的容量发生改变时,push的性能会有较大降低


5.实现自己的Stack类

 

数组的缺点是,当数组长度发生变化时,原有的元素需要经过copy到新的数组中,这样性能有较大的损耗,而链表最大的优点是插入和删除的性能非常好,Java提供了现成的双向链表类java.util.LinkedList,通过它可以快速编写自己的Stack程序,源码如下:

 

public class Stack<E>{
    LinkedList<E> list;
   
    public Stack(){
        list = new LinkedList();
    }
   
    public E pop(){
        return list.removeLast();
    }
   
    public void push(E o){
        list.add(o);
    }
   
    public E getTop(){
        return list.getLast();
    }
   
    public boolean isEmpty(){
        return list.size()==0;
    }
   
    public int size(){
        return list.size();
    }
   
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push("bottom");
        stack.push("middle");
        stack.push("top");
        System.out.println(stack.isEmpty());
        System.out.println(stack.getTop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
    }
   
}

 

 

 

 

  • 大小: 35.6 KB
2
0
分享到:
评论

相关推荐

    Java-计算器源码.zip

    在Java中,`java.util.Stack`是内置的栈类,可用于实现这个功能。 6. **控制流**:源码中可能使用`if-else`语句或者`switch`语句来决定根据接收到的运算符执行哪种计算。 7. **面向对象编程**:为了使代码更易于...

    用栈(stack)实现树形菜单

    例如,在Python中,我们可以定义一个`TreeNode`类来表示树的节点,然后创建一个`Stack`类或者直接使用内置的`list`来模拟栈的行为。 ```python class TreeNode: def __init__(self, value): self.value = value ...

    顺序栈实现源码(C、C++、Java)

    本主题将深入探讨顺序栈的实现,包括C、C++和Java三种编程语言的源码分析。 首先,我们从C语言的角度来理解顺序栈。在C中,我们通常使用数组作为基础数据结构来实现顺序栈。以下是一个简单的顺序栈定义: ```c #...

    java数据结构源码

    3. **栈**(Stack):栈是一种后进先出(LIFO)的数据结构,Java中的java.util.Stack类提供了push、pop、peek等方法来实现栈的操作。栈在递归、回溯算法和表达式求解等方面有广泛应用。 4. **队列**(Queue):队列...

    顺序栈入栈出栈实现源码

    ### 顺序栈入栈出栈实现源码解析 #### 一、基础知识介绍 ...这种实现方式简洁明了,易于理解和实现,适用于处理固定大小的数据集合。同时,代码还提供了简单的用户交互界面,使得用户能够直观地控制栈的操作流程。

    java util 类

    `Stack`类实现了后进先出(LIFO)的栈数据结构,而`Queue`接口及其实现类如`ArrayDeque`则提供了先进先出(FIFO)的队列操作。 `Properties`类用于处理属性文件,常用于配置文件的读取和写入。 `Iterator`和`...

    Java实现蜘蛛纸牌小游戏源码.zip

    【Java实现蜘蛛纸牌小游戏源码】是一个基于Java编程语言开发的项目,旨在复现Windows操作系统中的经典小游戏——蜘蛛纸牌。在这个项目中,开发者利用Java的面向对象特性、图形用户界面(GUI)以及事件处理机制,构建...

    Java软件结构与数据结构源码

    Java中的`java.util.Stack`类提供了栈的操作。 4. **队列**:队列是一种先进先出(FIFO)的数据结构,广泛应用于任务调度和消息传递。Java中的`java.util.Queue`接口和其实现如`LinkedList`或`ArrayDeque`可以用来...

    java实现的计算器源码

    3. **Stack**: 这个类可能是对Java内置数据结构栈(Stack)的自定义实现,用于处理计算过程中的进栈和出栈操作,如存储括号内的运算符或中间计算结果。 4. **Compute**: 这个类很可能是计算器的核心逻辑部分,它...

    java数据结构和算法(第二版)[含源码]

    Java.util.Stack和Java.util.Queue接口提供了实现这些数据结构的方法。 4. **集合框架**:Java集合框架包括ArrayList、LinkedList、HashSet、HashMap等,它们提供了丰富的操作和数据管理功能。理解这些类和接口的...

    java 电子商务 源码

    1. **Java技术栈**:Java电子商务源码通常采用Spring Boot框架作为基础,它简化了配置并提供了微服务架构的支持。Spring MVC处理HTTP请求,而Spring Data JPA则用于数据库交互。除此之外,MyBatis或Hibernate也可能...

    JAVA数据结构与算法—源码

    源码会展示如何设计和实现这些算法。 这些源码实例可以帮助Java开发者深入理解数据结构和算法,提高编程效率,并为解决实际问题打下坚实的基础。通过分析和实践这些代码,我们可以更好地掌握数据结构与算法的精髓,...

    模板线性表,链表,队列,栈的实现(C++实现)

    本文将深入探讨四个基本数据结构的C++实现:模板线性表、链表、队列和栈。这些数据结构在软件开发中扮演着至关重要的角色,它们提供了多种处理数据的方法,使得算法设计和程序优化变得更加灵活。 1. **模板线性表**...

    java各个数据结构源码

    Java的Stack类实现了栈的功能,源码分析能帮助理解push、pop等操作的实现。 4. **队列**:队列是一种先进先出(FIFO)的数据结构,适用于处理任务队列和事件驱动系统。Java的ArrayDeque类可以作为队列使用,查看其...

    java版网络聊天源码

    【Java版网络聊天源码详解】 Java作为一种广泛应用于软件开发的多平台...在学习过程中,遇到问题时,不要忘了查阅Java API文档,以及利用网络资源如Stack Overflow等获取帮助,不断探索和实践,提升自己的编程技能。

    数据结构马踏棋盘JAVA实验源码

    它涵盖了二维数组、图遍历(DFS和BFS)、状态标记、队列和栈、递归、以及图形界面设计等多个核心编程概念,是学习和巩固Java编程能力的好例子。通过这个实验,学习者不仅可以深化对数据结构和算法的理解,还能提升...

    Stack检测括号匹配.zip

    `MyStack.java`可能是实现自定义栈类的源码,它可能包含以下方法: 1. `push(E element)`:将元素压入栈顶。 2. `pop()`:移除并返回栈顶元素,如果栈为空则抛出异常。 3. `peek()`:查看但不移除栈顶元素,如果栈为...

    Java计算器源码含界面(基于堆栈算法实现)

    具体到这个Java计算器源码,开发者可能使用了Stack类(Java的内置数据结构类)来实现堆栈操作。Stack类继承自Vector类,提供了push()方法将元素压入栈顶,pop()方法将栈顶元素移除并返回,peek()方法查看栈顶元素但...

    Java数据结构和算法源码

    Java中的`Stack`类是基于数组的栈实现,而`Queue`接口则由多种实现,如`ArrayDeque`和`LinkedList`。 4. **集合框架**:Java集合框架包括接口如`List`, `Set`, `Map`,以及它们的实现,如`ArrayList`, `HashSet`, `...

    java 数据结构以及源码

    Java中,Stack类继承自Vector类,提供栈功能。 4. **队列**:队列是一种先进先出(FIFO)的数据结构。Java中,Queue接口定义了队列操作,如enqueue(add)、dequeue(remove)等。LinkedList可以作为队列实现,另外...

Global site tag (gtag.js) - Google Analytics