直播是网站怎么做,视频号推广入口,网站建设和网页设计是不是一样,哪个网站可以做微商文章目录 前言什么是栈(Stack)栈方法栈的模拟实现链表也可以实现栈逆波兰表达式逆波兰表达式在栈中怎么使用 前言
什么是栈(Stack)
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶#xff0… 文章目录 前言什么是栈(Stack)栈方法栈的模拟实现链表也可以实现栈逆波兰表达式逆波兰表达式在栈中怎么使用 前言
什么是栈(Stack)
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。遵循先进后出的原则。
类似于一串羊肉串后串进去的肉最先被吃到。 底层是数组
栈方法 栈的模拟实现
//接口
public interface IStack {//放元素void push(int x);//取元素int pop();//查看元素int peek();//栈大小int size();//判断满没满boolean empty();//判断空没空boolean full();
}package stackdemo;
import java.util.Arrays;
//类实现接口
public class MyStack implements IStack{private int[] elem;//栈的底层是一个数组private int usedSize;//有效数据的个数private static final int DEFAULT_CAPACITY 10;//自定义数组长度//构造方法public MyStack(){elem new int[DEFAULT_CAPACITY];}//放栈顶元素Overridepublic void push(int x) {//先检查满没满if (full()){//满了调用数组拷贝扩容空间elem Arrays.copyOf(elem,elem.length*2);}//没满就放xelem[usedSize] x;usedSize;}//取出栈顶元素Overridepublic int pop() {if (empty()){//抛异常throw new EmptyException(栈空了);}int old elem[usedSize-1];//usedSize往栈底移动一格usedSize--;//相当于删除//如果是引用类型//elem[usedSize] null;return old;}//查找栈顶的元素跟pop不一样的是peek不用删除噢只是返回栈顶那个元素噢Overridepublic int peek() {if (empty()){//抛异常throw new EmptyException(栈空了);}return elem[usedSize-1];//}/算栈的大小Overridepublic int size() {return usedSize;}//判断栈空没空Overridepublic boolean empty() {return usedSize 0;}//判断栈满没满Overridepublic boolean full() {if (usedSize elem.length){return true;}return false;}
}
//抛异常
public class EmptyException extends RuntimeException {//构造方法public EmptyException(String msg){super(msg);}
}链表也可以实现栈
单链表 双向链表 从头入 从头出都可以 若进栈序列为 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 一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈然后再依次出栈则元素出栈的顺 序是 。 A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA 答案B
逆波兰表达式
下面举的例子是后缀表达式就是把符号移到括号右边。 怎么转换成逆波兰表达式 逆波兰表达式在栈中怎么使用
1.把式子转换成逆波兰表达式后 2.遇到数字就放栈里面 2.当遇到非数字字符取出栈里面最顶上的两个元素第一个元素放在字符右边第二个放左边。 3.得到的结果又放进栈里面 4.再继续上面步骤 逆波兰表达式演示视频 class Solution {public int evalRPN(String[] tokens) {StackInteger stack new Stack();for(String s : tokens) {//不是操作符就是数字if (!isOperation(s)) {stack.push(Integer.parseInt(s));} else {int num2 stack.pop();int num1 stack.pop();switch (s) {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;//是返回true}//不是返回falsereturn false;}
}
