数据结构*栈

栈

什么是栈

这里的栈与我们之前常说的栈是不同的。之前我们说的栈是内存栈，它是JVM内存的一部分，用于存储局部变量、方法调用信息等。每个线程都有自己独立的栈空间，当线程启动时，栈就会被创建；线程结束，栈也会被销毁。
而数据结构中的栈是一种抽象数据类型，描述的是一种存储数据的一种方法，遵循“先进后出”的原则，是一种线性的数据结构。

像上图所示就是一个栈，只能对于顶部完成操作，放元素放在最上面，当要拿栈中的元素也只能从最上面的元素开始获取。

官方栈

Stack类中的方法

方法	功能
Stack()	构造方法
E push(E e)	将e入栈
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size	获取栈中的有效元素个数
boolean empty()	栈中是否为空
int search(Object o)

代码展示：

public static void test1() {Stack<Integer> stack = new Stack<>();stack.push(10);stack.push(20);stack.push(30);stack.push(40);stack.pop();System.out.println(stack);//[10, 20, 30]System.out.println(stack.size());//3System.out.println(stack.peek());//30System.out.println(stack.empty());//falseSystem.out.println(stack.search(10));//3
}

代码解释：

1、对于search方法的返回：如果对象存在于栈中，会返回该对象到栈顶的距离（栈顶元素的距离为 1）；若对象不在栈中，则返回 -1。
2、由于Stack继承了Vector等其他类，也可以调用Vecto等其他类中的方法。

用数组自己实现一个栈

代码展示：

import java.util.Arrays;
public class MyStack<E> {private Object[] elem;private int useSize;public static final int DEFAULT_CAPACITY = 10;public MyStack() {elem = new Object[DEFAULT_CAPACITY];}/*** 完成入栈操作*/public void push(E data) {if(isFull()) {elem = Arrays.copyOf(elem,elem.length*2);}elem[useSize] = data;useSize++;}/*** 完成出栈操作，将栈顶的元素出栈并返回*/public E pop() {if(isEmpty()) {return null;}E ret = (E)elem[useSize - 1];useSize--;return ret;}/*** 返回栈顶的元素*/public E peek() {if(elem == null) {return null;}return (E)elem[useSize - 1];}/*** 栈中的元素个数* @return*/public int size() {return useSize;}private boolean isFull() {return elem.length == useSize;}public boolean isEmpty() {return useSize == 0;}public void display() {for (int i = 0; i < useSize; i++) {System.out.print(elem[i] + " ");}System.out.println();}
}

代码解释：

1、定义的 MyStack 类属于泛型类，也就是 MyStack<E>，E 代表元素的类型，不过在编译时具体类型是未知的。Java 并不允许创建泛型数组，也就是不能直接写 E[] elem = new E[DEFAULT_CAPACITY]; 。这是由于 Java 的泛型是通过类型擦除来实现的，在运行时泛型类型信息会被擦除，因此无法创建泛型数组。此时，借助 Object 数组，能够存储任意类型的对象。
2、Stack类底层使用数组实现的，当然我们也可以用链表实现Stack类。
3、 我们也可以使用链表的形式实现栈，在LinkedList类中也有push、pop、peek方法等方法。

栈的使用

1、用栈实现逆序打印链表

对于之前实现是通过递归的方法

public void printList(ListNode head) {ListNode cur = head;if(head != null) {printList(cur.next);System.out.print(cur.value + " ");}
}

通过递归回代的机制实现链表的逆序打印。
这也可以看成先进后出的。正序是从头开始打印，先将元素放在栈中，在开始取出元素，取出的元素对于链表来说就是逆序输出。

public void print(ListNode head) {ListNode cur = head;if(head == null) {return;}Stack<ListNode> stack = new Stack<>();//从头节点开始依次存入栈中while (cur != null) {stack.push(cur);cur = cur.next;}//开始取出元素，此时取出的是链表中最后的节点，因为它是最后放入栈中的while (!stack.empty()) {System.out.print(stack.pop().value + " ");}System.out.println();
}

2、逆波兰表达式

逆波兰表达式也叫后缀表达式。我们平常算数用的是中缀表达式(例如：1 + 2 = 3)。关于后缀表达式怎么从中缀表达式得来的，可以自行百度。下面是豆包给出来的运算方法。

代码展示：

public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(String string : tokens) {if(!isOperations(string)) {//是数字将其存入栈中stack.push(Integer.parseInt(string));}else {//是操作符，取出两个数字进行计算，将运算的数字在存入栈中int right = stack.pop();int left = stack.pop();switch (string){case "+" :stack.push(left + right);break;case "-" :stack.push(left - right);break;case "*" :stack.push(left * right);break;case "/" :stack.push(left / right);break;}}}//返回栈中最后一个元素了return stack.pop();
}
private boolean isOperations(String string) {return string.equals("+") || string.equals("-") || string.equals("*") || string.equals("/");
}

3、栈的压入与弹出序列

代码展示：

public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;for (int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while (!stack.empty() && j < popV.length && stack.peek() == popV[j]){stack.pop();j++;}}return stack.empty();
}

代码解释：

for循环是将pushV数组中的元素依次放在栈中。while循环是按照popV数组取出来的，当栈顶上的元素等于popV中的第一个元素，就从栈中取出，popV往后走。为什么判断条件要有!stack.empty()？是因为防止stack.peek()为空指针异常。

4、最小栈

代码展示：

class MinStack {Stack<Integer> stack;Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if(minStack.empty()) {minStack.push(val);}else {if(val <= minStack.peek()) {minStack.push(val);}}}public void pop() {int popVal = stack.pop();if(popVal == minStack.peek()) {minStack.pop();}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}

代码解释：

1、在push()方法中将小的之push到minStack栈中。此时需要注意的是，当有两个紧挨一样的最小值，它们都需要push到minStack栈中，因为当stack栈中pop了这个值，但最小值还是它。
2、在pop方法中if语句的判断条件需要注意。由于栈中存储的是Integer类对象，比较时不能直接用等号（stack.pop() == minStack.peek()像这样是错的）。可以定义int类型的临时变量，在比较的时候Integer类型的会自动拆箱。（在push方法中if语句比较也是一样的）