栈是重要的数据结构,从数据结构角度看,栈也是线性表,其特殊性在栈的基本操作是线性表的子集。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
分享到:
相关推荐
在Java中,`java.util.Stack`是内置的栈类,可用于实现这个功能。 6. **控制流**:源码中可能使用`if-else`语句或者`switch`语句来决定根据接收到的运算符执行哪种计算。 7. **面向对象编程**:为了使代码更易于...
例如,在Python中,我们可以定义一个`TreeNode`类来表示树的节点,然后创建一个`Stack`类或者直接使用内置的`list`来模拟栈的行为。 ```python class TreeNode: def __init__(self, value): self.value = value ...
本主题将深入探讨顺序栈的实现,包括C、C++和Java三种编程语言的源码分析。 首先,我们从C语言的角度来理解顺序栈。在C中,我们通常使用数组作为基础数据结构来实现顺序栈。以下是一个简单的顺序栈定义: ```c #...
3. **栈**(Stack):栈是一种后进先出(LIFO)的数据结构,Java中的java.util.Stack类提供了push、pop、peek等方法来实现栈的操作。栈在递归、回溯算法和表达式求解等方面有广泛应用。 4. **队列**(Queue):队列...
### 顺序栈入栈出栈实现源码解析 #### 一、基础知识介绍 ...这种实现方式简洁明了,易于理解和实现,适用于处理固定大小的数据集合。同时,代码还提供了简单的用户交互界面,使得用户能够直观地控制栈的操作流程。
`Stack`类实现了后进先出(LIFO)的栈数据结构,而`Queue`接口及其实现类如`ArrayDeque`则提供了先进先出(FIFO)的队列操作。 `Properties`类用于处理属性文件,常用于配置文件的读取和写入。 `Iterator`和`...
【Java实现蜘蛛纸牌小游戏源码】是一个基于Java编程语言开发的项目,旨在复现Windows操作系统中的经典小游戏——蜘蛛纸牌。在这个项目中,开发者利用Java的面向对象特性、图形用户界面(GUI)以及事件处理机制,构建...
Java中的`java.util.Stack`类提供了栈的操作。 4. **队列**:队列是一种先进先出(FIFO)的数据结构,广泛应用于任务调度和消息传递。Java中的`java.util.Queue`接口和其实现如`LinkedList`或`ArrayDeque`可以用来...
3. **Stack**: 这个类可能是对Java内置数据结构栈(Stack)的自定义实现,用于处理计算过程中的进栈和出栈操作,如存储括号内的运算符或中间计算结果。 4. **Compute**: 这个类很可能是计算器的核心逻辑部分,它...
Java.util.Stack和Java.util.Queue接口提供了实现这些数据结构的方法。 4. **集合框架**:Java集合框架包括ArrayList、LinkedList、HashSet、HashMap等,它们提供了丰富的操作和数据管理功能。理解这些类和接口的...
1. **Java技术栈**:Java电子商务源码通常采用Spring Boot框架作为基础,它简化了配置并提供了微服务架构的支持。Spring MVC处理HTTP请求,而Spring Data JPA则用于数据库交互。除此之外,MyBatis或Hibernate也可能...
源码会展示如何设计和实现这些算法。 这些源码实例可以帮助Java开发者深入理解数据结构和算法,提高编程效率,并为解决实际问题打下坚实的基础。通过分析和实践这些代码,我们可以更好地掌握数据结构与算法的精髓,...
本文将深入探讨四个基本数据结构的C++实现:模板线性表、链表、队列和栈。这些数据结构在软件开发中扮演着至关重要的角色,它们提供了多种处理数据的方法,使得算法设计和程序优化变得更加灵活。 1. **模板线性表**...
Java的Stack类实现了栈的功能,源码分析能帮助理解push、pop等操作的实现。 4. **队列**:队列是一种先进先出(FIFO)的数据结构,适用于处理任务队列和事件驱动系统。Java的ArrayDeque类可以作为队列使用,查看其...
【Java版网络聊天源码详解】 Java作为一种广泛应用于软件开发的多平台...在学习过程中,遇到问题时,不要忘了查阅Java API文档,以及利用网络资源如Stack Overflow等获取帮助,不断探索和实践,提升自己的编程技能。
它涵盖了二维数组、图遍历(DFS和BFS)、状态标记、队列和栈、递归、以及图形界面设计等多个核心编程概念,是学习和巩固Java编程能力的好例子。通过这个实验,学习者不仅可以深化对数据结构和算法的理解,还能提升...
`MyStack.java`可能是实现自定义栈类的源码,它可能包含以下方法: 1. `push(E element)`:将元素压入栈顶。 2. `pop()`:移除并返回栈顶元素,如果栈为空则抛出异常。 3. `peek()`:查看但不移除栈顶元素,如果栈为...
具体到这个Java计算器源码,开发者可能使用了Stack类(Java的内置数据结构类)来实现堆栈操作。Stack类继承自Vector类,提供了push()方法将元素压入栈顶,pop()方法将栈顶元素移除并返回,peek()方法查看栈顶元素但...
Java中的`Stack`类是基于数组的栈实现,而`Queue`接口则由多种实现,如`ArrayDeque`和`LinkedList`。 4. **集合框架**:Java集合框架包括接口如`List`, `Set`, `Map`,以及它们的实现,如`ArrayList`, `HashSet`, `...
Java中,Stack类继承自Vector类,提供栈功能。 4. **队列**:队列是一种先进先出(FIFO)的数据结构。Java中,Queue接口定义了队列操作,如enqueue(add)、dequeue(remove)等。LinkedList可以作为队列实现,另外...