网站建设服务费税率多少钱,网站站制做,网站后台管理系统制作教程,单页面网站多少钱一、栈的基本概念
栈#xff08;Stack#xff09;是一种特殊的线性数据结构#xff0c;遵循后进先出#xff08;Last In First Out#xff0c;LIFO#xff09;的原则。就像一摞盘子#xff0c;最后放上去的盘子总是最先被拿走。栈有两个主要操作#xff1a; 入栈… 一、栈的基本概念
栈Stack是一种特殊的线性数据结构遵循后进先出Last In First OutLIFO的原则。就像一摞盘子最后放上去的盘子总是最先被拿走。栈有两个主要操作 入栈Push 将一个元素添加到栈的顶部。 出栈Pop 移除并返回栈顶部的元素。 二、手写栈的实现 java
class MyStack {private int[] array; // 用于存储栈中的元素private int top; // 栈顶指针指向栈顶元素的索引private int capacity; // 栈的容量// 构造函数初始化栈的容量public MyStack(int capacity) {this.capacity capacity;this.array new int[capacity];this.top 1; // 初始时栈为空栈顶指针为 1}// 判断栈是否为空public boolean isEmpty() {return top 1;}// 判断栈是否已满public boolean isFull() {return top capacity 1;}// 入栈操作public void push(int element) {if (isFull()) {System.out.println(栈已满无法入栈);return;}array[top] element; // 先将栈顶指针加 1再将元素放入栈顶}// 出栈操作public int pop() {if (isEmpty()) {System.out.println(栈为空无法出栈);return 1;}return array[top ]; // 先返回栈顶元素再将栈顶指针减 1}// 获取栈顶元素public int peek() {if (isEmpty()) {System.out.println(栈为空没有栈顶元素);return 1;}return array[top];}} 三、栈的应用 1. 有效的括号 问题描述 给定一个只包括 (){}[] 的字符串判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合。 思路 遍历字符串遇到左括号就将其入栈遇到右括号就检查栈顶元素是否为对应的左括号如果是则出栈否则字符串无效。遍历结束后如果栈为空则字符串有效。 java
import java.util.Stack;public class ValidParentheses {public static boolean isValid(String s) {StackCharacter stack new Stack();for (char c : s.toCharArray()) {if (c ( || c { || c [) {stack.push(c); // 遇到左括号入栈} else {if (stack.isEmpty()) {return false; // 栈为空遇到右括号无效}char top stack.pop(); // 出栈栈顶元素if ((c ) top ! () || (c } top ! {) || (c ] top ! [)) {return false; // 括号不匹配无效}}}return stack.isEmpty(); // 栈为空则有效}public static void main(String[] args) {String s ()[]{};System.out.println(isValid(s));}} 2. 逆波兰表达式求值 问题描述 逆波兰表达式后缀表达式是一种数学表达式的表示方法其中运算符紧跟在操作数之后。给定一个逆波兰表达式求其值。 思路 遍历逆波兰表达式遇到操作数就入栈遇到运算符就从栈中弹出两个操作数进行运算再将结果入栈。遍历结束后栈中剩下的元素就是表达式的值。 java
import java.util.Stack;public class EvaluateReversePolishNotation {public static int evalRPN(String[] tokens) {StackInteger stack new Stack();for (String token : tokens) {if (isOperator(token)) {int operand2 stack.pop(); // 弹出第二个操作数int operand1 stack.pop(); // 弹出第一个操作数int result applyOperation(operand1, operand2, token); // 进行运算stack.push(result); // 将结果入栈} else {stack.push(Integer.parseInt(token)); // 遇到操作数入栈}}return stack.pop(); // 栈中剩下的元素就是表达式的值}// 判断是否为运算符private static boolean isOperator(String token) {return token.equals() || token.equals( ) || token.equals(*) || token.equals(/);}// 进行运算private static int applyOperation(int operand1, int operand2, String operator) {switch (operator) {case :return operand1 operand2;case :return operand1 operand2;case *:return operand1 * operand2;case /:return operand1 / operand2;default:return 0;}}public static void main(String[] args) {String[] tokens {2, 1, , 3, *};System.out.println(evalRPN(tokens));}}
练习1中缀转后缀表达式
规则 操作数直接输出。 运算符与栈顶比较优先级优先级高则入栈否则弹出栈顶。 左括号入栈右括号弹出直到左括号。
public String infixToPostfix(String infix) {MyStackCharacter stack new MyStack();StringBuilder postfix new StringBuilder();for (char c : infix.toCharArray()) {if (Character.isDigit(c)) {postfix.append(c);} else if (c () {stack.push(c);} else if (c )) {while (!stack.isEmpty() stack.peek() ! () {postfix.append(stack.pop());}stack.pop(); // 弹出左括号} else {while (!stack.isEmpty() priority(c) priority(stack.peek())) {postfix.append(stack.pop());}stack.push(c);}}while (!stack.isEmpty()) postfix.append(stack.pop());return postfix.toString();} 蓝桥杯中的常考点和易错点
常考点
栈的基本操作push、pop、peek、isEmpty。
括号匹配使用栈检查括号是否正确匹配。
逆波兰表达式求值使用栈计算逆波兰表达式的值。
数据结构的实现手写栈的实现理解其内部机制。
易错点
栈的边界条件容易忽略栈为空或栈满的情况导致运行时错误。
括号匹配的逻辑容易在处理右括号时忘记检查栈是否为空。
逆波兰表达式的操作符处理容易在计算时混淆操作数的顺序尤其是减法和除法。
数组越界在实现栈时容易因为数组越界而出现错误。
6. 相关知识点总结
栈的实现使用数组或链表实现栈的基本操作。
括号匹配通过栈检查括号是否正确匹配。
逆波兰表达式求值通过栈计算逆波兰表达式的值。
蓝桥杯常考点栈的基本操作、括号匹配、逆波兰表达式求值。
易错点栈的边界条件、括号匹配的逻辑、逆波兰表达式的操作符处理。 四、知识点总结 栈的特性 后进先出LIFO适用于需要处理最近发生的元素的场景。 栈的基本操作 入栈Push、出栈Pop、获取栈顶元素Peek、判断栈空isEmpty和栈满isFull。 栈的应用场景 括号匹配、表达式求值等。在括号匹配中利用栈来检查括号的闭合顺序在表达式求值中使用栈来处理操作数和运算符的运算顺序。 五、蓝桥杯常考点 栈的基本操作实现 可能要求选手手写栈的实现包括入栈、出栈等操作。 栈的应用问题 如括号匹配、表达式求值等经典问题考查选手对栈的理解和应用能力。 复杂度分析 要求分析栈操作和相关算法的时间复杂度和空间复杂度。 六、蓝桥杯易错点 栈的边界条件处理 在入栈和出栈操作时要注意栈空和栈满的情况避免出现数组越界等错误。 运算符优先级问题 在表达式求值中要正确处理运算符的优先级确保运算顺序正确。 数据类型转换 在处理逆波兰表达式求值时要注意将字符串转换为合适的数据类型进行运算。
