什么是栈
栈又称为堆栈,是一种运算受限定表。说是限定表是由于对于元素的入栈和出栈都在表末尾进行,换言之就是先进后出,其本质就是对表尾部元素进行操作。在计算机系统中,栈是具有以上属性的动态内存区域。由于数据结构都是数组和指针的组合,故我们可以用JAVA数组来进行模拟。
算法原理
定义变量:TOP-栈顶指针 N-当前数组容器长度 S-数组 X-元素
1、入栈(PUSH)算法
1.1 首先判断指针 TOP +1 > N-1,满足则进行动态扩容后进入下一步,否则直接进入下一步
1.2 TOP++ 增加指针指向栈顶
1.3 S(TOP) = X 将元素赋值给栈顶索引
2、出栈(POP)算法
2.1 首先判断 TOP-1 < 0,满足抛出异常没有可出栈元素,否则进入下一步
2.2 X=S(TOP) 获取待出栈元素已备后续返回使用
2.3 S(TOP) = NULL,TOP– 置空栈顶元素,减少指针指向栈顶
小试牛刀
1、创建栈方法,并提供模拟动态扩容、出入栈、获取栈顶元素等方法
/**
* 数据结构-栈
* @author senfel
* @version 1.0
* @date 2022/11/24 11:01
*/
@Slf4j
public class Stack {
/**
* 栈数组
*/
private Object[] elementArray;
/**
* 栈顶指针
*/
private Integer top;
/**
* 栈深度
*/
private Integer deepness;
/**
* 默认栈深度为10的构造方法
*/
public Stack() {
this.elementArray = new Object[10];
this.top = -1;
this.deepness = 10;
}
/**
* 提供有个传入栈深度的构造方法
* @param deepness
*/
public Stack(Integer deepness) {
this.elementArray = new Object[deepness];
this.top = -1;
this.deepness = deepness;
}
/**
* 扩容方法
* 1、判断是否需要扩容
* 2、需要扩容则扩大两倍的量
* @param topIndex
* @author senfel
* @date 2022/11/24 11:08
* @return void
*/
public void grow(Integer topIndex){
//缓存当前栈深度
Integer currentDeepness = deepness;
//由于top为索引故栈顶深度 == index+ 1
if(topIndex + 1 > deepness){
//需要扩容并验证扩容后是否超过int取值范围
if(currentDeepness * 2 > Integer.MAX_VALUE){
deepness = Integer.MAX_VALUE;
}else{
deepness = currentDeepness * 2;
}
//对栈内元素重新分配索引
elementArray = Arrays.copyOf(elementArray, deepness);
}
}
/**
* 验证栈是否为空
* @author senfel
* @date 2022/11/24 11:23
* @return java.lang.Boolean
*/
public Boolean isEmpty(){
if(top > -1){
return false;
}else{
return true;
}
}
/**
* 入栈
* @param element
* @author senfel
* @date 2022/11/24 11:19
* @return void
*/
public void push(Object element){
//扩容并移动栈顶指针
grow(++top);
//元素压入栈顶
elementArray[top] = element;
}
/**
* 获取栈顶元素
* @author senfel
* @date 2022/11/24 11:21
* @return void
*/
public Object peek(){
if(isEmpty()){
return null;
}
return elementArray[top];
}
/**
* 弹出栈顶元素
* @author senfel
* @date 2022/11/24 11:24
* @return java.lang.Object
*/
public void pop(){
//获取栈顶元素
Object peek = peek();
if(Objects.isNull(peek)){
throw new EmptyStackException();
}
elementArray[top] = null;
top--;
}
}
2、提供测试方法
public static void main(String[] args) {
Stack stack = new Stack(8);
log.error("初始栈{}",Arrays.toString(stack.elementArray));
//当前栈是否为空
log.error("当前栈是否为空:{}",stack.isEmpty());
for(int i = 0;i< 10;i++){
stack.push(i);
}
log.error("入栈后的栈结构为{}",Arrays.toString(stack.elementArray));
log.error("当前栈顶元素为:{}",stack.peek());
//模拟出栈两次
stack.pop();
stack.pop();
log.error("出栈两次栈后的栈结构为{}",Arrays.toString(stack.elementArray));
log.error("当前栈顶元素为:{}",stack.peek());
}
3、展示测试结果
11:46:30.740 – 初始栈[null, null, null, null, null, null, null, null]
11:46:30.743 – 当前栈是否为空:true
11:46:30.743 – 入栈后的栈结构为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null, null, null, null, null, null]
11:46:30.743 – 当前栈顶元素为:9
11:46:30.743 – 出栈两次栈后的栈结构为[0, 1, 2, 3, 4, 5, 6, 7, null, null, null, null, null, null, null, null]
11:46:30.743 – 当前栈顶元素为:7
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/154667.html