接单子做网站,德州网站建设公司,admin管理员登录,网站添加搜索关键字1. 栈#xff08;Stack#xff09;
1.1 概念
栈#xff1a;一种特殊的线性表#xff0c;只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。栈中数据元素遵循后进先出LIFO(Last In First Out)的原则
压栈Stack
1.1 概念
栈一种特殊的线性表只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中数据元素遵循后进先出LIFO(Last In First Out)的原则
压栈栈的插入操作可以叫做进栈、压栈、入栈入数据在栈顶
出栈栈的删除操作叫做出栈出数据在栈顶
1.2 栈的使用
方法功能Stack()构造一个空的栈E push(E e)将e入栈并返回eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空 public static void main(String[] args) {StackInteger s new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());//获取栈中有效数据System.out.println(s.peek());//查看栈顶元素System.out.println(s.pop());//使栈顶元素出栈System.out.println(s.empty());//检测栈是否为空System.out.println(s.isEmpty());//检测栈是否为空继承自Vector}
System.out.println(s.isEmpty());
上面的isEmpty()方法查看源码虽然栈中没有但是栈继承自Vector在父类Vector中有isEmpty方法
1.3 栈的模拟实现
import java.util.Arrays;public class MyStack {public int[] elem;public int usedSize;public MyStack() {this.elem new int[10];}public void push(int val) {if(isFull()) {//扩容elem Arrays.copyOf(elem,2*elem.length);}elem[usedSize] val;usedSize;}public boolean isFull(){return usedSize elem.length;}public int pop() {if(empty()) {return -1;}int oldVal elem[usedSize-1];usedSize--;return oldVal;}public int peek() {if(empty()) {return -1;}return elem[usedSize-1];}public boolean empty() {return usedSize 0;}
}
使用泛型实现
import java.util.Arrays;public class MyStackE {public Object[] elem;public int usedSize;public MyStack() {this.elem new Object[10];}public void push(E val) {if(isFull()) {//扩容elem Arrays.copyOf(elem,2*elem.length);}elem[usedSize] val;usedSize;}public boolean isFull(){return usedSize elem.length;}public E pop() {if(empty()) {return null;}E oldVal (E)elem[usedSize-1];usedSize--;return oldVal;}public E peek() {if(empty()) {return null;}return (E)elem[usedSize-1];}public boolean empty() {return usedSize 0;}
}1.4 栈的应用场景
1.将递归转化为循环 //递归方式public void printList(Node head) {if(null ! head) {printList(head.next);System.out.println(head.val );}}//运用栈的循环方式public void printList(Node head) {if(null head) {return;}StackNode s new Stack();//将链表中的节点保存在栈中Node cur head;while(null ! cur) {s.push(cur);cur cur.next;}//将栈中元素出栈while(!s.empty()) {System.out.println(s.pop().val );}}
2. 括号匹配 class Solution {public boolean isValid(String s) {StackCharacter 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 {//2.遇到右括号//先判断栈是否为空if(stack.empty()) {return false;}else {//3.取栈顶左括号看与当前右括号是否匹配char chL stack.peek();if(chL ( ch ) || chL [ ch ] || chL { ch }) {stack.pop();//若左右括号匹配则栈顶元素出栈}else {return false;}}}}return stack.empty();//最后若栈为空返回true栈不为空返回false}
}
3. 逆波兰表达式求值
解析
逆波兰表达式是一种后缀表达式所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式如 ( 1 2 ) * ( 3 4 ) 。该算式的逆波兰表达式写法为 ( ( 1 2 ) ( 3 4 ) * ) 。
逆波兰表达式主要有以下两个优点
去掉括号后表达式无歧义上式即便写成 1 2 3 4 * 也可以依据次序计算出正确结果。适合用栈操作运算遇到数字则入栈遇到算符则取出栈顶两个数字进行计算并将结果压入栈中
将中缀表达式转换为后缀表达式的方法 当逆波兰式运用到栈中按照次序将数字入栈若遇到运算符则取出栈顶两个数字先取出为运算符右边操作数后取出为运算符左边操作数这是为了避免当运算符为 - 或 / 时顺序不同造成结果不同的问题如下图 代码 public int evalRPN(String[] tokens) {StackInteger s new Stack();for (int i 0; i tokens.length; i) {String tmp tokens[i];if(!isOpearation(tmp)) {//判断当前字符串是否为运算符Integer val Integer.valueOf(tmp);//将字符串转换为数字s.push(val);}else {Integer val2 s.pop();Integer val1 s.pop();switch(tmp) {case :s.push(val1val2);break;case -:s.push(val1-val2);break;case *:s.push(val1*val2);break;case /:s.push(val1/val2);break;}}}return s.pop();}public boolean isOpearation(String s) {if(s.equals() || s.equals(-) || s.equals(*) || s.equals(/)) {return true;}return false;}
4. 出栈入栈次序匹配 public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStackInteger s new Stack();int count 0;for(int i 0; i pushV.length; i) {s.push(pushV[i]);//这个单独的循环必须保证栈不为空count不能越界栈顶元素等于count下标处值while(!s.empty() count ! popV.length s.peek() popV[count]){s.pop();count;}}return s.empty();}
5. 最小栈 class MinStack {StackInteger s;//普通栈泛型类型别忘记加StackInteger ms;//最小栈public MinStack() {//构造方法s new Stack();ms new Stack();}public void push(int val) {s.push(val);if(ms.empty()) {//若为第一次入栈操作则最小栈无条件入栈ms.push(val);}else {Integer peekVal ms.peek();//若不是第一次则需与最小栈栈顶元素进行比较if(val peekVal) {ms.push(val);}}}public void pop() {if(s.empty()) {return;}int popVal s.pop();//包装类属于引用类型不能直接所以此处用int接收自动拆箱if(popVal ms.peek()) {ms.pop();}}public int top() {if(s.empty()) {return -1;}return s.peek();}public int getMin() {if(ms.empty()) {return -1;}return ms.peek();}
}
1.5 栈、虚拟机栈、栈帧的区别
栈Stack是一种只允许在一端进行插入或删除的线性表满足后进先出的特点
虚拟机栈逻辑结构是具有特殊作用的一块内存空间主管Java程序的运行它保存方法的局部变量8种基本数据类型、对象的引用地址、部分结果并参与方法的调用和返回
栈帧函数从调用过程到结束的体现一个函数从调用到销毁中占用的空间内部的局部变量统一放在栈帧中。每个函数在运行时JVM都会创建一个栈帧然后将栈帧压入到虚拟机栈中当函数调用结束时该函数对应的栈帧会从虚拟机栈中出栈
