Java中是没有栈这种数据结构的,如果想利用栈的先进后出(FILO),就必须自己动手实现。栈的底层可以使用数组,也可以使用Java中的容器类,如ArrayList、LinkList等。栈最常用的操作主要是压栈(push)、出栈(pop)、查看栈顶元素(peek)、判断栈是否为空(isEmpty)、返回栈的当前大小。原则上栈中有一个指针指向栈顶元素。
1、底层基于数组的栈实现:
import java.util.EmptyStackException;
public class MyStack {
private int[] arr; //底层数组
private int top; //相当于栈顶指针
/**
* 无参构造方法,默认初始容量为10个整形数据大小
*/
public MyStack(){
arr = new int[10];
top = -1;
}
/**
* 含参构造方法,构造指定大小的底层数组
* @param size
*/
public MyStack(int size){
arr = new int[size];
top =-1;
}
/**
* 判断栈是否为空
* @return
*/
public boolean isEmpty(){
return top == -1;
}
/**
* 压栈操作
* @param element
*/
public void push(int element){
if(top == arr.length-1)throw new StackOverflowError();
else arr[++top] = element;
}
/**
* 出栈操作
* @return
*/
public int pop(){
if(top == -1)throw new EmptyStackException();
else return arr[top--];
}
/**
* 查看栈顶元素
* @return
*/
public int peek(){
if(top == -1)throw new EmptyStackException();
else return arr[top];
}
}
2、底层基于容器的栈的实现:
注:使用ArrayList容器作为底层来实现栈,就必须知道ArrayList的一些特性,ArrayList是基于数组实现的,默认初始容量是10,当容量不足的时候,是会自动以1.5倍扩容,所以无需担心越界的问题,ArrayList提供的一些方法会对我们实现栈有帮助。因此,下面就无需再使用栈顶指针,ArrayList中有一个随内容数量变化的size可作为指针。
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;
public class MyCollectionStack<E extends Object>{
private List<E> list = new ArrayList<E>(); //底层基于ArrayList的容器
public MyCollectionStack(){
}
public boolean isEmpty(){
return list.isEmpty();
}
public void push(E e){
list.add(e);
}
public E pop(){
if(list.isEmpty()) throw new EmptyStackException();
else return list.remove(list.size()-1);
}
public E peek(){
if(list.isEmpty()) throw new EmptyStackException();
else return list.get(list.size()-1);
}
}
分享到:
相关推荐
Java语言编写的数据结构-栈的实现,包括顺序栈和链栈。
数据结构和算法分析(java)实现中第三章知识点的总结,主要讲的是表。栈、队列的原理和实现,以及应用。一共17页。
java基础笔记数据结构-栈,详细描述了栈的原理及其实现方式,基础数据结构。
包含JWArray和JWList,分别包含顺序结构及链式结构的线性表、栈和队列操作,函数使用方便简单,可以作为简单的C语言线性表、栈和队列操作库。
《计算机科学丛书·数据结构从应用到实现(Java版)》系统地介绍了数据结构以及数据结构与对象之间的联系。主要内容包括:算法效率的输入规模、阶和大O,数据结构的无序和有序列表,队列和栈基于数组和链表的设计实例...
数据结构的定义 数据结构是计算机存储、组织数据的方式,用于高效地访问和修改数据。...Java提供了丰富的数据结构库,包括数组、链表、栈、队列等,这些数据结构为程序员提供了处理各种问题的工具和方法。
数据结构(Java)实践作业迷宫参考书本使用栈结构实现的
Java-用数组实现栈-队列-线性列表(最详细) 有注释 适合java新生 进行数组的练习 3个数据结构的数组实现练习
数据结构 第3章 栈和队列(课后习题程序实现).rar 数据结构 第3章 栈和队列(课后习题程序实现).rar 数据结构 第3章 栈和队列(课后习题程序实现).rar 数据结构 第3章 栈和队列(课后习题程序实现).rar
包含链表、 栈、 队列、优先级队列、哈希表,绝对原创总结!
包含了各种数据结构和算法(java)的实现方式和详解(图解),包括单双链表、环形链表(约瑟夫问题)、栈、后缀表达式、中缀表达式转后缀表达式、迷宫问题、八大排序算法、多种查找算法、哈希表、二叉树实现以及操作...
主要介绍了java数据结构实现栈,需要的朋友可以参考下
数据结构与算法----线性表及Java实现顺序表、链表、栈、队列 定义线性表节点的结构.pdf
简单的介绍了队列的实现原理,和一些开发中的考量
“计算中缀表达式”可以称得上是一个特别经典的关于栈的算法题,几乎在所有数据结构教材中都会涉及,而且很多公司面试或者笔试的时候都会把这道题作为一个考察点。可以说,这是一道必须要掌握的算法题。中缀表达式、...
主要介绍了Java数据结构之栈的基本定义与实现方法,简单描述了数据结构中栈的功能、原理,并结合java实例形式分析了栈的基本定义与使用方法,需要的朋友可以参考下
包含数据结构常用的知识:顺序表(数组实现和链表)、栈和队列的顺序实现和链式实现,二叉树的实现和遍历、常用的排序算法
基于c语言数据结构中栈和队列思想的简单停车场管理系统,以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车...
主要介绍了Java数据结构之链表、栈、队列、树的实现方法,结合实例形式分析了Java数据结构中链表、栈、队列、树的功能、定义及使用方法,需要的朋友可以参考下