- 逆波兰表达式求值（ 后缀表达式）
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。(a+b)*c-(a+b)/e的后缀表达式为：
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
思路：构造一个判断运算符的函数，然后判断为数字则入栈，遇到运算符则弹出两个元素进行相关操作，将运算得到的结果再次入栈，直至将最后的元素弹出栈即为最后的结果。
( ( 1 2 + ) ( 3 4 + ) * )
1,2先入栈，遇到运算符+即出栈，1,2相加得3入栈，3，4同理得7入栈，最后遇到 * ,3，7出栈相乘得结果为21
代码实现：
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
//字符数组进行遍历
for(String x : tokens){
if(!isOperation(x)){
//使用parseInt()函数将字符串转换为整型
stack.push(Integer.parseInt(x));
}else{
//如果遇到运算符，弹出数据进行相关操作
int num2 = stack.pop();
int num1 = stack.pop();
switch(x){
case "+":
stack.push(num1+num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1*num2);
break;
case "/":
stack.push(num1 / num2);
break;
}
}
}
return stack.pop();
}
//判断是否为运算符
private boolean isOperation(String s){
if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
return true;
}else{
return false;
}
}- 将递归转化为循环
如：逆序打印链表
- 递归实现逆序打印
public void display(ListNode head){
if(head == null){
return;
}
//直到链表末尾，再归回去
if(head.next == null){
System.out.println(head.val+" ");
return;
}
display(head.next);
System.out.println(head.val+" ");
}- 使用栈实现
public void display(ListNode head){
if(head == null){
return;
}
Stack<ListNode> stack = new Stack<>();
ListNode cur = head;
while(cur!= null){
stack.push(cur);
cur = cur.next;
}
while(!stack.empty()){
ListNode ret = stack.pop();
System.out.println(ret.val+" ");
}
}利用栈先进后出的特性，将链表的节点都加入栈中，然后再依次出栈，并打印栈中节点的 val 的值，即实现了链表的逆序打印。✅栈、虚拟机栈、栈帧有什么区别呢？
栈： 一种先进后出的数据结构
虚拟机栈：JVM中的一块内存空间
栈帧：再调用函数过程当中，在java 虚拟机栈上开辟的一块内存
- 使用栈来实现队列
思路：初始化两个空栈s1,s2 当实现入队操作时，即入栈 s1 即可，出栈时 如果s1不为空，将s1当中的元素进行出栈，并入栈到s2 中去，s2再进行出栈，即实现了队列先进先出的效果，当s1与s2 都为空时，则此队列为空。
class MyQueue {
private Stack<Integer> s1;
private Stack<Integer> s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if(empty()){
return -1;
}
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if(empty()){
return -1;
}
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.empty()&&s2.empty();
}
}
- 使用队列来实现栈
思路：初始化两个空队列 q1与q2，当q1 或者 q2为空时，入队,两者都为空时，入队q1;
当弹出元素时，将其余size -1 个元素全部转移到另一个队列当中，剩余的一个元素出队即可，注意要将非空队列长度提前储存；取队首元素时，将出队列 1中的最后一个元素储存临时变量当中，返回临时变量即可
class MyStack {
private Queue<Integer> qu1;
private Queue<Integer> qu2;
public MyStack() {
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}
public void push(int x) {
if(!qu1.isEmpty()){
qu1.offer(x);
}else if(!qu2.isEmpty()){
qu2.offer(x);
}else{
qu1.offer(x);
}
}
public int pop() {
if(empty()){
return -1;
}
if(!qu1.isEmpty()){
int size = qu1.size()-1;
for(int i = 0;i <size;i++){
qu2.offer(qu1.poll());
}
return qu1.poll();
}else{
int size = qu2.size()-1;
for(int i = 0;i <size;i++){
qu1.offer(qu2.poll());
}
return qu2.poll();
}
}
public int top() {
if(empty()){
return -1;
}
if(!qu1.isEmpty()){
int size = qu1.size();
int ret = -1;
for(int i = 0;i <size;i++){
ret = qu1.poll();
qu2.offer(ret);
}
return ret;
}else{
int size = qu2.size();
int ret = -1;
for(int i = 0;i <size;i++){
ret = qu2.poll();
qu1.offer(ret);
}
return ret;
}
}
public boolean empty() {
return qu1.isEmpty()&&qu2.isEmpty();
}
}- 栈的压入、弹出序列匹配问题
/**
* 栈的次序匹配问题
* 判断出栈入栈是否符合
* @param pushA
* @param popA
* @return
*/
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;//遍历popA数组
for(int i = 0;i < pushA.length;i++) {
stack.push(pushA[i]);
// i下标所指元素直接入栈，入栈之后判断j下标所指元素是否相同
while(j < popA.length && !stack.empty() && stack.peek() == popA[j]) {
// 如果是则出栈,j++
stack.pop();
j++;
}
}
// 如果此时栈为空，则满足，不为空则不满足
return stack.empty();
}- 括号匹配问题
/*
* 括号匹配问题
* */
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length();i++) {
char ch = s.charAt(i);
//1. 判断是不是左括号
if(ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
}else {
if(stack.empty()) {
//2. 遇到了右括号 但是栈为空，此时不匹配！
return false;
}
char ch2 = stack.peek();
//3。 此时 如果满足 这里面的任何一个匹配逻辑 都是匹配的
if(ch2 == '[' && ch == ']' || ch2 == '(' && ch == ')' || ch2 == '{' && ch == '}') {
stack.pop();
}else{
return false;
}
}
}
//4. 当字符串遍历完成了，但是栈不为空，说明左括号还在栈当中没有匹配完成
if(!stack.empty()) {
return false;
}
return true;
}
}- 逆波兰表达式求值（ 后缀表达式）
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。(a+b)*c-(a+b)/e的后缀表达式为：
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
思路：构造一个判断运算符的函数，然后判断为数字则入栈，遇到运算符则弹出两个元素进行相关操作，将运算得到的结果再次入栈，直至将最后的元素弹出栈即为最后的结果。
( ( 1 2 + ) ( 3 4 + ) * )
1,2先入栈，遇到运算符+即出栈，1,2相加得3入栈，3，4同理得7入栈，最后遇到 * ,3，7出栈相乘得结果为21
代码实现：
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
//字符数组进行遍历
for(String x : tokens){
if(!isOperation(x)){
//使用parseInt()函数将字符串转换为整型
stack.push(Integer.parseInt(x));
}else{
//如果遇到运算符，弹出数据进行相关操作
int num2 = stack.pop();
int num1 = stack.pop();
switch(x){
case "+":
stack.push(num1+num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1*num2);
break;
case "/":
stack.push(num1 / num2);
break;
}
}
}
return stack.pop();
}
//判断是否为运算符
private boolean isOperation(String s){
if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
return true;
}else{
return false;
}
}- 将递归转化为循环
如：逆序打印链表
- 递归实现逆序打印
public void display(ListNode head){
if(head == null){
return;
}
//直到链表末尾，再归回去
if(head.next == null){
System.out.println(head.val+" ");
return;
}
display(head.next);
System.out.println(head.val+" ");
}- 使用栈实现
public void display(ListNode head){
if(head == null){
return;
}
Stack<ListNode> stack = new Stack<>();
ListNode cur = head;
while(cur!= null){
stack.push(cur);
cur = cur.next;
}
while(!stack.empty()){
ListNode ret = stack.pop();
System.out.println(ret.val+" ");
}
}利用栈先进后出的特性，将链表的节点都加入栈中，然后再依次出栈，并打印栈中节点的 val 的值，即实现了链表的逆序打印。✅栈、虚拟机栈、栈帧有什么区别呢？
栈： 一种先进后出的数据结构
虚拟机栈：JVM中的一块内存空间
栈帧：再调用函数过程当中，在java 虚拟机栈上开辟的一块内存
- 使用栈来实现队列
思路：初始化两个空栈s1,s2 当实现入队操作时，即入栈 s1 即可，出栈时 如果s1不为空，将s1当中的元素进行出栈，并入栈到s2 中去，s2再进行出栈，即实现了队列先进先出的效果，当s1与s2 都为空时，则此队列为空。
class MyQueue {
private Stack<Integer> s1;
private Stack<Integer> s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if(empty()){
return -1;
}
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if(empty()){
return -1;
}
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.empty()&&s2.empty();
}
}
- 使用队列来实现栈
思路：初始化两个空队列 q1与q2，当q1 或者 q2为空时，入队,两者都为空时，入队q1;
当弹出元素时，将其余size -1 个元素全部转移到另一个队列当中，剩余的一个元素出队即可，注意要将非空队列长度提前储存；取队首元素时，将出队列 1中的最后一个元素储存临时变量当中，返回临时变量即可
class MyStack {
private Queue<Integer> qu1;
private Queue<Integer> qu2;
public MyStack() {
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}
public void push(int x) {
if(!qu1.isEmpty()){
qu1.offer(x);
}else if(!qu2.isEmpty()){
qu2.offer(x);
}else{
qu1.offer(x);
}
}
public int pop() {
if(empty()){
return -1;
}
if(!qu1.isEmpty()){
int size = qu1.size()-1;
for(int i = 0;i <size;i++){
qu2.offer(qu1.poll());
}
return qu1.poll();
}else{
int size = qu2.size()-1;
for(int i = 0;i <size;i++){
qu1.offer(qu2.poll());
}
return qu2.poll();
}
}
public int top() {
if(empty()){
return -1;
}
if(!qu1.isEmpty()){
int size = qu1.size();
int ret = -1;
for(int i = 0;i <size;i++){
ret = qu1.poll();
qu2.offer(ret);
}
return ret;
}else{
int size = qu2.size();
int ret = -1;
for(int i = 0;i <size;i++){
ret = qu2.poll();
qu1.offer(ret);
}
return ret;
}
}
public boolean empty() {
return qu1.isEmpty()&&qu2.isEmpty();
}
}- 栈的压入、弹出序列匹配问题
/**
* 栈的次序匹配问题
* 判断出栈入栈是否符合
* @param pushA
* @param popA
* @return
*/
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;//遍历popA数组
for(int i = 0;i < pushA.length;i++) {
stack.push(pushA[i]);
// i下标所指元素直接入栈，入栈之后判断j下标所指元素是否相同
while(j < popA.length && !stack.empty() && stack.peek() == popA[j]) {
// 如果是则出栈,j++
stack.pop();
j++;
}
}
// 如果此时栈为空，则满足，不为空则不满足
return stack.empty();
}- 括号匹配问题
/*
* 括号匹配问题
* */
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length();i++) {
char ch = s.charAt(i);
//1. 判断是不是左括号
if(ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
}else {
if(stack.empty()) {
//2. 遇到了右括号 但是栈为空，此时不匹配！
return false;
}
char ch2 = stack.peek();
//3。 此时 如果满足 这里面的任何一个匹配逻辑 都是匹配的
if(ch2 == '[' && ch == ']' || ch2 == '(' && ch == ')' || ch2 == '{' && ch == '}') {
stack.pop();
}else{
return false;
}
}
}
//4. 当字符串遍历完成了，但是栈不为空，说明左括号还在栈当中没有匹配完成
if(!stack.empty()) {
return false;
}
return true;
}
}
