使用一个数组实现两个栈
[!Tip]
本节源代码见Github链接🔗
问题描述
如何使用一个数组实现两个栈？并且保证只要数组中还有剩余空间，栈操作就不能提示异常。
核心思路
- 初始化两个栈的top下标变量分别指向数组的左右两端
- 左边的下标表示第一个栈的top元素，右边的下标表示第二个栈的top元素
- 如果需要对第一个栈进行元素入栈操作，那么将元素赋值到左边下标变量指示的位置
- 如果需要对第二个栈进行元素入栈操作，那么将元素赋值到右边下标变量指示的位置
- 第一个栈向右增长，第二个栈向左增长
实现代码
【👉🏻>>点击展开查看代码】
/**
* 一个数组实现两个栈
*
* @className: ArrayWithTwoStacks
* @author: Max Solider
* @date: 2023-06-09 07:42
*/public class ArrayWithTwoStacks {
private Integer[] dataArray;
private int topOne;
private int topTwo;
private int size;
public ArrayWithTwoStacks(int size) {
if (size < 2) {
throw new IllegalStateException("size < 2 is no persmissible");
}
dataArray = new Integer[size];
this.size = size;
topOne = -1;
topTwo = size;
}
public void push(int stackId, int data) {
if (topOne + 1 == topTwo) {
throw new StackOverflowError("Array is full");
}
if (stackId == 1) {
dataArray[++topOne] = data;
} else if (stackId == 2){
dataArray[++topTwo] = data;
}
return;
}
public Integer pop(int stackId) {
if (stackId == 1) {
if (topOne == -1) {
throw new EmptyStackException();
}
int data = dataArray[topOne];
dataArray[topOne--] = null;
return data;
} else if (stackId == 2) {
if (topTwo == size) {
throw new EmptyStackException();
}
int data = dataArray[topTwo];
dataArray[topTwo++] = null;
return data;
}
return null;
}
}
时间复杂度
时间复杂度为O(1)。
空间复杂度
空间复杂度为O(1)，用于存储临时变量。