深圳企业网站,做网站网页兼容性,电子商务网站设计的三大原则,批量查询收录1.栈
1.1什么是栈
栈是一种特殊的线性表#xff0c;只允许在固定的一段进行插入和删除操作#xff0c;进行插入和删除操作的一段称为栈顶#xff0c;另一端称为栈底。
栈中的数据元素遵顼后进先出LIFO#xff08;Last In First Out#xff09;的原则#xff0c;就像一…1.栈
1.1什么是栈
栈是一种特殊的线性表只允许在固定的一段进行插入和删除操作进行插入和删除操作的一段称为栈顶另一端称为栈底。
栈中的数据元素遵顼后进先出LIFOLast In First Out的原则就像一叠盘子只能在顶部添加或移除盘子。 压栈栈的插入操作叫做压栈/进栈/入栈新插入的元素在栈顶。
出战栈的删除操作叫做出栈要删除的 元素在栈顶。
从图上观察发现无论是插入还是删除操作栈底的位置不发生变化但是栈顶的位置会随插入或删除操作而发生变化。 1.2栈的常用方法
在Java标准库中提供了java.util.Stack栈的实现类此处的常用方法指的是Stack的常用方法。
Stack的常用方法如下表所示
方法解释Stack()构造方法构造一个空的栈E push(E,e)将元素e入栈并返回eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素的个数boolean empty()检验栈是否为空
注意
pop()是删除元素并返回删除删除前的栈顶元素的元素
peek()是获取栈顶元素并返回不进行出栈操作
常用方法的代码演示
public class Test {public static void main(String[] args) {StackString stacknew Stack();//入栈stack.push(My);stack.push(name);stack.push(is);stack.push(hajimi);//获取栈中有效元素的个数--4System.out.println(stack.size());//获取栈顶元素--hajimi 遵循后进先出System.out.println(stack.peek());//peek方法不会改变栈中的元素个数System.out.println(stack.size());//出栈String deleteElemstack.pop();//获取栈中有效元素的个数--3System.out.println(stack.size());//判断栈是否为空--falseSystem.out.println(stack.isEmpty());}
} 2.Stack
2.1什么是Stack
Java提供了多种方式来实现栈包括使用java.util.Stack类使用Deque接口或者手动实现栈。
java.util.Stack是Java标准库中提供的一个栈实现类。它继承自Vector类是一个线程安全的栈实现。 2.2 Stack的特点
1.线程安全
由于Stack继承自Vector它的所有方法都是同步的(线程安全的)。 2.动态扩容
Stack的底层是Vector它会根据需要进行动态扩容。
这是Vector的动态扩容方法的原码 2.3 Stack的局限性
虽然Stack提供了很方便的栈操作但仍存在一些局限性
1.继承自VectorStack继承自Vector意味着它继承了一些与栈无关的方法可能会导致误用
2.性能问题由于Stack是线程安全的它的同步机制可能会导致性能的下降尤其是单线程环境中 2.4实现一个Stack
Stack的底层是Vector而Vector的底层是数组接下来我们来编写自己的Stack。
代码编写
package datastructure;import java.util.Arrays;public class MyStack2 {//用来存放栈中的元素private int[] elem;//计算栈中有效元素的个数private int usedSize;//默认初始容量private static final int DEFAULT_SIZE10;public MyStack2(){this.elemnew int[DEFAULT_SIZE];}//判断栈是否已满private boolean isFull(){return elem.lengthusedSize;}//判断栈是否为空private boolean isEmpty(){return usedSize0;}//元素入栈方法public void push(int val){//判断栈是否已满如果已满进行扩容if(isFull()){Arrays.copyOf(elem,2*elem.length);}//将元素压入并将有效元素的个数加一elem[usedSize]val;}//元素出栈操作public int pop(){if(isEmpty()){System.out.println(栈中没有元素无法进行出栈操作);return Integer.MAX_VALUE;}//获取栈顶元素即要删除的元素int deleteElemelem[usedSize-1];usedSize--;return deleteElem;}//获取栈顶元素public int peek(){if(isEmpty()){System.out.println(栈为空无法获取栈顶元素);return Integer.MAX_VALUE;}return elem[usedSize-1];}//计算栈中元素的个数public int size(){return usedSize;}
}对上述的代码进行运行测试
public class Test {public static void main(String[] args) {MyStack2 myStack2new MyStack2();myStack2.push(1);myStack2.push(2);myStack2.push(3);myStack2.push(4);myStack2.push(5);System.out.println(当前栈中元素的个数:myStack2.size());System.out.println(获取栈顶元素:myStack2.peek());System.out.println(进行出栈:myStack2.pop());System.out.println(当前栈中元素的个数:myStack2.size());System.out.println(获取栈顶元素:myStack2.peek());}
}
运行结果 3.栈虚拟机栈栈帧
概念区分栈虚拟机栈和栈帧
栈一种数据结构遵循后进先出LIFO的原则允许在栈顶进行元素的插入和删除操作常用于括号匹配表达式求值深度优先搜索等场景。
虚拟机栈Java虚拟机JVM运行时数据区的一部分用于存储方法调用局部变量。每个线程都具有一个自己的虚拟机栈虚拟机栈中存储的是栈帧
栈帧是虚拟机栈中的一个条目用于存储方法调用的相关信息。每个方法调用都会创建一个栈帧并将其压入虚拟机栈方法结束后栈帧会被弹出。 4.栈的应用-逆波兰表达式求值
4.1 什么是逆波兰表达式
逆波兰表达式也称后缀表达式是一种特殊的算数表达式表示方式。在逆波兰表达式中操作符位于操作数之后这种表达方式的优点式不需要括号来表示操作的优先级从而简化了表达式的解析和计算 4.2 逆波兰表达式的特点
1.操作符在操作数之后例如普通的表达式 中缀表达式5 - 2 在逆波兰表达式中表示为 5 2 -
2.无需括号由于操作符位置明确不需要括号来表示优先级
3.易于计算可以使用栈这种数据结构计算表达式的值 4.3 如何用栈解决逆波兰表达式求值
我们知道栈遵循后入先出Last In First Out的原则逆波兰表达式中操作符位于操作数之后我们可以根据这两个特点对元素进行出栈和入栈操作。
1.先初始化一个空栈
2.从左向右扫描表达式如果遇到操作数就将其压入栈中如果遇到操作符就从栈中弹出两个元素进行计算并将计算的结果压入栈中
3.表达式扫描完成后栈顶元素即为计算的结果
假设传递的参数是一个数组tokens[2,1,,3,*]
将其转为中缀表达式(21)*39
代码编写
public int evalRPN(String[] tokens) {StackInteger stack new Stack();for (int i 0; i tokens.length; i) {String token tokens[i];if (isNumber(token)) {stack.push(Integer.parseInt(token));} else {int num2 stack.pop();int num1 stack.pop();switch (token) {case :stack.push(num1 num2);break;case -:stack.push(num1 - num2);break;case *:stack.push(num1 * num2);break;case /:stack.push(num1 / num2);break;default:}}}return stack.pop();
}
public boolean isNumber(String token) {return !(.equals(token) || -.equals(token) || *.equals(token) || /.equals(token));
}
