这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和
java
集合有个大概的了解。当然实现没有java
集合的实现那么复杂,功能也没有那么强大,但是可以通过这些简单的实现窥探到底层的一些共性原理。
一. 什么是栈?
栈是一种特殊的线性表,还有另外一种特殊的线性表是队列,后面我们会讲到。栈的特殊之处是其插入和删除操作只允许在线性表的一端进行。允许操作的一端叫做栈顶(top
),不允许操作的一端叫做栈底(bottom
),往栈中插入元素的操作称作入栈,往栈中删除元素的操作叫做出栈。栈的数据模型如下所示(图片来源于网络):
由于对栈的操作只允许在栈顶进行,所以每次入栈的元素就成为新的栈顶元素,每次出栈的元素都是当前最后一个入栈的元素,一句话总结就是后来的先走,就像生活中我们叠盘子,每次都是把盘子放在最上面,取盘子的时候也总是从最上面取,所以栈也被叫做后进先出(Last
In
First
Out
)表。
二. 栈接口的定义
栈的基本操作有下面几个:
1. 创建栈
2. 判断是否为空栈(没有元素的栈称作空栈)
3. 入栈
4. 出栈
5. 取栈顶元素值等
所以栈的接口定义如下:
package org.light4j.dataStructure.linearList.stack;
/**
* 栈接口
*
* @author longjiazuo
*/
public interface SStack<E> {
/**
* 判断栈是否为空,若为空则返回true
*
* @return
*/
boolean isEmpty();
/**
* element元素入栈,若操作成功返回true
*
* @param element
* @return
*/
boolean push(E element);
/**
* 出栈,返回当前栈顶元素,若栈空返回null
*
* @return
*/
E pop();
/**
* 取栈顶元素值,未出栈,若栈空返回null
*
* @return
*/
E get();
}
栈的实现有顺序栈和链式栈,可以点击下文查看:
自己实现集合框架(十):顺序栈的实现
自己实现集合框架(十一):链式栈的实现
三.源代码示例
公众号ID:longjiazuoA

未经允许不得转载:人生设计师 » 自己实现集合框架(九):栈接口