常用的数据结构——栈

目录

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);}}

好了，如果本篇文章对你有所帮助，不要忘了点赞、收藏哦~