深入理解Java 栈数据结构
2018-11-22 08:42:29来源:博客园 阅读 ()
栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
从上图是基于数组实现的栈,可以看到,对栈的操作(压栈、出栈)其实都是对栈顶元素的操作,因此压栈和出栈的速度都比较快。栈中元素按照FILO顺序排序的,即先入后出的规则,先放进去的元素最后才能被弹出来。
一、栈结构要素
1、栈,是用来存储数据的数据结构,可以使用数组或链表来实现栈结构
2、栈顶,顾名思义栈最顶部的元素,压栈与出栈的对象
3、栈深度,栈中数据多少,如果栈结构为数组,当栈长度大于等于数组长度后,会抛出异常或对数组进行扩容,栈结构是链表就没有这个限制。
//存放数据 private Object[] data; //数据量 private int size; //栈顶 private int top; //默认栈大小 private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量 private int maxCapacity;
二、压栈
/** * 向栈中放数据 * @param obj * @return */ public boolean push(Object obj){ if (size >= maxCapacity) return false; data[++top] = obj; size++; return true; }
压栈操作比较简单,将新元素放在原栈顶的上面,栈顶指针往上移动一位。我这里当栈深度等于数组长度后是直接返回false的,当然根据实际的需求,你也可以对现有数组进行扩容,然后将原栈中元素放入新栈中即可。如:
/** * 压栈,如果栈深度超出数组长度,将数组扩大1.5倍 * @param obj * @return */ public boolean push1(Object obj){ if (size >= maxCapacity){ maxCapacity = maxCapacity * 3 / 2; Object[] newStack = new Object[maxCapacity]; System.arraycopy(data,0,newStack,0,size); Arrays.fill(data,null); data = newStack; } data[++top] = obj; size++; return true; }
三、出栈
/** * 从栈中弹出数据 * @return */ public Object pop(){ if (size <= 0) return null; size--; Object old = data[top]; data[top--] = null; return old; }
出栈操作将栈顶元素掷为null,然后将栈顶指针往下移动一位即可,很简单。
四、查看栈顶
/** * 查看数据 */ public Object peek(){ if (isEmpty()) return null; return data[top]; }
这个方法更是简单到令人发指,只是查看栈顶元素,并没有将栈顶元素删除。
五、清空栈
/** * 清空栈数据 */ public void clear(){ while (top > -1){ data[top--] = null; } size = 0; }
栈数据结构的实现基本已经讲完了,栈的基本操作差不多包包含在里面了,代码实现起来就是这么简单。另外,另一种基于链表的栈我就不再这里说了,因为也是很简单的,这是栈限定对链表的操作只能是操作链表头部,大家如果感兴趣的话可以自己尝试用链表实现一个栈,或者可以参考一下我之前写的基于链表实现的队列,原理是差不多的,也可以参考一下jdk中的LinkedList。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:6.并发编程--volatile
下一篇:采用位异或方式将两个变量数值调换
- 国外程序员整理的Java资源大全(全部是干货) 2020-06-12
- 2020年深圳中国平安各部门Java中级面试真题合集(附答案) 2020-06-11
- 2020年java就业前景 2020-06-11
- 04.Java基础语法 2020-06-11
- Java--反射(框架设计的灵魂)案例 2020-06-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash