特色专业网站建设模板,沈阳网站建设哪家公司好,网站建设收费标准资讯,网站搭建论文什么是栈栈是一种特殊的线性表#xff0c;只允许一端进行数据的插入和删除#xff0c;即先进后出原则。类似于弹夹先装进去的子弹后面出#xff0c;后放入的子弹先出。栈的底层原理栈是一种线性结构#xff0c;所以既能使用数组实现#xff0c;也能使用链表实现#xff0…什么是栈栈是一种特殊的线性表只允许一端进行数据的插入和删除即先进后出原则。类似于弹夹先装进去的子弹后面出后放入的子弹先出。栈的底层原理栈是一种线性结构所以既能使用数组实现也能使用链表实现我就采用数组的方法实现一下栈public class MyStack {public int[] elem;private static final int DEFAULT_CAPACITY 10;public MyStack() {elem new int[DEFAULT_CAPACITY];}//既能统计栈中存储多少个有效数据也可以作为存放元素的下标public int usedSize;//压栈public void push(int val) {//先判满如果满了要扩容if(isFull()) {elem Arrays.copyOf(elem, elem.length * 2);}elem[usedSize] val;usedSize;}private boolean isFull() {return usedSize elem.length;}//出栈public int pop() {//先判空如果栈为空抛出异常if(empty()) {throw new EmptyArrayException(栈为空);}int val elem[usedSize-1];usedSize--;return val;}private boolean empty() {return usedSize 0;}//查看栈顶元素public int peek() {if(empty()) {throw new EmptyArrayException(栈为空);}return elem[usedSize-1];}//获取栈中有多少元素public int getUsedSize() {return usedSize;}
}使用数组的实现方式入栈只需要elem[usedSize] data和出栈只需要usedSize--的时间复杂度都是O1。如果使用单向链表采用头插法入栈和出栈只需要移动head头节点时间复杂度也是O(1);要是采用尾插法入栈和出栈入栈和出栈都需要从头节点出发走到尾巴才能完成元素的入栈或出栈时间复杂度为On).如果是双向链表那么一个节点即知道后继节点也知道前驱节点有头节点head也有尾节点tail采用头插法进行入栈和出栈只需要移动head头节点采用尾插法进行入栈和出栈也是一样只需要移动tail尾巴节点。栈的可能出栈顺序题目若入栈序列为1234进栈的过程中可以出栈则下面不可能的出栈序列是哪个A.1,4,3,2 B.2,3,4,1 C.3,1,4,2 D.3,4,2,1方法按题目给的入栈顺序结合选项加画图熟练以后不用画图A选项第一个出栈是1所以1进栈后出栈2进栈3进栈因为出栈的第二个是4所以23没有出栈4进栈。4出栈3出栈2出栈。所以A是可能的出栈序列B选项B选项第一个出栈的是2所以1进栈2进栈2出栈3进栈3出栈4进栈4出栈此时栈还剩11出栈。也是可能的出栈序列C选项你看C选项第一个出栈的是3所以123都进栈3再出栈它第二个出栈的是1但是此时栈顶元素是2所以这是不可能的出栈顺序D选项第一个出栈的是3所以要123都入栈了3是栈顶元素才能出栈接着4入栈4又出栈然后把栈中2出栈1出栈有关出栈顺序的oj题 https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId13tqId11174rp1ru/activity/ojqru/ta/coding-interviews/question-rankingpublic class Solution {public boolean IsPopOrder(int [] pushA, int [] popA) {StackInteger stack new Stack();int index 0;//popA数组下标//遍历压栈pushA数组for (int i 0; i pushA.length; i) {stack.push(pushA[i]);//如果栈顶元素和popA[index]相等//并且要防止栈为空空指针异常和数组越界//使用循环可能连着多个相等while (!stack.empty() index popA.length stack.peek() popA[index]) {stack.pop();index;}}//如果是可能的出栈序列那么栈中的元素能全部匹配全部被弹出//如果栈不为空说明是不可能的出栈序列return stack.empty();}
}中缀表达式转后缀表达式题目1中缀表达式23*6的后缀表达式题目2 中缀表达式23*5的后缀表达式中缀转后缀我们是加括号然后把操作符移到对应括号后面再去括号。同理中缀转前缀就是把操作符移到括号前面求后缀表达式/逆波兰表达式的计算结果力扣Oj: https://leetcode.cn/problems/evaluate-reverse-polish-notation/解决方法使用栈将数字放入栈中如果碰到操作符取出栈顶的2个元素第一个取出的放操作符右边第二个取出放操作符左边固定的计算完了再放入栈中直到遍历完该字符串数组此时栈中元素的值就是结果class Solution {public int evalRPN(String[] tokens) {//等会要进行运算类型用IntegerStackInteger stack new Stack();//遍历数组for(String x: tokens) {//判断是不是数字字符串if(! isOperation(x)) {//如果是数字字符串入栈stack.push(Integer.parseInt(x));//转为数字}else {//碰到操作符出栈2个数int num1 stack.pop();int num2 stack.pop();//根据不同操作字符进行运算,第一个弹出放操作符右边第二个放左边//运算完后重新入栈switch(x) {case :stack.push(num2 num1);break;case - :stack.push(num2 - num1);break;case *:stack.push(num2 * num1);break;case / :stack.push(num2 / num1);break;} }}//此时栈中元素就是运算结果return stack.pop();}private boolean isOperation(String x) {//字符串比较不能使用,是比较地址而不是比较值//字符串重写了Object类的equals()方法是比较值的if(x.equals() || x.equals(-) || x.equals(*) || x.equals(/)) {return true;//如果是操作符返回真}return false;//不是返回假}
}
