用 Java 数组实现栈结构
最近在学数据结构这门课,不过数据结构这门课是用的 C 语言,而我主要学的是 Java,所以就用 Java 实现一下。栈结构是先进后出的数据结构,在算法中非常有用,以后也会写一些关于栈的算法题解。
- 首先写出栈的接口,定义栈的基本操作。
public interface IStack<T> {
/**
* 元素入栈
* @param e
*/
void push(T e);
/**
* 弹出栈顶
* @return
*/
T pop();
/**
* 是否空栈
*/
boolean empty();
/**
* 获得栈內元素个数
* @return
*/
int getSize();
/**
* 弹出栈顶元素
* @return
*/
T peek();
}
- 然后定义一个栈类实现这个接口,实现原理很简单,首先定义栈顶下标、栈底下标、置零。入栈从数组后面添加元素,栈顶下标 +1,出栈从数组后面取出元素栈顶下标-1,栈顶下标永远是要插入元素的下标,当栈顶下标和栈底下标相等时
表示空栈。
public class MyOrderStack<T> implements IStack {
private T[] elements;
private int capacity = 10;
//栈底下标
private int base =0;
//栈顶下标
private int top = 0;
private int size = 0;
public MyOrderStack(int capacity){
this.capacity = capacity;
this.elements = (T[]) new Object [capacity];
}
public MyOrderStack(){
this.elements = (T[]) new Object [capacity];
}
@Override
public void push(Object e) {
//判断数组是否已满
if (top==capacity){
//建立一个是原来空间二倍的数组
capacity = capacity *2;
T[] temp = (T[]) new Object[capacity];
for (int i = 0; i <elements.length ; i++) {
//将原来数组元素挪进新数组
temp [i] = elements [i];
}
elements = temp;
}
elements [top++] = (T) e;
size++;
}
@Override
public Object pop() {
if (top == base){
throw new RuntimeException("栈空");
}
size--;
return elements [--top];
}
@Override
public boolean empty() {
return top == base;
}
@Override
public int getSize() {
return size;
}
@Override
public Object peek() {
return elements [top-1];
}
}
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于