Stack是Java中常用的数据结构之一,Stack具有"后进先出(LIFO)"的性质。 只能在一端进行插入或者删除,即压栈与出栈
栈的实现比较简单,性质也简单。可以用一个数组来实现栈结构。
- 入栈的时候,只在数组尾部插入
- 出栈的时候,只在数组尾部删除**
我们来看一下Stack的用法 :如下
public static void main(String[] args){
//新建一个栈
Stack<String> stack = new Stack<>();
//分别向栈中添加不同的元素
stack.push("tom");
stack.push("jim");
stack.push("wendy");
stack.push("natasha");
//分别弹栈
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
输出如下:
natasha
wendy
jim
tom
从输出可以看到,最后入栈的,最先出栈
下面我们底层用数组也来实现这样一个栈,在数组的尾部插入和删除。 也就是入栈和出栈。如下图:
完整的源码如下:
public class QStack<E> {
//数组的默认大小为10
private static final int DEFAULT_INIT_CAPACITY = 10;
//底层的数组
private Object[] elements;
//栈中的个数
private int size;
public QStack() {
this(DEFAULT_INIT_CAPACITY);
}
public QStack(int capacity) {
//capacity条件检查 ,这里我们直接抛出异常
if (capacity <= 0) {
throw new IllegalArgumentException("capacity <= 0");
}
if (capacity > Integer.MAX_VALUE) {
throw new IllegalArgumentException("capacity > Integer.MAX_VALUE");
}
//新建一个capacity大小的数组
elements = new Object[capacity];
//初始个数为0
size = 0;
}
//栈是否为空
public boolean isEmpty() {
return size == 0;
}
//返回栈中的元素个数
public int size() {
return size;
}
//将一个元素压入栈中
public E push(E e) {
//如果栈已满,进行扩容
if (size >= elements.length) {
grow();
}
//扩容完后将元素e压入栈中
elements[size] = e;
//别忘了size需要加 1
size++;
return e;
}
//出栈,就是将数组最后一个元素弹出
public E pop() {
//如果栈为空就返回null
if (isEmpty()) {
return null;
}
//拿到栈的大小
int len = size();
//把数组中最后一个元素保存起来
E e = peek();
//个数别忘了减1
size--;
//将最后一个元素置null
elements[len - 1] = null;
//返回e
return e;
}
//返回最后一个元素
public E peek() {
int len = size();
if (len == 0)
throw new RuntimeException("stack is empty");
return (E) elements[len - 1];
}
//扩容
private void grow() {
//将之前的数组保存
int oldCapacity = elements.length;
Object[] old = elements;
//新的数组大小为原来数组大小的2倍
int newCapacity = oldCapacity * 2;
//再新建一个大小为原来数组2倍的新数组
elements = new Object[newCapacity];
//把以前的老的数组中的元素都移动新数组中
for (int i = 0; i < oldCapacity; i++) {
elements[i] = old[i];
}
//释放以前的内存空间
old = null;
}
}
以上面可知:用数组实现栈结构,主要需要注意以下 2 点:
- 在数组的尾部插入和删除,也就是压栈和弹栈
- 由于是用数组实现栈结构,数组满的时候,需要扩容
下面我们写一段测试代码来测试,如下:
public static void main(String[] args){
//创建一个栈
QStack<String> stack = new QStack<>();
//分别向栈中压入4个不同的元素
stack.push("tom");
stack.push("jim");
stack.push("wendy");
stack.push("natasha");
//分别弹栈
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
打印如下:
natasha
wendy
jim
tom