常用的数据结构——栈
目录
1、入栈
2、出栈
3、获取栈顶的元素
4、从栈中查找元素
栈是一种常见的数据结构，栈的特点是后进先出，就像我们叠盘子，拿走上面的盘子才能拿到下一个。java中的栈java.util.Stack是通过java.util.Vector实现的，所以底层都是数组，并且是线程安全的。
接下来，我们通过数组来实现一个简单的栈
首先，栈Stack中应该有以下几个方法：
- 入栈（压栈）：push()
- 出栈：pop()
- 取栈顶元素：peek()
- 从栈中查找某个元素：search()
首先我们先描绘一下栈的基本结构，使用一个数组保存栈中所有对象，还要保存数组的长度。
package stack;import java.util.Arrays;/*** @author heyunlin* @version 1.0*/
public class Stack<E> {private E[] data;private int length;public Stack() {}public boolean isEmpty() {return data == null || data.length == 0;}@Overridepublic String toString() {return Arrays.toString(data);}}1、入栈
入栈就是把元素放到栈中，然后要让栈的长度+1，初始时栈为空，需要实例化。
但是这个过程中，遇到一点问题，因为栈的元素类型E需要运行时才能确定，不能直接通过new E[]的方式实例化。这时候想到：所有自定义的类都默认继承自我们的顶级超类java.lang.Object，那就可以创建一个Object类型的空数组，再强转成E[]类型，这样就相当于创建了一个E类型的空数组。实现的代码如下
public synchronized E push(E e) {if (isEmpty()) {Object[] array = new Object[1];data = (E[]) array;data[0] = e;length = 1;} else {length ++;// 数组扩容data = Arrays.copyOf(data, length);// 把元素放到数组最后一个下标的位置data[length - 1] = e;}return data[length - 1];
}
2、出栈
出栈，就是删除并返回栈顶的元素
这个比较简单，直接贴上代码
public synchronized E pop() {if (isEmpty()) {throw new RuntimeException("出栈失败，当前栈为空~");}// 取栈顶元素E top = data[length - 1];length --;// 数组长度减1data = Arrays.copyOf(data, length);return top;
}
3、获取栈顶的元素
这个方法最简单，直接获取数组中最后一个元素就行了
public E peek() {if (isEmpty()) {throw new RuntimeException("获取栈顶元素失败，当前栈为空~");}return data[length - 1];
}
4、从栈中查找元素的位置
使用该方法前，请确保E.java中重写了equals()方法
public int search(E target) {int index = -1;for (int i = 0; i < data.length; i++) {if (data[i] == target) {index = i;}}return index;
}
最后，贴上完整的代码
package stack;import java.util.Arrays;/*** @author heyunlin* @version 1.0*/
public class Stack<E> {private E[] data;private int length;public Stack() {}/*** 入栈/压栈* @param e E* @return E*/public synchronized E push(E e) {if (isEmpty()) {Object[] array = new Object[1];data = (E[]) array;data[0] = e;length = 1;} else {length++;// 数组扩容data = Arrays.copyOf(data, length);// 把元素放到数组最后一个下标的位置data[length - 1] = e;}return data[length - 1];}/*** 出栈* @return E*/public synchronized E pop() {E top = peek();length --;data = Arrays.copyOf(data, length);return top;}/*** 取栈顶元素* @return E*/public E peek() {if (isEmpty()) {throw new RuntimeException("获取栈顶元素失败，当前栈为空~");}return data[length - 1];}public boolean isEmpty() {return data == null || data.length == 0;}/*** 查找对象在栈中的位置* @param target E* @return int*/public int search(E target) {int index = -1;for (int i = 0; i < data.length; i++) {E element = data[i];if (target == null && element == null || element.equals(target)) {index = i;}}return index;}@Overridepublic String toString() {return Arrays.toString(data);}}最后，我们新建一个demo来测试一下刚刚写的Stack
package stack;/*** @author heyunlin* @version 1.0*/
public class StackExample {public static void main(String[] args) {Stack<String> stack = new Stack<>();stack.push("a");stack.push("b");stack.push("c");stack.push("d");stack.push("e");System.out.println(stack.push("f"));System.out.println(stack);String pop = stack.pop();System.out.println(pop);System.out.println(stack);}}好了，如果本篇文章对你有所帮助，不要忘了点赞、收藏哦~