数据结构(Java版)第十期：栈和队列(一)

专栏：数据结构(Java版)

个人主页：手握风云

一、栈

1.1. 栈的概念

1.2. 栈的使用

1.3. 栈的模拟实现

二、栈的经典面试题

2.1. 逆波兰表达式

2.2. 有效的括号

2.3. 最小栈

一、栈

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--;//相当于把数据置为nullreturn 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();}
}