数据结构(Java版)第十期：栈和队列(一)
专栏：数据结构(Java版)
个人主页：手握风云
目录
一、栈
1.1. 栈的概念
栈是⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作 的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。
入栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
1.2. 栈的使用
import java.util.Stack; public class Main { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); } }我们点进去看一下Stack的源码：
public class Stack<E> extends Vector<E> { public Stack() { } public E push(E item) { addElement(item); return item; }下面是一些Stack的方法，我们来实现一下。
| 方法 | 功能 |
| Stack() | 创建一个空的栈 |
| E push(E e) | 将e入栈并返回e |
| E pop() | 将栈顶元素出栈并返回 |
| E peek() | 获取栈顶元素 |
| int size() | 获取栈中有效元素的个数 |
| boolean empty() | 检查栈是否为空 |
import java.util.Stack; public class Main { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); System.out.println(stack.empty());//检查栈是否为空 stack.push(5);//入栈 stack.push(4); stack.push(3); stack.push(2); stack.push(1); System.out.println(stack.size());//获取栈的元素个数 System.out.println(stack); System.out.println(stack.empty()); System.out.println(stack.pop());//栈顶元素出栈 System.out.println(stack.peek());//获取栈顶元素 } }1.3. 栈的模拟实现
Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是 Vector是线程安全的，我们可以直接用数组来实现栈。
import java.util.Arrays; public class MyStack { private int[] elem; private int usedSize; private static final int DEFAULT = 10; public MyStack(){ elem = new int[DEFAULT]; } public void push(int val){//模拟入栈操作 if(isFull()){//如果满了就扩容 grow(); } elem[usedSize] = val; usedSize++; } private void grow(){ elem = Arrays.copyOf(elem,elem.length); } public boolean isFull(){//判断数组是否满了 return usedSize == elem.length; } public int pop() { if(isEmpty()){ throw new StackIsEmpty("栈为空"); } usedSize--;//相当于把数据置为null return elem[usedSize-1]; } public boolean isEmpty(){ return usedSize == 0; } public int peek() { if(isEmpty()){ throw new StackIsEmpty("栈为空"); } return elem[usedSize--]; } public int size(){ return usedSize; } }public class StackIsEmpty extends RuntimeException{ public StackIsEmpty() { super(); } public StackIsEmpty(String message) { super(message); } } public class Main { public static void main(String[] args) { MyStack stack = new MyStack(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack.size()); int num1 = stack.pop(); System.out.println(num1); int num2 = stack.peek(); System.out.println(num2); } } 二、栈的经典面试题
2.1. 逆波兰表达式
逆波兰表达式，又称为后缀表达式，特点是运算符位于操作数之后。例如((2+1)*3)、(4+(13/5))是中缀表达式，转化为逆波兰表达式则为2 1 + 3 *、4 13 5 / +。
本题方法参数给出的是字符串数组，我们要先将字符转化为数字。先用引用去遍历数组，如果是数字，就放入栈中；如果引用指向的是运算符，则将栈顶的两个元素出栈进行运算。如此循环往复，直至遍历完整个字符串数组。
import java.util.Stack; public class Solution { public int evalRPN(String[] tokens){ Stack<Integer> stack = new Stack<>(); int len = tokens.length; for (int i = 0; i < len; i++) {//遍历字符串数组 String str = tokens[i]; if(!isOperator(str)){ Integer num = Integer.valueOf(str);//将字符转化为数字 stack.push(num); }else{//如果是运算符，则栈顶两个元素出栈 Integer num1 = stack.pop(); Integer num2 = stack.pop(); switch (str){ case "+": stack.push(num2+num1); break; case"-": stack.push(num2-num1); break; case"*": stack.push(num2*num1); break; case"/": stack.push(num2/num1); break; } } } return stack.pop(); } private boolean isOperator(String val){//先判断字符串是数字还是运算符 if(val.equals("+") || val.equals("-") || val.equals("*") || val.equals("/")){ return true; } return false; } }2.2. 有效的括号
题目中要求字符串只有大、中、小括号，返回true的条件为：当我们遍历完字符串之后并且栈为空。如果说，当我们左右括号不匹配时，比如"([))"，就返回false；当我们遍历完字符串之后，如果栈不为空，也返回false，比如"(()"；当我们还没有遍历完字符串，栈已经为空，也会返回false，比如"({}))"。
import java.util.Stack; public class Solution { public boolean isValid(String s){ Stack<Character> stack = new Stack<>(); int len = s.length(); for (int i = 0; i < len; i++) { char ch1 = s.charAt(i); if(ch1 == '{' || ch1 == '[' || ch1 == '('){ stack.push(ch1);//将左括号入栈 }else{ if(stack.isEmpty()){ return false; } char ch2 = stack.peek();//获取入栈的左括号，与右括号进行匹配 if((ch2=='{'&&ch1=='}') || (ch2=='['&&ch1==']') || (ch2=='('&&ch1==')')){ stack.pop(); }else { return false; } } } if(!stack.isEmpty()){ return false; } return true; } }2.3. 最小栈
如果我们抛开这道题，获取栈中的最小元素，我们就可以去遍历这个栈来找出我们的最小元素。但这道题限制我们需要在让时间复杂度为常数，所以说，一个栈是不能解决问题的，还需要在引入一个栈stack。
对于push方法，普通栈当中，所有数据都要放入，最小栈要对我们的普通栈第一次push进行维护。如果最小栈不为空，那么需要比较刚存放的数据与最小栈栈顶的数据进行比较，以对里面的最小值进行更新。这样顺便解决了getMin的实现，直接从最小栈栈顶获取。
对于pop方法，如果弹出的数据不是最小栈的栈顶数据，则只需要弹出普通栈的栈顶数据就行，否则则要弹出最小栈的栈顶数据。top相当于peek方法，只获取普通栈的栈顶元素。
这4个方法基本实现完成，但还有一个问题。如上图所示，如果我们再放入一个-1进入普通栈，那么最小栈需不需要再放入-1呢？答案是需要。因为按照我们的pop方法，把-1弹出，minstack也要弹出。
完整代码：
import java.util.Stack; public class MinStack { Stack<Integer> stack = new Stack<>(); Stack<Integer> minStack = new Stack<>(); public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int val) { stack.push(val); if(minStack.empty()){ minStack.push(val); }else{ int peekMinVal = minStack.peek(); if(val <= peekMinVal){ minStack.push(val); } } } public void pop() { int val = stack.pop(); if(val == minStack.peek()){ minStack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }
