明白一个概念:
栈:是一种特殊的数据结构,特数性在于:栈本身是数组或者链表,常用的是数组
特点:
LIFO:后进先出
生活场景:叠加盘子,取盘子
2.栈在函数中的调用
package com.redis.algorithm.stack; /** * 栈:一种特殊的数据结构,是数组或者链表 * * @param <Item> */
package com.redis.algorithm.stack;
public interface MyStack<Item> {
MyStack<Item> push(Item item); //入栈
Item pop(); //出栈
int size();
boolean isEmpty();
}
public class ArrayStack<Item> implements MyStack<Item> {
private Item[] a = (Item[]) new Object[1]; //
private int n = 0; //初始的元素个数
public ArrayStack(int cap) {
a = (Item[]) new Object[cap]; //初始化的时候,指定大小,这样就不需要扩容
}
@Override
public MyStack<Item> push(Item item) {
judgeSize(); //判断容量,是不是需要扩容
a[n++] = item; //向数组中添加元素
return null;
}
private void judgeSize() {
if (n <= a.length) { //元素的个数已经超出了数组的容量,进行扩容
resize(2 * a.length);
} else if (n > 0 && n <= a.length / 2) {
resize(a.length / 2); //动态缩容
}
}
private void resize(int size) {
//扩容:建立一个临时的变量进行扩容,数的赋值关系
Item[] temp = (Item[]) new Object[size];
for (int i = 0; i < n; i++) {
temp[i] = a[i];
}
a = temp;
}
@Override
public Item pop() { //出栈
if (isEmpty()) {
return null;
}
Item item = a[--n]; //--n 把n减了在用,n--用了在减
a[n] = null;
return item; //默认值为null
}
@Override
public int size() {
return n; //默认值为0
}
@Override
public boolean isEmpty() {
return n == 0; //默认值为false
}
}