栈在现实生活中的例子：

二、栈的使用

 

 public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size()); // 获取栈中有效元素个数---> 4System.out.println(s.peek()); // 获取栈顶元素---> 4s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());}}

三、栈的模拟实现

import java.sql.Array;
import java.util.Arrays;public class MyStack {public int[] elem;public int usedSize;public MyStack(int[] elem) {this.elem = new int[10];}public void push(int data){if(ifFull()){grow();}elem[usedSize++]=data;}public boolean ifFull(){return elem.length==usedSize;}private void grow(){elem= Arrays.copyOf(elem,elem.length*2);}public int pop(){if(isEmpty()){throw new  EmptyException("栈为空");}else {int k=usedSize-1;usedSize--;return elem[k];}}private boolean isEmpty(){return usedSize==0;}public int peek(){if(isEmpty()){throw new  EmptyException("栈为空");}else {return elem[usedSize-1];}}
}

四、栈的应用场景

1. 改变元素的序列

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A: 1,4,3,2                        B: 2,3,4,1                          C: 3,1,4,2                     D: 3,4,2,1

答案：C

2. 一个栈的初始状态为空。现将元素 1 、 2 、 3 、 4 、 5 、 A 、 B 、 C 、 D 、 E 依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。

A: 12345ABCDE            B: EDCBA54321              C: ABCDE12345           D: 54321EDCBA

答案：B

---

单链表是否可以实现栈？

答：

• 顺序表实现的栈可以将插入、删除的时间复杂度达到O（1），
• 如果采用尾插操作，入栈时间复杂度为O（N），如果有last那么时间复杂度为O（1），但是出栈一定是O（N）
• 如果采用头插法，入栈时间复杂度为O（1），同时出栈的时间复杂度也是O（1）

结论：

• 如果采用单链表来实现栈，那么可以采用头插法的形式来入栈和出栈，叫做链式栈
• 采用双向链表来实现栈是完全ok的，入栈不管是头插还是尾插都可以实现，时间复杂度都可以达到O（1）

2. 将递归转化为循环

{Stack<Node> s = new Stack<>();// 将链表中的结点保存在栈中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}
// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}}

3. 括号匹配

class Solution {public boolean isValid(String s) {Stack<Character> stack=new Stack<>();for(int i=0;i<s.length();i++){char ch=s.charAt(i);//判断是否为左括号if(ch=='('||ch=='['||ch=='{'){stack.push(ch);//是左括号则入栈}else{if(stack.isEmpty()){return false;//不是左括号，但是栈空，右括号多}char ch2=stack.peek();if((ch2=='('&&ch==')')||(ch2=='['&&ch==']')||(ch2=='{'&&ch=='}')){stack.pop();//有括号刚好匹配左括号，出栈}else{return false;//右括号不匹配左括号，错误}}}if(!stack.isEmpty()){return false;//遍历结束但是但是栈不空，左括号多}return true;}
}

4. 逆波兰表达式求值

题目：中缀表达式a+b*c+(d*e+f)*g，其转换成后缀表达式为abc*+de*f+g*+。

将表达式按照运算先后加括号

a+b*c+(d*e+f)*g=（（a+（b*c））+（（(d*e）+f)*g））

再将每个运算符移出对应的括号外面

（（a+（b*c））+（（(d*e）+f)*g））=（（a（bc）*）+（（(de）*f)+g）*）+

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack=new Stack<>();for(int i=0;i<tokens.length;i++){String ch=tokens[i];if(isOperator(ch)==false){int z=Integer.parseInt(ch);stack.push(z);}else{int y=stack.pop();int x=stack.pop();switch(ch){case"+":stack.push(x+y);break;case"-" :stack.push(x-y);break;case"*" :stack.push(x*y);break;case"/":stack.push(x/y);break;}}}return stack.pop();}private boolean isOperator(String ch){if(ch.equals("+")||ch.equals("-")||ch.equals("*")||ch.equals("/")){return true;}return false;}
}

把字符串变成整形的函数Integer.parseInt（） 

5. 出栈入栈次序匹配

顺序遍历pushV，如果栈顶元素和popV当前元素相同，则弹出，不同则将pushV当前元素入栈

import java.util.*;
public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack=new Stack<>(); int j=0;for(int i=0;i<pushV.length;i++){stack.push(pushV[i]);while(stack.empty()==false&&j<popV.length&&stack.peek()==popV[j]){stack.pop();j++;}}return stack.empty();}
}

6. 最小栈

入栈：

• 普通栈一定要放
• 最小栈放的原则：
  • 如果最小栈是空的，则放
  • 如果放的元素小于等于当前栈顶的元素，则放

出栈：判断出栈元素和最小栈栈顶元素关系，相同则最小栈也出去

import java.util.Stack;class MinStack {public Stack<Integer> stack;public  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 {int peekVal = minStack.peek();if(val <= peekVal) {minStack.push(val);}}}public void pop() {if(stack.empty()) {return;}int popVal = stack.pop();if(popVal == minStack.peek()) {minStack.pop();}}public int top() {if(stack.empty()) {return -1;}return stack.peek();}public int getMin() {if(minStack.empty()) {return -1;}return minStack.peek();}
}

五、 概念区分

• 栈:是一种数据结构
• 虚拟机栈：是jvm中的一块内存
• 栈帧：运行一个方法、一个函数时，给它开辟的内存