栈
2020-06-12 本文已影响0人
不服输的小蜗牛
什么是栈?
栈是一种线性数据结构,只能在栈顶操作元素,先进后出,或者说是后进先出。
添加数据被称为入栈,删除数据被称为出栈。
栈的底层可以是动态数组,也可以通过链表。
通过上一篇的动态数组我们来实现一个栈。
由于数组在末尾添加元素和删除元素的时间复杂度都是O(1)的,所以我们只操作数组尾部来实现栈,入栈就是向数组尾部添加元素,出栈就是删除数组尾部元素,peek就是获取数组尾部的元素。
public class ArrayStack<E> {
private Array<E> array;
public ArrayStack() {
array = new Array<>();
}
public void push(E e){
array.addLast(e);
}
public E pop(){
return array.deleteLast();
}
public E peek(){
return array.getLast();
}
public int getSize() {
return array.getSize();
}
public boolean isEmpty(){
return array.isEmpty();
}
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append(String.format("array size :%s \n", array.getSize()));
stringBuffer.append("[");
for (int i = 0; i < array.getSize(); i++) {
if (i != array.getSize() - 1) {
stringBuffer.append(array.get(i) + ",");
} else {
stringBuffer.append(array.get(i));
}
}
stringBuffer.append("]top");
return stringBuffer.toString();
}
}