Java - 数据结构，栈

一、栈

1.1、什么是栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈
顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶

什么是Java虚拟机栈？

java虚拟机栈也是栈，就是JVM中的一块内存，也是符合栈的规则 – 先进后出规则

方法区：存放类定义信息、字节码、常量等数据，在Sun HotSpot JVM中，这块也称为Perm Gen。
 
堆：创建的对象信息将放入堆中，堆内部如何实现各虚拟机各不相同，对于Sun HotSpot JVM来说又分为Young Gen和Tenured Gen，更详细描述参见《[Java性能剖析]Sun JVM内存管理和垃圾回收 》
 
Java栈：对于每个执行线程，会分配一个Java栈，JVM在执行过程当中，每执行一个方法，都会为方法在当前栈中增加一个栈帧，每个栈帧的信息与具体实现相关，但一般会由3部分组成：变量区，方法参数和本地变量会放入这个位置，大小是固定的，在进行方法时会先分配好，在类定义中，会由max local来指定这块区的大小；方法信息区，会包括当前类常量池的入口地址等信息，这块大小也是固定的；操作栈，与Intel体系架构中的运算使用寄存器来进行不一样，JVM的字节码的方法调用、运算等需要的参数，都是通过操作栈来传递的。在类定义中，会由max stack指定最大的操作栈。关于Java栈的更详细描述参见《Java 栈内存介绍 》
 
本地方法栈：对本地方法的调用，并不会使用Java栈而是使用本地方法栈，本地方法栈的组成取决于所使用的平台和操作系统.
 
PC寄存器/程序计数器：对于每个执行线程会分配一个PC寄存器，寄存器中存放当前字节码的执行位置

什么是栈帧？
调用函数的时候，我们会为函数开辟一块内存，这块内存叫做栈帧，这个内存在Java虚拟机栈中开辟

2.2、栈的笔试题

2.2.1、一个栈的输入顺序是ABCDEF，那么不可能出现的出栈顺序是什么（）

A、DCBAEF

B、ACBEDF

C、DEFBCA

D、CDBAFE

在出栈的时候可以入一个出一个，入栈和出栈的顺序可以打乱，但是出栈的时候，一定是先出栈顶的元素

剑指 Offer 31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

public boolean validateStackSequences(int[] pushed, int[] popped) {Stack<Integer> stackA = new Stack<Integer>();int j = 0;//遍历数组pushedfor(int i = 0; i < pushed.length; i++){stackA.push(pushed[i]);//判断栈顶元素是否和popped数组的j下标相等，如果相等就出栈while(j < popped.length && !stackA.empty() && stackA.peek() == popped[j]){stackA.pop();j++;}    }return stackA.empty();}

2.2.2、中缀表达式转后缀表达式

它们都是对表达式的记法，因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同：前缀表达式的运算符位于与其相关的操作数之前；中缀和后缀同理。

举例：
(3 + 4) × 5 - 6 就是中缀表达式

-× + 3 4 5 6 前缀表达式

3 4 + 5 × 6 - 后缀表达式

中缀表达式（中缀记法）
中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。
虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。

前缀表达式（前缀记法、波兰式）
前缀表达式的运算符位于操作数之前。

后缀表达式（后缀记法、逆波兰式）
后缀表达式与前缀表达式类似，只是运算符位于操作数之后。

如何将中缀表达式转换成后缀表达式

利用栈实现计算后缀表达式的值：逆波兰表达式求值

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(int i = 0; i < tokens.length; i++){String val = tokens[i];if(isOperator(val) == false){stack.push(Integer.parseInt(val));}else {int num2 = stack.pop();int num1 = stack.pop();switch (val){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();}//判断是不是运算符，是就返回true，不是就返回FALSEprivate boolean isOperator(String val){if(val.equals("+") || val.equals("-") || val.equals("*") || val.equals("/")){return true;}return false;}
}

2.3、栈的方法

public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);stack.push(2);stack.push(3);stack.push(4);System.out.println(stack);System.out.println(stack.pop());System.out.println(stack);stack.peek();System.out.println(stack);}

2.4、模拟实现一个栈

public class MyStack {public int elem[];public int usedSize;public MyStack(){//源码中默认大小为10this.elem = new int[10];}//添加元素public void push(int val){//判断是否满if(isFull()){//如果满了就要扩容,this.elem = Arrays.copyOf(elem, 2*this.usedSize);}this.elem[this.usedSize] = val;this.usedSize++;}private boolean isFull(){//满了返回truereturn this.elem.length == this.usedSize;}//出栈public int pop(){//首先要判断栈里面有没有元素if(empty()){//如果没有元素就不能出栈，此时就要抛出异常throw new RuntimeException("栈为空！");}//如果有元素就可以出栈了int oldVal = this.elem[usedSize-1];//如果栈里面存的是引用类型，那这个就要置位nullusedSize--;return oldVal;}public boolean empty(){return this.usedSize == 0;}//获取栈顶元素public int peek(){//首先要判断栈里面有没有元素if(empty()){//如果没有元素就不能出栈，此时就要抛出异常throw new RuntimeException("栈为空！");}return this.elem[usedSize-1];}}

面试题：能不能用单链表实现一个栈

首先，要实现一个栈，就要知道栈的特点
1、先进后出
2、入栈和出栈的时间复杂度是O(1)
那单链表呢，单链表可以头插和尾插，那用头插还是插？？？
如果用头插：在入栈的时候就头插，时间复杂度也是O(1)，出栈的时候只要删除头结点，时间复杂度也是O(1)。
如果用尾插：那就不可能实现，在插入的时候可以用尾插，时间复杂度是O(1)，但是在出栈的时候就不行了，在删除尾巴节点的时候，要知道尾巴节点的前驱才能删除，但是这时候就要遍历一遍链表，时间复杂度就是O(n)

那单链表不行，就可以使用双向链表。

有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

/在做这道题的时候要考虑几种情况//1、左括号多了 （（（  ））//2、右括号多了 （（（（（  ））//2、括号不匹配  （ [ ] } public boolean isValid(String s) {//栈里面存放的是左括号Stack<Character> stack = new Stack<>();char[] chars = s.toCharArray();for(int i = 0; i < chars.length; i++){if(chars[i] == '[' || chars[i] == '(' || chars[i] == '{'){stack.push(chars[i]);}else{if(stack.empty()){//右括号多了return false;}else{if((chars[i] == '}' && stack.peek() == '{') || (chars[i] == ']' && stack.peek() == '[') || (chars[i] == ')' && stack.peek() == '(')){stack.pop();}else{//括号不匹配return false;}}}}if(!stack.empty()){//右括号多了return false;}return true;}

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

 private Stack<Integer> stack;private 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(!minStack.empty()){if(popVal == minStack.peek()){minStack.pop();}}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}